2-2. DFS - 깊이 우선 탐색

1. DFS(Depth First Search) ; 깊이 우선 탐색

깊이를 우선으로 탐색하는 알고리즘.

struct Vertex
{

};

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);
	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);
}

위의 그래프 사진과 같이 정점들과 연결 상태를 만들어 준다.

그리고 이미 방문한 정점인지 채크하는 visited boolean벡터를 만들어준다.

int main()
{
	CreateGraph();

	visited = vector<bool>(6, false);

	Dfs(0);

}

 

(1) 인접 리스트 방법

해당 정점을 방문했는지 배열로 관리한다.

모든 인접한 정점들을 순회한다. 재귀 함수를 이용한다.

void Dfs(int here)
{	// 방문했음을 체크
	visited[here] = true;

	// 인접한 모든 길을 방문
	for (int i = 0; i < adjacent[here].size(); i++)
	{	// 목적지
		int there = adjacent[here][i];
		if (visited[there] == false)
			Dfs(there);
	}

}

또한 아래 함수를 통해서 방문하지 않은 탐색 정점(연결되지 않아 떨어져 있는 정점)도 탐색을 실시한다.

void DfsAll()
{
	for (int i = 0; i < 6; i++)
	{
		if (visited[i] == false)
			Dfs(i);
	}
}

 

(2) 인접 행렬 방법

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},
	};

}

void Dfs(int here)
{	// 방문했음을 체크
	visited[here] = true;

	for (int there = 0; there < 6; there++)
	{
		if (adjacent[here][there] == 0)
			continue;

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

}