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

1. DFS란...?

• 정점의 자식들을 먼저 탐색

 

2. 구현 전 생각정리

• 탐색할 그래프를 딕셔너리와 데크를 활용하여 구현해보자
• need_visit 데크의 오른쪽에서 하나씩 node를 뽑아오며 탐색하면 최대 깊이까지 탐색하고 다시 올라오는 느낌으로의 탐색이 가능

 

3. 코드 구현

from collections import deque

graph = dict()

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

def bfs(graph, start_node):
    visited = deque()
    need_visit = deque()
    
    need_visit.append(start_node)
    
    while need_visit:
        node = need_visit.pop()
        if node not in visited: #아직 탐색 안된 상태라면
            visited.append(node)
            need_visit.extend(graph[node])#아래 level도 need_visit에 추가되겠지만 현 level이 다 탐색 된 이후에 탐색됨
            
    return visited


bfs(graph,'A')

 

4. 시간 복잡도

• while문이 '노드 수' + '간선 수' 만큼 실행되므로 O(노드 수 + 간선 수)