그래프 탐색 알고리즘 : DFS (Python)

DFS

---

깊이 우선 탐색 gif

 

- 개념 : 그래프에서 깊은 부분을 우선적으로 탐색하는 깊이 우선 탐색 알고리즘이다. 

- 스택 자료구조 이용 (= 파이썬 리스트. 재귀 함수를 이용했을 때 구현이 간결)

- 시간 복잡도 : O(N) - 인접리스트로 구현시

 

- 장점 : 

  1) BFS에 비해 저장공간의 필요성이 적다. 

  2) 찾아야 하는 노드가 깊은 단계에 있을 수록, 그 노드가 왼쪽에 있을 수록 BFS보다 유리하다.

 

- 단점 :

  1) 목표 노드가 없는 경로에 깊이 빠질 수 있다.

  2) 최단 경로가 보장되지 않는다.

 

- 사용예 : 위상정렬, 사이클 탐지

 

- 구현

# DFS
def dfs(graph, v, visited):
	visited[v] = True
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

# 인접 리스트
graph = [
	[], # 0번 노드와 인접한 노드
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9
dfs(graph, 1, visited)

1) 탐색 시작노드를 스택에 삽입하고 방문 처리를 한다.

2) 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. (인접한 노드 중에서 방문하지 않은 노드가 여러 개 있으면 번호가 낮은 순서부터 처리한다.)

3) 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.