깊이우선탐색 (DFS)

스택을 사용할 수 있지만 재귀 또한 스택의 특성을 가지고 있으므로 더 빠른 프로그래밍을 위해 재귀를 사용하였다.

 

코드는 아래의 그래프를 참고하여 구현하였다.

 

 

 

#include <iostream>
#include <vector>

using namespace std;

int n;
int flag[8];
vector<int> dfs[8];

void dfs_search(int start) {
	if (flag[start]) return;
	flag[start] = true;
	printf("%d ", start);
	for (int i = 0; i < dfs[start].size(); i++) {
		int x = dfs[start][i];
		dfs_search(x);
	}
}


int main() {
	dfs[1].push_back(2);
	dfs[1].push_back(3);

	dfs[2].push_back(3);
	dfs[2].push_back(4);
	dfs[2].push_back(5);

	dfs[3].push_back(6);
	dfs[3].push_back(7);
	dfs[3].push_back(1);
	dfs[3].push_back(2);

	dfs[4].push_back(2);
	dfs[4].push_back(5);

	dfs[5].push_back(2);
	dfs[5].push_back(4);

	dfs[6].push_back(3);
	dfs[6].push_back(7);

	dfs[7].push_back(6);
	dfs[7].push_back(3);

	dfs_search(1);

}