[그래프 알고리즘]DFS 깊이 우선 탐색

그래프 탐색

그래프를 탐색한다는 것은, 한 노드에서 시작해 엣지를 따라 다른 노드들을 방문하는 것입니다.

이때 노드를 방문하기 위해 깊이를 우선으로 할수도 있고, 너비를 우선으로 할 수도 있습니다.

Depth First Search

DFS는 말 그대로 깊이를 우선하여 노드들을 방문하는 방법을 말합니다.

한 노드에서 시작해, 아직 방문하지 않았고 엣지를 따라 방문할 수 있는노드가 있으면 우선적으로 방문합니다.

현재 노드에서 엣지를 따라 방문할 수 있더라도 이미 방문한 노드는 방문하지 않아야 하기 때문에,

노드들을 방문했는지 표시해야합니다.

 

한 노드에서 DFS를 시작하더라도 모든 노드를 방문할 수 있는 것은 아닙니다.

서로 연결되지 않는 두 그래프가 있다면, 한 그래프에서 시작한 DFS는 다른 그래프로 방문할 수 없습니다.

한 그래프에 있더라도, 방향 그래프인 경우 두 노드가 연결될 수 없는 경우도 존재합니다.

예를 들어 DAG(Directed Acyclic Graph, 유향 비순환 그래프) 의 중간에서 DFS를 시작하면, 

시작 노드로 들어오는 엣지는 방문하지 못하기 때문에 모든 노드를 방문할 수 없습니다.

 

재귀로 구현

DFS를 코드로 구현할 때, 보통 함수의 재귀를 이용합니다.

한 노드에서 시작해서 연결되어 있는 아직 방문하지 않은 다른 노드들을 방문하면서 재귀적으로 탐색합니다.

노드가 매우 많으면서 일렬로 연결되어 있는 그래프가 있다면, 처음 노드부터 방문하는 경우, 프로그래밍 언어에 따라 스택 오버플로우가 발생할 수 있습니다. 이런 경우 스택을 이용하여 구현하면 이를 방지할 수 있습니다.

스택으로 구현

노드들을 재귀적으로 방문하는 것이, 노드들을 방문하면서 발견한 노드를 스택에 쌓아놓고 가장 위의 노드를 꺼내 방문하는 방식과 같습니다.

따라서 DFS를 스택으로도 구현할 수 있습니다.

스택으로 구현할 경우 하나의 함수 내에서만 작동하기 때문에, 재귀를 이용할 때보다 함수 호출비용을 아낄 수 있습니다.