• 그래프의 탐색 (search) 알고리즘 : 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘
• 트리의 순회는 트리에 있는 정점들을 모두 확인한다는 것 외에 큰 의미가 없지만, 그래프는 트리보다 구조가 훨씬 복잡할 수 있기 때문에 탐색 과정에서 얻어지는 정보가 아주 중요하다.
• 탐색 과정에서 어떤 간선이 사용되었는지, 또 어떤 순서로 정점들이 방문되었는지를 통해 그래프의 구조를 알 수 있다.
• 탐색 알고리즘 중 가장 널리 사용되는 두 가지가 깊이 우선 탐색과 너비 우선 탐색이다.

2. 그래프의 깊이 우선 탐색

2.1 깊이 우선 탐색 (depth-first search, DFS) 란?

그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법

• 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 따라가는 것
• 더이상 갈 곳이 없는 막힌 정점에 도달하면 포기하고, 마지막에 따라왔던 간선을 따라 뒤로 돌아간다.

DFS EX)

실선 화살표 : DFS가 따라가는 간선 점선 화살표 : 더 갈 정점이 없어서 뒤로 돌아가는 경우 화살표가 없는 점선 : 탐색 과정에서 따라가지 않은 간선

• 정점 s에서 탐색을 시작하되, 각 인접한 정점들을 알파벳 순서대로 검사한다고 할 때 DFS
• DFS 는 각 과정에서 가능한 한 그래프 안으로 '깊이' 들어가려고 시도하며, 막힌 정점에 도달하지 않는 한 뒤로 돌아가지 않음.