(알고리즘) 깊이우선탐색 (DFS)

1. 파이썬으로 그래프를 표현하는 방법

• 파이썬에서 제공하는 딕셔너리와 리스트 자료 구조를 활용해서 그래프를 표현할 수 있음

 

graph = dict()

graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']

 

3. DFS 알고리즘 구현

• 자료구조 스택과 큐를 활용함
  • need_visit 스택과 visited 큐, 두 개의 자료 구조를 생성

BFS 자료구조는 두 개의 큐를 활용하는데 반해, DFS 는 스택과 큐를 활용한다는 차이가 있음을 인지해야 함

 

 1 - 1. BFS의 처음과 비슷하다. 먼저 최상단 노드를 need_visit stack에 넣고 pop()을 한 후 visited queue에 존재하는지 확인 후 없다면 삽입

1 - 2. A의 값인  B, C를 need_visit에 넣는다. 

2 - 1. BFS와 다르게 이번엔 맨 끝의 node인 C를 pop()하여 처리한다. need_visit이 stack이기 때문이다.

 

위의 순서를 계속 반복한다.

코드로 나타내보면 아래와 같다.

 

def dfs(graph, start_node):
    visited, need_visit = list(), list()
    need_visit.append(start_node)
    
    while need_visit:
        node = need_visit.pop()  # BFS와 달리 pop(0)이 아니라 pop()이다. 맨 끝의 값을 빼내는 메소드이다.
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
    
    return visited

 

4. 시간 복잡도

• 일반적인 DFS 시간 복잡도
  • 노드 수: V
  • 간선 수: E
    • 위 코드에서 while need_visit 은 V + E 번 만큼 수행함
  • 시간 복잡도: O(V + E)