[c++/그래프] DFS (깊이 우선 탐색)

깊이 우선 탐색이란

1. 인접한 정점 중 하나 선택

2. 인접한 정점으로 이동

3. 더이상 이동할 정점이 없을 경우 백트래킹

그래프의 모든 정점을 탐색할 때까지 위의 과정을 반복한다.

​

시작 정점으로부터 거리가 멀어지는(깊이가 깊어지는) 방식으로 정점 탐색

​

보통 재귀, 스택을 이용하여 구현한다.

​

bool isVisited[N] = { };

-> 정점 방문 여부 검사

-> 정점 방문 여부를 검사하지 않으면 무한 루프에 빠질 수 있다.

<재귀 이용 방법>

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 6;	//정점 6개
bool gVisited[N] = {};	//정점 방문 했는지 확인

void dfs_recursion(const vector<vector<int>> &adj_list, int s) {
	//만약 이미 방문했으면 pass (true면 방문한 것)
	if (gVisited[s])
		return;
	gVisited[s] = true;
	cout << s << ", ";	//이 자리에 필요한 코드 작성

	//s와 인접한 모든 노드에 대해 dfs_recursion() 함수 재귀 호출
	for (int v : adj_list[s])
		dfs_recursion(adj_list, v);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	vector<vector<int>> adj_list = { {1,3,4},{0,2,4},{1,5},{0,4},{0,1,3},{2} };

	dfs_recursion(adj_list, 0);
	cout << endl;
}
//0, 1, 2, 5, 4, 3,

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> map[101];
bool visited[101] = { false };
int ans = 0;

int dfs(int n) {
	for (int i = 0; i < map[n].size(); i++) {
		int k = map[n][i];

		if (visited[k] == false) {
			visited[k] = true;
			ans++;
			dfs(k);
		}
	}
	return 0;
}

int main() {
	int t, n;
	cin >> t >> n;

	//인접 리스트 만드는 과정? ㅇㅇ 마쟈 
	//map 벡터 2차원으로 만듬..짱신기
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;

		map[b].push_back(a);
		map[a].push_back(b);
	}

	visited[1] = true;
	dfs(1);

	for (int i = 0; i < map[1].size(); i++) {
		cout << map[1][i] << endl;
	}
	cout << ans;
}

<스택 이용 방법>

#include <string>
#include <vector>
#include <iostream>
#include <stack>
using namespace std;

vector<int> dfs(const vector<vector<int>>& adj_list, int s) {
	vector<bool> visited(adj_list.size(), false);	//정점의 개수 모두 false
	vector<int> visited_order;	//방문 순서
	stack<int> stk;
	stk.push(s);

	while (!stk.empty()) {
		int v = stk.top();
		stk.pop();

		if (visited[v]) continue;	//이미 방문한 정점이면 패스

		visited[v] = true;
		visited_order.push_back(v);

		for (int a : adj_list[v]) {
			if (!visited[a])
				stk.push(a);
		}
	}
	return visited_order;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	vector<vector<int>> adj_list = { {1,3,4},{0,2,4},{1,5},{0,4},{0,1,3},{2} };

	dfs(adj_list, 0);
	cout << endl;
}// 0 4 3 1 2 5

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

vector<int> map[101];
bool visited[101];

int main() {
	int t, n;
	cin >> t >> n;

	//인접 리스트 만드는 과정? ㅇㅇ 마쟈 
	//map 벡터 2차원으로 만듬..짱신기
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;

		map[b].push_back(a);
		map[a].push_back(b);
	}

	stack<int> stk;
	stk.push(1);
	visited[1] = true;

	while (!stk.empty()) {
		int v = stk.top();
		stk.pop();

		for (int i = 0; i < map[v].size(); i++) {
			if (visited[map[v][i]])
				continue;
			visited[map[v][i]] = true;

			stk.push(map[v][i]);
		}
	}
	int ans = 0;
	for (int i = 2; i <= t; i++) {
		if (visited[i])
			ans++;
	}
	cout << ans;
	return 0;
}