너비 우선 탐색이라 하며 BFS(Breadth-First Search)라 부름.
루트 노드 혹은 임의의 노드에서 시작해 인접한 노드를 먼저 탐색하는 방법.
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
즉, 깊게 탐색하기 전에 넓게 탐색하는 것이다.
큐를 사용한다. (해당 노드의 주변부터 탐색해야 하기 때문이다.)
최소 비용(즉, 모든 곳을 탐색하는 것보다 최소 비용이 우선일 때)에 적합하다.
# 딕셔너리 타입인 graph와 시작 노드를 인자로 받는다.
def bfs(graph, start_node):
visited = list()
need_visit = list()
need_visit.append(start_node)
while need_visit:
# BFS는 큐를 사용하기 때문에 pop(0)을 사용.(FIFO)
node = need_visit.pop(0)
if node not in visited:
visited.append(node)
need_visit.extend(graph[node])
return visited
깊이 우선 탐색이며 DFS(Depth-First Search)라고 부른다.
루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색한다.
넓게 탐색하기 전에 깊게 탐색하는 것이다.
예를 들어, 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.
스택이나 재귀함수를 통해 구현한다.
모든 경로를 방문해야 할 경우 사용에 적합하다.
def dfs(graph, start_node):
visited = list()
need_visit = list()
need_visit.append(start_node)
while need_visit:
# DFS는 스택을 사용하기 때문에 pop()을 사용.(FILO)
node = need_visit.pop()
if node not in visited:
visited.append(node)
need_visit.extend(graph[node])
return visited