깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS) 구현

먼저 깊이 우선 탐색은 노드에서 진행할 수 있는 최대 지점까지 진행하고 되돌아오면서 옆으로 넘어가는 방식이다.

 

아래의 예시에서는 인접리스트로 그래프를 표현했고, 0번 노드에는 1, 3번 노드가 연결되어있다.

1번에는 2, 4번 노드가, 그리고 2번과 4번 노드는 5번과 연결되어있다. 

#include <iostream>
#include <vector>
using namespace std;
const int N = 6;

// 인접리스트
vector<int> adj[N];

//깊이 우선 탐색
bool visited[N];
void dfs(int s) {
	if (visited[s]) return;
	visited[s] = true;
	cout << s << ' ';
	for (auto u : adj[s]) {
		dfs(u);
	}
}


int main() {

	adj[0].push_back(1);
	adj[0].push_back(3);

	adj[1].push_back(2);
	adj[1].push_back(4);

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

	dfs(0);
}

방문을 기록할 배열을 선언하고, 간단한 재귀 방식으로 구현할 수 있다.

숫자를 출력하는 부분 대신 노드 방문 시 처리할 동작을 입력하면 된다.

 

실행결과 : 

---

너비 우선 탐색은 시작 노드에서 가까운 노드부터 차례로 방문하는 방식이다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N = 6;

// 인접리스트
vector<int> adj[N];

queue<int> q;
bool visited2[N];
int dist[N];

int main() {

	adj[0].push_back(1);
	adj[0].push_back(3);

	adj[1].push_back(2);
	adj[1].push_back(4);

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


	// 0번 노드에서 시작
	visited2[0] = true;
	dist[0] = 0;
	q.push(0);
	while (!q.empty()) {
		int s = q.front(); q.pop();
		cout << s << ' ';
		for (auto u : adj[s]) {
			if (visited2[u]) continue;
			visited2[u] = true;
			dist[u] = dist[s] + 1;
			q.push(u);
		}
	}
}

아까와 같은 그래프를 가지고, BFS 방식으로 탐색하는 코드이다.

이번에도 방문 기록에 대한 배열이 필요하고, 추가로 방문 순서를 정할 Queue가 필요하다. 뒤에서 부터 다음 방문 노드를 추가하고, 앞에 있는 노드부터 처리한다. 

 

또한 시작노드 사이의 거리를 기록하기위해 dist 배열을 추가하였다.

 

실행결과: