Algorithm/Study
2021. 9. 17.
그래프 탐색 알고리즘 : DFS (Python)
DFS - 개념 : 그래프에서 깊은 부분을 우선적으로 탐색하는 깊이 우선 탐색 알고리즘이다. - 스택 자료구조 이용 (= 파이썬 리스트. 재귀 함수를 이용했을 때 구현이 간결) - 시간 복잡도 : O(N) - 인접리스트로 구현시 - 장점 : 1) BFS에 비해 저장공간의 필요성이 적다. 2) 찾아야 하는 노드가 깊은 단계에 있을 수록, 그 노드가 왼쪽에 있을 수록 BFS보다 유리하다. - 단점 : 1) 목표 노드가 없는 경로에 깊이 빠질 수 있다. 2) 최단 경로가 보장되지 않는다. - 사용예 : 위상정렬, 사이클 탐지 - 구현 # DFS def dfs(graph, v, visited): visited[v] = True # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]:..
