[c++] DFS(깊이 우선 탐색) / 개념 / 함수 구현

DFS(깊이 우선 탐색)

- 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

- 스택 또는 재귀함수로 구현

 

DFS: Stack(스택)

// DFS 구현 - 스택
// 답: 1, 2, 4, 6, 5, 7, 3
#include <stdio.h>
#include <vector>
#include <stack>

using namespace std;

// 인접행렬로 표현한 그래프
vector<vector<int>> adjacent =
{
	{ 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<bool> visited;

// dfs 함수
void dfs(int start)
{
	// 시작 노드 번호
	visited.at(start) = true; // 방문 표시
	stack<int> s; // 스택
	s.push(start); // 스택에 노드 넣기
	printf("%d ", start + 1); // 노드 번호 프린트

	// 스택에 노드가 남아있을 동안 반복
	while (!s.empty())
	{
		int here = s.top(); // 현재 검사중인 노드
		int i; // for문 밖에 선언
		for (i = 0; i < adjacent.size(); i++) // 인접행렬 탐색
		{
			// 현재 검사중인 노드와 연결되어있고, 방문하지 않은 노드
			if (adjacent.at(i).at(here) == 1 && visited.at(i) == false)
			{
				s.push(i); // 스택에 넣고
				visited.at(i) = true; // 방문했다고 표시하고
				printf("%d ", i + 1); // 프린트
				break;
			}
		}
		
		// 연결된 노드가 없거나 모두 방문한 경우
		if (i == adjacent.size()) {
			s.pop(); // 스택의 top노드 제거
		}
	}
}

// 모든 그래프를 탐색할 수 있도록 하는 함수
// 왜냐하면 모든 그래프가 서로 연결되어있는 것이 아니기 때문에
void dfsAll()
{
	visited.assign(adjacent.size(), false); // 방문 표시를 모두 false로 초기화
	for (int i = 0; i < adjacent.size(); i++) // 인접행렬로 모든 노드 체크
	{
		if (visited.at(i) == false) // 방문하지 않은 노드이면
		{
			dfs(i); // dfs 함수 호출
		}
	}
}

int main()
{
	dfsAll();

	return 0;
}

 

DFS: Recursive(재귀)

// DFS 구현 - 재귀
// 답: 1, 2, 4, 6, 5, 7, 3
#include <stdio.h>
#include <vector>

using namespace std;

// 인접행렬로 표현한 그래프
vector<vector<int>> adjacent =
{
	{ 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<bool> visited;

// dfs 함수
void dfs(int index)
{
	printf("%d ", index + 1); // 노드 번호 프린트
	visited.at(index) = true; // 노드 방문 표시

	for (int i = 0; i < adjacent.size(); i++) // 인접행렬 탐색
	{
		// 연결되어있고, 방문하지 않았다면
		if (adjacent.at(index).at(i) == 1 && visited.at(i) == false)
		{
			dfs(i); // dfs 함수 호출
		}
	}
}

// 모든 그래프를 탐색할 수 있도록 하는 함수
// 왜냐하면 모든 그래프가 서로 연결되어있는 것이 아니기 때문에
void dfsAll()
{
	visited.assign(adjacent.size(), false); // 방문 표시를 모두 false로 초기화
	for (int i = 0; i < adjacent.size(); i++) // 인접행렬로 모든 노드 체크
	{
		if (visited.at(i) == false) // 방문하지 않은 노드이면
		{
			dfs(i); // dfs 함수 호출
		}
	}
}

int main()
{
	dfsAll();

	return 0;
}

 

끝!