1. 탐색 알고리즘

트리에 순회가 있다면, 그래프에는 탐색 알고리즘이 있다. 탐색 알고리즘이란, 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘을 의미한다.

트리의 순회는 트리에 있는 정점들을 모두 확인한다는 것 이외에는 큰 의미가 없었지만, 그래프는 트리보다 구조가 훨씬 복잡하기 때문에 탐색 과정에서 얻어지는 정보가 매우 중요하다. 이를테면

와 같은 정보들 말이다람쥐.

그래프의 탐색 알고리즘 중에는 크게 깊이 우선 탐색과 너비 우선 탐색이 존재한다람쥐.

Untitled

2. DFS

먼저 깊이 우선 탐색(Depth-First Search), 줄여서 DFS라 하는 녀석에 대해 알아보자.

DFS란 그래프의 깊이를 우선하여 그래프를 탐색하는 방식이다. 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 따라간다.

Untitled

무슨 말인지 잘 이해가 되지 않는 사람들에게 예시를 들기 위해 그래프 하나를 준비했다. 이 그래프에 DFS를 적용해 보자. 단, 탐색해야 할 정점이 두 개 이상일 경우 알파벳이 앞서는 정점을 먼저 탐색한다고 하자.

먼저 우리는 s에서 시작한다. s와 인접한 정점 중에서 우리는 a와 b를 탐색하지 않았으므로, 다음으로 탐색해야 할 정점은 a이며 우리는 간선 (s, a)를 따라간다.
도착한 정점 a에 인접한 정점 중에서 우리는 c와 d를 탐색하지 않았으므로, 다음으로 탐색해야 할 정점은 c이며 우리는 간선 (a, c)를 따라간다.