그래프 탐색 알고리즘 (DFS, BFS)

이 포스트를 이해하기 위해 필요한 사전지식 : 
C++(혹은 C), 그래프 이론, 큐(자료구조)

 

 

그래프의 노드(Node)를 모두 탐색하는 방법으로 크게 DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 두 가지가 있다.

다음과 같은 그래프가 있다고 하자.

 

8개의 노드와 7개의 간선으로 이루어진 양방향 그래프이다.

어디에서 시작하든 상관은 없지만 시각적 편리함을 위해 예시에서는 데이터 2가 저장된 노드에서 시작하기로 한다.

 

 

 

 

 

 

DFS (깊이 우선 탐색)

Depth First Search의 약자이며 말 그대로 깊이 갈 수 있는 곳까지 탐색하는 알고리즘.

각 노드에 연결된 노드들 중 아직 탐색하지 않은 노드들 중 아무거나 골라서 그 노드로 넘어가는 알고리즘이다.

 

위의 예시에서는 2에서 시작했으므로 2에 연결된 7, 4, 11 중 하나를 고르는데, 7을 골랐다고 하면 

7에서 연결된 노드들을 살펴보는데 아직 방문(탐색)되지 않았으면서 연결된 노드가 3밖에 없으므로 3으로 넘어가고 같은 방법으로 9를 탐색한다.

9에 도달했는데 9에 연결된 노드(여기서는 3밖에 없다)들은 모두 방문된 상태이다.

따라서 이전의 노드로 돌아가는데 3도 9와 마찬가지로 연결된 노드들(7, 9)가 모두 방문 되었으므로 7로 돌아가고 7도 역시 연결된 노드들(2, 3)이 모두 방문되었으므로 이전 노드인 2로 돌아오게 된다.

 

2로 돌아와 보니 연결된 노드들(7, 4, 11) 중 7을 제외한 노드들은 아직 방문된 상태가 아니므로 4, 11 중 하나를 선택해서 방문한다. 여기서는 4를 선택했다고 하자. 4를 방문하고 더이상 연결 되어있는 노드들 중 미방문인 노드가 없으므로 이전노드인 2로 돌아간다. 

 

다시 2로 돌아왔지만 아직 방문하지 않은 11이라는 노드가 남아있다. 11로 이동하여 같은 방법으로 1, 8을 탐색하고 돌아와서 2로 되돌아왔지만, 이제 더 이상 방문할 노드가 남아있지 않다.

이로써 탐색이 끝난것이다.

 

 

 

 

 

 

 

 

 

 

 

BFS (너비 우선 탐색)

Breadth First Search. 깊게 들어갈 수 있으면 최대한 깊게 먼저 탐색했던 DFS와는 달리 BFS는 그 노드와 같은 층(level)의  노드들을 모두 탐색한 후 다음 깊이로 넘어가는 알고리즘이다.

 

2에서 연결된 노드들 7, 4, 11을 모두 먼저 탐색 한 후 7, 4, 11 과 연결된 노드들 중 미방문인 노드들(3, 1, 8)을 탐색하고 3, 1, 8과 연결된 노드들 중 미방문인 노드(9)를 마지막으로 탐색하고 9에서 더 이상 연결되어있고 방문되지 않은 노드들이 없으므로 탐색이 종료된다.

 

 

 

 

 

 

 

 

 

코드로 표현하기 (C++) 

 

DFS

#define CONNECTED 1
#define UNCONNECTED 0
#define VISITED 1
#define UNVISITED 0
#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> graph(100); // 크기가 신축적인 배열을 100개 선언함
int visited[100]; // 그 노드가 방문되었는지 체크하는 용도의 배열

void dfs(int node_now) {
	visited[node_now] = VISITED;
	cout << node_now << " "; // 현재 방문한 노드의 번호를 출력함

	for (int i = 0; i < graph[node_now].size(); i++) {
		int next = graph[node_now][i];
		if (visited[next] != VISITED) {
			dfs(next);
		}
	}
}

int main() {
	
	int number_of_nodes, number_of_edges;
	cin >> number_of_nodes >> number_of_edges; // 노드의 갯수와 간선의 갯수를 입력받음

	for (int i = 0; i < number_of_edges; i++) {
		int node_A, node_B; // 연결할 두 노드
		cin >> node_A >> node_B;

		graph[node_A].push_back(node_B);
		graph[node_B].push_back(node_A); // 양방향이므로 A에서 B로 가는 길 뿐만 아니라 B에서 A로 가는 길도 연결 해주어야 한다
	}
	dfs(2);

	return 0;
}

vector가 무엇인지 모른다면 vector stl부터 찾아보고 오는걸 권장함

 

dfs는 stack 자료구조로 구현할 수 있는데 코드길이와 가독성 문제로 일반적으로는 재귀로 구현을 한다.

vector<vector<int>> graph(100)는 길이가 가변적인 배열을 100개 미리 선언해 놓았다는 의미이다.

이걸로 그래프를 어떻게 표현할 수 있을까?

 

위의 예시 그래프를 이용해 설명을 하겠다.

첫 줄에 노드의 갯수(8)과 간선의 갯수(7)을 입력을 하고

그 다음 7줄의 입력으로는 간선들의 연결 정보를 입력한다.

예를들어 2 11을 입력하면 2와 11이 양방향으로 연결되어 있다는 의미이다.

2와 11을 입력하면 graph[2]에 11의 값을 push 하고 graph[11]에도 2를 push하게 된다.

이 입력과정을 마치면 graph에는 다음과 같이 모든 그래프의 연결상태가 저장되게 된다.

 

vector<vector<int>> graph(100)이라고 선언했으므로 아래로 graph[99]까지 존재하게 된다.

가령 graph[2]를 보면 7 4 11이 저장되어 있는데 이것은 2번 노드가 7, 4, 11이랑 연결 되어 있다는 뜻이 된다.

 

이제 dfs함수를 살펴보자.

node_now번 노드를 이제 방문할 예정이므로 visited[node_now]의 값을 VISITED (1이라고 define 됨)으로 바꾸어 주고

graph[now_node]에 들어있는 모든 노드들에 대해 방문하지 않았다면 곧바로 재귀로 dfs를 부름으로써 다음 노드로 이동하게 된다.

 

2번 노드부터 시작하므로 visited[2] = 1이 되고, graph[2]의 값들 7, 4, 11중 7부터 선택해 7번 노드에 대해 dfs함수가 다시 불러져 같은 행위를 반복하는 방식이다. 즉 탐색의 깊이를 재귀의 깊이로 표현한 꼴인 것이다.

 

DFS 방식으로 탐색하면 2 7 3 9 4 11 1 8 순서로 방문됨을 알 수 있다. (같은 그래프라도 vector에 저장되는 순서에 따라 조금 차이가 있을 수 있음)

 

 

 

 

 

 

 

BFS

#define CONNECTED 1
#define UNCONNECTED 0
#define VISITED 1
#define UNVISITED 0
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<vector<int>> graph(100); // 크기가 신축적인 배열을 100개 선언함
int visited[100]; // 그 노드가 방문되었는지 체크하는 용도의 배열

void bfs(int begin_node) { // DFS와는 달리 재귀방식이 아니다.
	queue<int> node_que; // 노드들을 관리할 큐를 생성
	visited[begin_node] = VISITED; // 방문처리 해주고
	node_que.push(begin_node); // 첫번째 노드를 일단 push 함

	while (!node_que.empty()) { // 큐가 모두 빌때까지 반복함
		int now = node_que.front(); // 현재 큐의 맨 앞을 뽑아서 탐색대상으로 설정
		visited[now] = VISITED; // 역시 방문 체크 해주고
		cout << now << " "; // 노드 번호 출력
		node_que.pop();

		for (int i = 0; i < graph[now].size(); i++) { 
			// 그 탐색대상의 노드에 연결되어 있고 아직 방문하지 않은 노드들을 모두 큐에 넣음
			int next = graph[now][i];

			if (visited[next] != VISITED)
				node_que.push(next);
		}
	}
	return;
}

int main() {
	
	int number_of_nodes, number_of_edges;
	cin >> number_of_nodes >> number_of_edges; // 노드의 갯수와 간선의 갯수를 입력받음

	for (int i = 0; i < number_of_edges; i++) {
		int node_A, node_B; // 연결할 두 노드
		cin >> node_A >> node_B;

		graph[node_A].push_back(node_B);
		graph[node_B].push_back(node_A); // 양방향이므로 A에서 B로 가는 길 뿐만 아니라 B에서 A로 가는 길도 연결 해주어야 한다
	}
	bfs(2);

	return 0;
}

BFS를 구현하기 위해 queue를 include 했다.

큐 자료구조를 모른다면 큐(queue)자료구조와 queue stl을 먼저 보고 오는것을 추천함.

 

dfs와는 달리 bfs는 재귀함수가 아니다.

어떤 노드를 방문할 때마다 그 노드에 연결되어있고 방문하지 않은 노드들을 모두 큐에 넣는 다음

그 큐의 맨 앞의 노드를 방문하여 같은 행위를 반복하며

큐가 비어서 더이상 뽑을 노드가 없을 때까지 반복하는 방식이다.

while문의 조건을 위해 방문하는 첫 노드는 그 노드만 큐에 넣어주고 그 다음 노드부터는 현재 노드와 연결된 노드들을 큐에 넣는다.

 

역시 vector에 저장한 순서에 따라 출력이 조금 달라질 수는 있다. 다만 처음에 정렬해서 넣었다면 항상 같은 결과값이 나온다.

 

 

 

프로그래밍 문제

실제로 구현해서 풀어보자.

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

vector<int> graph[1001];
vector<int> check(1001);
queue<int> q;

void dfs(int n) {
	check[n] = 1;
	cout << n << " ";
	for (int i = 0; i < graph[n].size(); i++) {
		int next = graph[n][i];
		if (!check[next]) {
			check[next] = 1;
			dfs(next);
		}
	}
}

void bfs(int begin) {
	check[begin] = 1;
	q.push(begin);
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		cout << now << " ";
		for (int i = 0; i < graph[now].size(); i++) {
			int next = graph[now][i];
			if (!check[next]) {
				check[next] = 1;
				q.push(next);
			}
		}
	}
}

int main() {
	int n, m, s;
	cin >> n >> m >> s;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	for (int i = 0; i < n; i++) {
		sort(graph[i].begin(), graph[i].end());
	}
	dfs(s);
	fill(check.begin(), check.end(), 0);
	cout << endl;
	bfs(s);

	return 0;
}