[파이썬][알고리즘] 너비 우선 탐색과 깊이 우선 탐색

너비 우선 탐색

BFS와 DFS

1. 너비 우선 탐색 (Breadth First Search): 노드들과 같은 레벨에 있는 노드를 먼저 탐색하는 방법
2. 깊이 우선 탐색 (Depth First Search): 한 노드의 자식을 끝가지 간 후 다시 돌아와 다른 노드로 돌아간 후 그 노드의 자식들을 탐색

• 어떤 방식을 택하는지에 따라서 같은 그래프라 할지라도 탐색하는 순서가 달라진다.

그래프 표현

• 파이썬에서는 딕셔너리와 리스트 자료 구조를 이용하여 표현한다.
  • 노드를 딕셔너리의 키로 두고 키에 대한 값을 인접 노드의 리스트로 만든다.

 

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

graph

{'A': ['B', 'C'],
 'B': ['A', 'D'],
 'C': ['A', 'G', 'H'],
 'D': ['B', 'E', 'F'],
 'E': ['D'],
 'F': ['D'],
 'G': ['C'],
 'H': ['C', 'I'],
 'I': ['H']}

BFS 구현

• 큐를 이용하여 구현한다.
  • 파이썬에서는 list의 기능으로 구현할 수 있다.

def bfs(graph, first_node):
    checked = list() # 탐색 끝난 노드
    line_up = list() # 탐색 할 노드

    line_up.append(first_node)

    while line_up:
        node = line_up.pop(0) # pop(0) 0번째 데이터 뽑고 삭제
        if node not in checked:
            checked.append(node)
            line_up.extend(graph[node])

    return checked

bfs(graph, 'A')

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

시간 복잡도

• 노드 수: V
• 간선 수: E
• 시간 복잡도: O(V+E)

깊이 우선 탐색

DFS 구현

• 스택과 큐를 이용하여 구현한다.
  • BFS에서 line_up 리스트를 스택으로 한다.
  • 리스트의 기능을 이용하여 구현할 수 있다.

def dfs(graph, first_node):
    checked, line_up = list(), list()

    line_up.append(first_node)

    while line_up:
        node = line_up.pop() # pop에 인자가 없으면 가장 마지막 데이터를 가져오고 삭제
        if node not in checked:
            checked.append(node)
            line_up.extend(graph[node])

    return checked

dfs(graph, 'A')

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

시간 복잡도

• O(V+E)