그래프에 DFS 구현하기
이 연습 문제에서는 그래프를 순회하기 위한 깊이 우선 탐색(DFS) 알고리즘을 구현해 보겠습니다.
단계를 다시 살펴보면 다음과 같아요:
- 임의의 정점에서 시작합니다.
- 해당 정점을 방문한 정점 리스트에 추가합니다.
- 현재 노드의 인접 정점 각각에 대해
- 이미 방문했다면 -> 건너뜁니다
- 아직 방문하지 않았다면 -> DFS를 재귀적으로 수행합니다
코드를 테스트할 수 있도록, 다음 그래프가 딕셔너리를 사용해 로드되어 있어요.
graph = {
'0' : ['1','2'],
'1' : ['0', '2', '3'],
'2' : ['0', '1', '4'],
'3' : ['1', '4'],
'4' : ['2', '3']
}
이 연습은 강의의 일부입니다
Python으로 배우는 자료구조와 알고리즘
연습 안내
current_vertex가 아직 방문되지 않았는지 확인하세요.current_vertex를visited_vertices에 추가하세요.- 적절한 값을 전달하여
dfs()를 재귀적으로 호출하세요.
실습형 인터랙티브 연습
이 예제를 이 샘플 코드를 완성하여 풀어보세요.
def dfs(visited_vertices, graph, current_vertex):
# Check if current_vertex hasn't been visited yet
if current_vertex not in ____:
print(current_vertex)
# Add current_vertex to visited_vertices
____.add(____)
for adjacent_vertex in graph[current_vertex]:
# Call recursively with the appropriate values
____(____, ____, ____)
dfs(set(), graph, '0')