bfs와 dfs 구현해보기

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;

vector<int> a[1001];    // 2차원 동적배열
bool check[1001]; // 방문 플래그

void dfs(int node) {
	check[node] = true;
	for (int i = 0; i < a[node].size(); i++) {
    	int next = a[node][i];
		if (check[next] == false) {
			dfs(next);
		}
	}
}

void bfs(int start) {
	memset(check, false, sizeof(check)); // dfs를 수행한 후이기 때문에 초기화.
	check[start] = true;
	queue<int> q;
	q.push(start);
	while(!q.empty()){
		int node = q.front();
		q.pop();
		for (int i = 0; i < a[node].size(); i++) {
        	int next = a[node][i];
			if (check[next] == false) {
				q.push(next);
				check[next] = true;
			}
		}
	}
}

int main() {
	int n, m, start;
	cin >> n >> m >> start;
	for (int i = 0; i < m; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		a[u].push_back(v); a[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) {
		sort(a[i].begin(), a[i].end());
	}
	dfs(start);
	cout << endl;
	bfs(start);
	cout << endl;
	return 0;
}

알고리즘을 하며 모를수가 없는 dfs(depth first search)와 bfs(breadth-first search).

 

위에는 기본적인 dfs와 bfs의 뼈대 코드를 구현한 소스이다.

 

간선들을 저장하는데에는 여러가지 방법이 쓰일 수 있지만 위에서는 vector를 이용한 2차원 배열로 그래프를 저장하였다.

 

위에서의 dfs는 재귀호출을 통한 구현이다. 필자는 재귀호출이 가장 코드가 간단하다고 생각된다.

   

    dfs는 기본적으로 stack 자료구조를 사용하게 된다.

    정점에 방문할 때마다 stack에 정점을 넣고, 더이상 탐색이 불가할 때 stack으로부터 꺼내며 가장최근의 정점으로부터 탐색을 다시 시작하는 것이다.

    기본적으로 c++에서 함수의 호출이 stack 방식을 택하기 때문에 재귀호출을 이용한 구현을 한 방식이 가장 간단한 코드를 작성할 수 있게 된다.

 

    코드를 들여다보면,  첫 번째로 함수의 맨 처음에 정점방문을 체크해주는 것을 잊지 않아야 한다.

    그리고 다음에는 for문이 오는데, 이 for문 안에 dfs()를 다시 호출하여 stack에 넣는거라고 보면 된다.

    물론 정점방문은 check배열을 이용하여 방문한 적이 없는 곳만 방문한다.

    그 외에는 별 것이 없으며 신기할 정도로 코드가 간단하다.

 

 

   bfs는 코드가 좀 더 복잡하다.

일단 "queue" 자료구조를 사용하여 구현하는 방식이다.

또 bfs의 특징은 코드블록 안에 이중 반복문이 있다는 점이다.

 

    첫 번째 반복문은 while문인데, queue가 빌 때까지 반복하는 구조이다.

    두 번째 반복문은 for문으로, 한 정점에서 방문할 수 있는 모든 정점을 방문하는 코드이다. 이 때 정점들을 방문할 때마다 queue에 넣어준다. 여기에서 너비우선 탐색의 특징을 볼 수가 있다.

    한 정점에서의 모든 방문이 끝나면 while문이 반복되는데, 여기서 중요한 것은, queue의 제일 오래된 값을 변수에 저장한 뒤, pop, 꺼내서 지워버리는 것이다.

    그러고 나면 이 정점에서 탐색을 또 시작하고, while문이 반복되고 이런 식이다.

    queue가 빌 때까지 탐색을 마치면, 모든 정점에서의 탐색을 마친 것이다.