깊이 우선 탐색(DFS)
루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.
사용하는 경우
모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다
특징
- 자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다
- 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다. 검사하지 않을 경우 무한루프에 빠질 위험이 있다.
장/단점
- 장점
- 현재 경로상의 노드들만 기억하면 되므로, 저장 공간의 수요가 비교적 적다
- 목표 노드가 깊은 단계에 있는 경우 해를 빨리 구할 수 있다
- 구현이 BFS보다 간단하다
- 단점
- 단순 검색 속도가 BFS보다 느리다
- 깊이 우선 탐색은 해를 구하면 탐색이 종료되므로, 구한 해가 최단 경로가 된다는 보장이 없다
시간복잡도
- 인접리스트 : O(V+E) (V : 정점의 개수, E : 간선의 개수)
- 한번 방문한 지점은 다시 방문하지 않는다
- 하나의 정점에서 다음으로 방문할 정점들을 순회하는 횟수가 그 정점의 간선의 개수와 같기 때문이다
- 인접행렬 : O(V^2) (V: 정점의 개수)
- DFS를 호출하는 회수 V
- 다음 방문할 정점을 찾을 때 모든 정점을 순회하며 두 정점이 연결되어 있는지 확인해야 하기 때문이다
구현
def dfs(graph, start_node):
visit = list()
stack = list()
stack.append(start_node)
while stack:
node = stack.pop()
if node not in visit:
visit.append(node)
stack.extend(graph[node])
return visit너비우선탐색(BFS)
루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다. 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
사용하는 경우
두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때
특징
- 재귀적으로 동작하지 않는다
- 어떤 노드를 방문했었는지 여부를 검사해야한다. 검사하지 않을 경우 무한 루프에 빠질 위험이 있다
- 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료구조인 큐(Queue)를 주로 사용한다.
장/단점
- 장점
- 노드의 수가 적고 깊이가 얕은 경우 빠르게 동작할 수 있다
- 단순 검색 속도가 DFS보다 빠르다
- 너비를 우선으로 탐색하기 때문에 답이 되는 경로가 여러개인 경우에도 최단 경로를 보장한다
- 단점
- 재귀적으로 동작하지 않기 때문에 저장공간이 많이 필요하다
구현
def bfs(graph, start_node):
visit = list()
queue = list()
queue.append(start_node)
while queue:
node = queue.pop(0)
if node not in visit:
visit.append(node)
queue.extend(graph[node])
return visit시간 복잡도
BFS와 동일하다
