[알고리즘] 탐색 - DFS(C++)

DFS : stack 또는 recursion 사용하여 구현

주의할 점 - 그래프가 여러개 일 수 있으므로 모든 정점에 대해 dfs 수행하기!! 

 

 

DFS를 적용할 그래프

 

1 -> 2  -> 5 -> 6 -> 3 -> 7 -> 4

 

<Recursion>

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

vector<vector<int>> edge; // 간선들을 저장하는 vector
vector<bool> check; // 노드 방문 여부 check
int N, M, start; // 노드 개수, 간선 개수, 시작점
int u, v; // 간선 u -> v 연결

void dfs(int start) {
	check[start] = true; // start로 들어온 노드 방문 표시
	cout << start << ' ';
	for (int i = 0; i < edge[start].size(); i++) {
		int next = edge[start][i];
		if (check[next]) continue; // 이미 방문한 노드면 continue
		dfs(next); // 다음 노드로 dfs 수행
	}
}

int main() {
	cin >> N >> M >> start;
	edge.resize(N + 1);
	check.resize(N + 1);
    
	for (int i = 0; i < M; i++) {
		cin >> u >> v;
		edge[u].push_back(v);
	}
  
    	for(int i=1; i<=N; i++){
		sort(edge[i].begin(), edge[i].end()); // node값에 순차적으로 접근하기 위한 sorting
	}
    
	dfs(start);
}

Sample Input	Sample output
8 11 1 1 3 1 4 1 6 2 8 2 4 3 4 5 6 6 2 7 6 8 7  8 5	1 3 4 6 2 8 7 5

 

<stack>

1. stack의 top에 있는 노드를 기준으로 간선이 연결 되어 있으며, 아직 방문하지 않은 노드 찾기

2. 해당 노드를 stack에 넣은 후 break 걸기

3. 연결된 간선이 없으며, 방문하지 않은 노드를 찾지 못하면 pop.

 

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

// 인접리스트, 스택으로 구현
void dfs(int start, vector<vector<int>> graph, vector<bool> check) {
	stack<int> s;
	int current_node, next_node;
	s.push(start);
	check[start] = true;
	printf("%d ", start);

	while (!s.empty()) { // stack이 비어 있을 때까지 반복
		current_node = s.top();
		s.pop();
		for (int i = 0; i < graph[current_node].size(); i++) {
			next_node = graph[current_node][i];
			if (!check[next_node]) { // 아직 방문하지 않은 노드라면..
				printf("%d ", next_node);
				check[next_node] = true; // 방문 완료 표시
				s.push(current_node);
				s.push(next_node);
				break; // dfs를 진행하기 위함
			}
		}
	}
}

int main() {
	int N, M, start;
	int u, v;
	vector<vector<int>> graph;
	vector<bool> check;

	cin >> N >> M >> start;
	
	graph.resize(N + 1);
	check.resize(N + 1);

	for (int i = 0; i < M; i++) {
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	for (int i = 1; i <= N; i++) {
		sort(graph[i].begin(), graph[i].end());
	}

	dfs(start, graph, check);

	return 0;
}

Sample Input	Sample Output
5 5 3 5 4 5 2 1 2 3 4 3 1	3 1 2 5 4

참고 블로그 : https://twpower.github.io/73-how-to-implement-dfs-and-bfs-in-cpp