Overview

그래프 탐색 알고리즘은 그래프 구조에서 특정 vertex나 path를 찾기 위해 사용되는 알고리즘이다. 총 4가지 알고리즘을 소개한다.

Breadth-first search

Breadth-first search(너비 우선 탐색 ; BFS)는 최대한 넓게 이동한 뒤, 더 이상 갈 수 없을 때 아래로 이동하는 탐색 방법이다.

• Queue를 사용한다.

Time complexity

• Initialization: $O(|V|)$
• Enqueuing/Dequeuing: $O(|V|)$
• Scanning adjacent vertices: $O(|E|)$
• Total: $O(|V| + |E|)$

Depth-first search

Depth-first search(깊이 우선 탐색 ; DFS)는 최대한 깊이 내려간 뒤, 더 이상 내려갈 곳이 없을 경우 옆으로 이동하는 탐색 방법이다.

• 재귀 함수 또는 스택을 사용한다.

Time complexity

• Initialization: $O(|V|)$
• Traversing vertices: $O(|V|)$
• Scanning adjacent vertices: $O(|E|)$
• Total: $O(|V| + |E|)$