DFS - 깊이 우선 탐색

DFS (Depth First Search)는 깊이 우선 탐색으로 루트 노드를 시작으로 해당 노드에서 갈 수 있는 분기들을 완벽하게 탐색한 후에 다음 분기로 넘어가는 탐색 방법이다. 탐색 가능한 끝까지 검색을 하기 때문에 이 탐색에 대한 구현은 재귀적 표현을 통해서 보통 구현된다.

 

탐색을 하기전, 탐색할 그래프를 만들어보자.

struct Vertex
{
	// int data;
};

vector<Vertex> vertices;
vector<vector<int>> adjacent;
vector<bool> visited;

void CreateGraph()
{
	vertices.resize(6);
	adjacent = vector<vector<int>>(6);

	// 인접 리스트
	adjacent[0].push_back(1); // '0' 노드에서 '1'로 가는 간선이 존재
	adjacent[0].push_back(3);
	adjacent[1].push_back(0);
	adjacent[1].push_back(2);
	adjacent[1].push_back(3);
	adjacent[3].push_back(4);
	adjacent[5].push_back(4);
}

 

 

 만약, 노드끼리의 서로 간선이 많지 않다면 연결된 간선들에 대한 정보를 담은 동적 배열을 이용하여 간선들 간의 정보를 담을 것이다. 하지만 노드들끼리의 간선이 많다면 각 노드들이 연결된 간선들에 대한 검색이 느릴수 있다. 그런 경우에는

void CreateGraph()
{
	vertices.resize(6);
	adjacent = vector<vector<int>>(6);

	// 인접 행렬'	
	adjacent = vector<vector<int>>
	{
		{0,1,0,1,0,0},
		{1,0,1,1,0,0},
		{0,0,0,0,0,0},
		{0,0,0,0,1,0},
		{0,0,0,0,0,0},
		{0,0,0,0,1,0},
	};

}

 이런 식으로 나타낸다면 가지고 있지 않은 간선에 대한 정보도 포함하므로 메모리에 대한 손해가 생기지만, 검색에 대한 속도가 빨라지므로 간선이 많다면 위와 같은 표현도 좋을 수 있을 것이다.

 

 이런 식으로 그래프와 그래프에 존재하는 노드들의 간선을 연결하였다면 본격적으로 DFS를 하기 위한 준비를 해보자.

 우선, 반복적으로 같은 노드에 대해 접근하지 않도록 존재하는 모든 노드에 대한 방문 여부를 묻는 배열을 하나 준비한다.

vector<bool> visited;

 이후, 루트 노드부터 시작하여 재귀적으로 다음 노드들을 검색해 나가면 DFS에 대한 구현은 끝이다.

void Dfs(int here)
{
	// [방문]
	visited[here] = true;

	cout << "Visited : " << here << endl;

	for (int there = 0; there < 6; there++)
	{
		// 연결되지 않은 간선은 무시한다
		if (adjacent[here][there] == 0)
			continue;

		// 아직 방문하지 않은 곳이 있으면 방문한다.
		if (visited[there] == false)
			Dfs(there);
	}
}

구현 자체는 생각보다 어렵지 않지만 처음 이해하기 어려운 부분이 있으므로 여러번 반복하여 공부하면 좋을 것 같다.

 

이상으로  DFS에 대한 설명을 마치도록 하겠습니다. 포바~!