DFS, BFS

그래프

node와 vertex로 이루어진 자료구조
전 세계 비행기 이동은 공항(node)과 항공편(vertex)으로 생각할 수 있고,
대한민국의 도로는 교차점 또는 마을(node)과 도로(vertex)로 생각할 수 있다.

directed graph

vertex에 방향이 있다.
A공항에서 B공항으로 가는 항공편은 있지만, B공항에서 A공항으로 가는 항공편이 없는 경우

undeirected graph

vertex에 방향이 없다.
도로는 양방 통행이므로, A도시에서 B도시로 가는 길이 있다면 B도시에서 A도시로 가는 길이 있다.

DFS

Depth-First Search
최대한 깊이 탐색한 후, 더 이상 탐색할 수 없는 경우 옆으로 이동하여 탐색한다.
미로 찾기에서 왼손법칙, 오른손 법칙 등은 DFS의 일종이라고 볼 수 있다.
한쪽 방향으로 쭉 가다가 막힐 경우, 왔던 길을 되돌아가며 다른 방향을 탐색하는 방법이다.

알고리즘적 구현은 재귀함수 또는 스택을 주로 사용하며 구현한다.

코드(재귀함수)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int visited[100001] = { 0 };
vector<int> load[100001];
int order = 1;

//시작하는 node를 받으면 재귀함수를 통해 탐색한다.
void dfs(int node) {
	if (visited[node] == 0) {
		visited[node] = order++;
		for (auto iter = load[node].begin(); iter != load[node].end(); iter++) {
			dfs(*iter);
		}
	}
}

//undirected graph, 양방향으로 길을 기록한다.
load[node1].push_back(node2);
load[node2].push_back(node1);

BFS

Breadth-First Search
넓게 탐색한 후, 다음 깊이로 이동

알고리즘적 구현은 주로 큐를 사용하여 구현한다.

코드

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

int visited[100001] = { 0 };
vector<int> load[100001];
int order = 1;
queue<int> q;

//undirected graph, 양방향으로 길을 기록한다.
load[node1].push_back(node2);
load[node2].push_back(node1);

//시작하는 노드의 번호를 큐에 넣는다.
q.push(R);
while (!q.empty()) {
	temp = q.front();
	q.pop();
	if (visited[temp] == 0) {
		visited[temp] = order++;
		for (auto iter = load[temp].begin(); iter != load[temp].end(); iter++) {
			q.push(*iter);
		}
	}
}

응용 문제

해당 노드까지의 길을 기억해야 하는 문제는 DFS를 사용하면 편리하다.
stack을 이용한 DFS를 사용하여, 원하는 node에 도달하면 현재 stack에 있는 노드들이 경로가 된다.

최단거리를 구해야 하는 문제는 BFS를 사용하면 편리하다.
처음 시작 node의 거리 순서대로 탐색하므로, 항상 처음 발견되는 node까지의 거리는 최단거리가 된다.