BFS와 DFS

BFS와 DFS란?

• 너비 우선 탐색(Breadth First Search) : 정점들과 같은 레벨에 있는 노드들을 먼저 탐색
• 깊이 우선 탐색(Depth First Search) : 정점의 자식들을 먼저 탐색
• 시간 복잡도는 정점의 수(V)와 간선의 수(E)를 더한 O(V + E)
• 파이썬에서는 딕셔너리와 리스트 자료구조를 활용해서 구현 가능

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']

너비 우선 탐색(BFS)

- 큐의 역할을 하는 visited와 need_visit을 이용해 구현

- 방문한 노드는 visited에, 방문할 노드는 need_visit에 추가

def bfs(graph, start_node):
    visited = list()
    need_visit = list()
    
    need_visit.append(start_node)
    
    while need_visit:
        node = need_visit.pop(0)
        if node not in visited:
            visited.appned(node)
            need_visit.extend(graph[node])
    
    return visited

 

깊이 우선 탐색(DFS)

- 큐의 역할을 하는 visited, 스택의 역할을 하는 need_visit을 이용해 구현

def dfs(graph, start_node):
    visited = list()
    need_visit = list()
    
    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])
    
    return visited