깊이 우선 탐색 (DFS)

깊이 우선 탐색 (Depth First Search : DFS)은 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘 중 하나이다. 현재 정점과 인접한 간선들을 검사하다가 방문하지 않은 정점을 발견하면 그 간선을 통해 방문하지 않은 정점으로 이동하는 것이다.

 

이 과정을 반복하다가 더 이상 방문할 수 있는 정점이 없는 경우 마지막으로 통과한 간선을 통해 뒤로 돌아가서 해당 정점에서 방문할 수 있는 정점을 탐색한다. 그림을 통해 한번 살펴보자.

 

 

위 그림의 그래프가 존재하고 한 정점에서 여러 개의 정점으로 이동이 가능할 때 정점의 번호가 더 작은 쪽을 먼저 방문한다고 가정하자. 우선, 정점 1에서 깊이 우선 탐색을 한다고 하자.

 

먼저, 정점 1에서 연결된 간선들을 통해 연결된 정점을 확인하면 2, 3, 7이 있다. 이때, 위와 같은 규칙에 의해 2번으로 이동하게 된다. 2번 정점에서 또 규칙에 의해 3번으로 이동한다. 이와 같은 식으로 이동하다보면 1 - 2 - 3 - 5 - 7- 6 - 4 순으로 방문한다.

 

마지막 방문 정점이 4에서는 3을 방문 할 수 있지만 이미 방문 했으므로 이동할 수 없다. 4번에서 더이상 이동할 수 있는 정점이 없으므로 6번으로 돌아간다. 6번에서도 5번으로 이동할 수 있지만, 이미 방문된 정점이므로 7번으로 돌아간다. 이렇게 계속 돌아가다보면 1번 정점으로 돌아가게 된다. 이렇게 모든 정점에서 방문이 있었으므로 깊이 우선 탐색은 종료하게 된다.

 

깊이 우선 탐색의 시간 복잡도는 정점의 개수(Vertex)를 V, 간선의 개수(Edge)를 E라고 했을때  인접 리스트 방식이면, O(V+E)이고 인접 행렬 방식이면 O(V^2)이다. 

---

구현

위 그래프 정보를 바탕으로 깊이 탐색을 구현해보자. 구현 방법은 두가지가 있다.

 

재귀함수를 이용한 DFS구현

#include <iostream>
#include <vector>
#include <algorithm>

#define VISITED 1
#define UNVISITED 0
#define CONNECTED 1

using namespace std;

// 인접행렬로 표현한 간선
vector<vector<int>> edge =
{
	{0, 1, 1, 0, 0, 0, 0},
	{1, 0, 0, 1, 1, 0, 0},
	{1, 0, 0, 0, 0, 0, 1},
	{0, 1, 0, 0, 0, 1, 0},
	{0, 1, 0, 0, 0, 1, 0},
	{0, 0, 0, 1, 1, 0, 1},
	{0, 0, 1, 0, 0, 1, 0}
};

vector<int> vertices;

void DFS(int index)
{
	// 정점에 방문 표시를 한다.
	vertices[index] = VISITED;

	// 해당 정점의 간선에서
	for (size_t i = 0; i < edge.size(); ++i)
	{
    	// 정점과 연결되어 있고 방문한 적이 없다면
		if (CONNECTED == edge[index][i] &&
			UNVISITED == vertices[i])
		{
        	// 재귀 함수를 호출한다.
			cout << i + 1 << " ";
			DFS(i);
		}
	}
}

int main()
{
	// 정점정보 초기화
	vertices = vector<int>(edge.size(), UNVISITED);

	// 모든 정점이 방문상태여야 깊이 우선 탐색이 종료되므로
    // 모든 정점을 깊이 우선 탐색한다.
	for (size_t i = 0; i < edge.size(); ++i)
	{
		if (UNVISITED == vertices[i])
		{
			cout << i + 1 << " ";
			DFS(i);
		}
	}

	cout << endl;
}

 

스택을 이용한 DFS 구현

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>

#define VISITED 1
#define UNVISITED 0
#define CONNECTED 1

using namespace std;

vector<vector<int>> edge =
{
	{0, 1, 1, 0, 0, 0, 0},
	{1, 0, 0, 1, 1, 0, 0},
	{1, 0, 0, 0, 0, 0, 1},
	{0, 1, 0, 0, 0, 1, 0},
	{0, 1, 0, 0, 0, 1, 0},
	{0, 0, 0, 1, 1, 0, 1},
	{0, 0, 1, 0, 0, 1, 0}
};

vector<int> vertices;

void DFS(int index)
{
	vertices[index] = VISITED;
	stack<int> s;
	// 처음 방문한 정점을 스택에 push한다.
	s.push(index);
	cout << index + 1 << " ";

	// 스택이 빌때까지
	while (false == s.empty())
	{
		// 스택의 top에서 부터
		int target_vertex = s.top();
		bool exist_subdepth = false;

		for (size_t i = 0; i < edge.size(); ++i)
		{
			// 정점과 연결되어 있고 방문한 적이 없다면
			if (CONNECTED == edge[i][target_vertex] &&
				UNVISITED == vertices[i])
			{
				// 스택에 push한다.
				cout << i + 1 << " ";
				s.push(i);

				// 정점에 방문 표시를 한다.
				vertices[i] = VISITED;
				exist_subdepth = true;

				break;
			}
		}

		// 해당 정점이 더이상 연결된 어느 정점과도 방문할 수 없으므로 
		// 이전 단계로 되돌아 간다.
		if (false == exist_subdepth)
			s.pop();
	}
}

int main()
{
	vertices = vector<int>(edge.size(), UNVISITED);

	for (size_t i = 0; i < edge.size(); ++i)
	{
		if (UNVISITED == vertices[i])
		{
			DFS(i);
		}
	}

	cout << endl;
}

 

출력 값

1 2 4 6 5 7 3