06 - 1. 그래프 순회, 탐색 (DFS, BFS)

 

그래프는 범용적인 특징을 가지고 있어서 많은 응용 프로그램에서 사용된다.

그래프를 통해 유한 상태 기계(finite state machine, automata)를 모델링 하거나, 도로 네트워크에서 교통 흐름을 연구하기도 한다.

이번 장에서는 가중치가 양수인 주로 방향 가중 그래프에 대해 다룰 것이다.

 

 

 

그래프 순회 문제

그래프 G = <V, E>가 주어질 때 특정 정점 s로부터 시작하여 모든 정점 v ∈ V를 방문하는 문제로,

그래프에서 특정 정점을 찾기 위한 용도로 사용될 수도 있기 때문에 그래프 탐색 문제라고도 부른다.

 

대표적인 탐색 방법은 다음 두가지가 있다.

- 너비 우선 탐색(BFS, Breadth First Search)

시작 정점을 경계에 추가하고 현재 경계에 인접한 정점을 반복적으로 탐색한다.

BFS는 모든 정점에 대해 자식 정점을 손자 정점보다 먼저 방문하는 특징이 있고, 큐를 이용하여 구현한다.

 

- 깊이 우선 탐색(DFS, Depth First Search)

시작 정점에서 시작하여 특정 경로를 따라 가능한 멀리 있는 정점을 재귀적으로 방문하는 방식이다.

그리고 더 방문할 정점이 없어지면 다른 경로를 찾아 다시 멀어지는 방향으로 탐색을 반복한다.

이러한 탐색 방법을 백트래킹(backtracking)이라고 하고, 스택을 이용하여 구현한다.

 

 

소스 코드 및 실행 결과

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <stack>

#include "graph_and_edge.h"

using namespace std;

template <typename T>
vector<unsigned> dfs(const Graph<T>& G, unsigned start) {
	// queue<unsigned> queue; 
	stack<unsigned> stack;
	set<unsigned> visited;         // 방문한 정점
	vector<unsigned> visit_order;  // 방문 순서

	stack.push(start);

	while (!stack.empty()) {
		unsigned curr_vertex = stack.top();     // queue.front();
		stack.pop();
		// queue.pop();

		// 현재 정점을 이전에 방문하지 않았다면
		if (visited.find(curr_vertex) == visited.end()) {
			visited.insert(curr_vertex);
			visit_order.push_back(curr_vertex);

			for (Edge<T>& e : G.edges(curr_vertex))
				// 인접한 정점 중에서 방문하지 않은 정점이 있다면 스택에 추가
				if (visited.find(e.dst) == visited.end())
					stack.push(e.dst);
					// queue.push(e.dst);
		}
	}

	return visit_order;
}

int main() {
	using T = unsigned;

	// 그래프 객체 생성
	Graph<T> G = create_reference_graph<T>();
	cout << "[입력 그래프]" << endl;
	cout << G << endl;

	// 1번 정점부터 DFS 실행 & 방문 정점 출력
	cout << "[DFS 방문 순서]" << endl;
	vector<unsigned> visit_order = dfs(G, 1);

	for (unsigned v : visit_order)
		cout << v << " ";
	cout << endl;
}

 

 

 

=> DFS와 BFS의 시간 복잡도는 모두 O(V + E)이다. 

BFS는 시작 정점에서 가까운 정점을 찾는 데 적합하고, 반대로 DFS는 시작 정점에서 멀리 있는 정점을 찾는 경우 적합하다.

 

=> 또한 BFS에서 특정 정점을 방문할 경우, 시작 정점에서 해당 정점까지의 최단 거리 경로가 보장되는 반면 DFS에서는 보장되지 않는다. 따라서 최단 경로 알고리즘은 BFS를 기반으로 한다.

 

=> BFS는 현재 경계에 인접한 모든 정점을 방문하므로 BFS에 의해 생성된 검색 트리는 짧고 넓은 편이며 많은 메모리를 필요로 한다. 반면 DFS에 의해 생성된 검색 트리는 길고 좁은 편이며 상대적으로 적은 메모리를 필요로 한다.