[자료구조] DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)

본 글은 <C++로 쉽게 풀어쓴 자료구조>를 참고하여 작성되었다.

 

그래프 탐색이란 하나의 정점에서 시작하여 모든 정점들을 한 번씩 방문하는 작업이다. DFS(depth first search, 깊이 우선 탐색)와 BFS(breadth first search, 너비 우선 탐색)는 그래프를 탐색하는 가장 고전적인 두 가지 방법이다.

이름에서 알 수 있듯이 깊이 우선 탐색은 한 방향으로 갈 수 있을 때까지 가다가 길이 끝나면 가장 가까운 갈림길로 되돌아와 다른 방향을 다시 탐색하는 방식이고, 너비 우선 탐색은 가장 가까운 정점들을 차례로 방문한 뒤 방문했던 정점들과 가장 가까운 정점들을 또다시 탐색하는 방식이다. 그림으로 한번 알아보자.

위와 같은 그래프에서 A를 시작 정점으로 깊이 우선 탐색을 한다면 순서는 이렇게 된다.

A B D H I E J C F G 순으로 탐색한다. 이 탐색 과정을 구현하기 위해서는 먼저 그래프를 순차적으로 방문할 수 있어야 하고, 방문한 노드들은 다시 탐색할 일이 없도록 방문 처리되어야 한다. DFS는 스택 또는 순환 알고리즘으로 나타낼 수 있는데, 스택으로 예시를 든다면 이렇게 된다.

1) 시작 정점 A를 스택에 넣고 방문 처리한다. A
2) 스택의 최상단 노드 A는 꺼내 출력하고, 그 인접 노드인 C, B를 스택에 넣고 방문처리한다.(위 그림과 같이 직관적인 순서로 나타내기 위해 알파벳 역순으로 스택에 삽입하였다.) C B
3) 스택의 최상단 노드인 B는 꺼내 출력하고, 그 인접 노드인 E, D를 스택에 넣고 방문처리한다. C E D
4) 스택의 최상단 노드인 D는 꺼내 출력하고, 그 인접 노드인 I, H를 스택에 넣고 방문처리한다. C E I H
5) 스택의 최상단 노드인 H는 꺼내 출력한다. 방문하지 않은 인접 노드가 없으므로 스택에는 아무것도 넣지 않는다. C E I
6) 위 과정을 스택에 아무것도 남지 않을 때까지 반복한다.

 

 

한편 너비 우선 탐색은 이렇게 된다.

A B C D E F G H I J 순으로 탐색한다. 역시 그래프를 순차적으로 방문할 수 있어야 하고, 방문한 노드들은 다시 탐색할 일이 없도록 방문 처리되어야 한다. DFS는 큐를 사용해 나타낼 수 있다. 마찬가지로 예시를 보자.

1) 시작 정점 A를 큐에 넣고 방문 처리한다. A
2) 큐에서 A를 꺼내고, 인접 노드 B, C를 큐에 삽입 후 방문 처리한다. B C
3) 큐에서 B를 꺼내고, 인접 노드 D, E를 큐에 삽입 후 방문 처리한다. C D E
4) 큐에서 C를 꺼내고, 인접 노드 F, G를 큐에 삽입 후 방문 처리한다. D E F G
5) 위 과정을 스택에 아무것도 남지 않을 때까지 반복한다.

 

 

코드로 살펴보면 이렇게 된다.

시작 노드 v 방문 표시;
큐/스택에 v 삽입;
while (큐/스택 is not empty()) {
   큐/스택에서 정점 x 삭제;
   for(정점 x의 인접한 모든 정점 u)
       u가 아직 방문되지 않았다면 큐/스택에 삽입 및 방문 표시;
}

#include <iostream>
#include <queue>
#include <vector>
#include <list>
#include <stack>
using namespace std;

class Node {
private:
	int key;
public:
	Node(int key): key(key) {}
	int getKey() { return key; }
};

class Graph {
private:
	vector<int> vertices;
	vector<bool> visited;
	vector<list<Node>> adj;		// 인접 리스트
public:
	Graph(int numOfVertices) {
		for (int i = 1; i <= numOfVertices; i++)
			vertices.push_back(i);
		for(int i=0; i<=numOfVertices; i++)
			visited.push_back(false);
			
		adj.resize(numOfVertices+1);
		adj[0].push_back(Node(-1));		// 0번 인덱스 사용 X
	}

	void insertUndirectEdge(int u, int v) {
		adj[u].push_back(Node(v));
		adj[v].push_back(Node(u));
	}

	void BFS(int start) {
		queue<int> queue;
		queue.push(start);
		visited[start] = true;

		cout << "BFS" << endl;
		while (!queue.empty()) {
			int v = queue.front();
			queue.pop();

			list<Node>::iterator iter;
			for (iter = adj[v].begin(); iter != adj[v].end(); ++iter) {
				if (visited[iter->getKey()] == false) {
					queue.push(iter->getKey());
					visited[iter->getKey()] = true;
				}
			}
			cout << v << " ";
		}
	}

	void DFS(int start) {		// start: 시작 노드
		stack<int> stack;
		stack.push(start);
		visited[start] = true;

		cout << "DFS" << endl;
		while (!stack.empty()) {
			int v = stack.top();
			stack.pop();

			list<Node>::iterator iter;
			for (iter = adj[v].begin(); iter != adj[v].end(); ++iter) {
				if (visited[iter->getKey()] == false) {		// 방문하지 않은 노드라면 push
					stack.push(iter->getKey());
					visited[iter->getKey()] = true;
				}
			}
			cout << v << " ";
		}
	}
};


int main() {
	Graph graph(8);
	graph.insertUndirectEdge(1, 2);
	graph.insertUndirectEdge(1, 3);
	graph.insertUndirectEdge(2, 4);
	graph.insertUndirectEdge(3, 4);
	graph.insertUndirectEdge(3, 5);
	graph.insertUndirectEdge(4, 6);
	graph.insertUndirectEdge(5, 7);
	graph.insertUndirectEdge(5, 8);
	graph.insertUndirectEdge(7, 8);

	graph.BFS(1);
	cout << endl;

	return 0;
}

 

 

위와 같은 그래프의 결과는 이렇게 된다.