그래프 이론 - 깊이 우선 탐색: DFS

그래프란?

 

우리 일상생활에서 흔히 볼 수 있는 그래프로 도로, 네트워크, 버스 노선도 등을 들 수 있습니다. 그래프를 탐색하거나 분석할 때 그냥 일일히 방문하는 방법도 있겠지만 프로그래머들은 다른 방법이 없을까 고민했습니다. 

 

DFS - 깊이 우선 탐색

 

깊이 우선 탐색이란 한 노드를 선택하고 그 노드를 타고 노드의 끝까지 매우 deep 하게 파고들어갑니다. 방문한 곳에는 항상 방문표시를 합니다. 그림으로 보면

 1번 노드부터 시작했습니다.

가장 인접한 노드(자식노드) 2, 5중 더 작은 번호로 가는 것으로 여기선 가정하겠습니다.

2번 노드 도착 -> DFS 그럼 2의 인접노드 3, 4 중 더 작은 번호로 갑니다.

3번 노드 도착 -> DFS 그런데 3번노드에서 보니 자식노드가 없습니다. 그렇다면 위로 돌아가 2번의 다른 인접 노드를 봅니다. 4번을 가지 않았네요! 4번으로 갑니다.

4번 노드 도착 -> DFS 4번도 자식노드가 없죠. 그럼 다시 위로 올라갑니다. 2번의 인접노드는 모두 다녀왔죠. 1번까지 갑니다. 1번의 인접노드를 보니 5번에 가지 않았네요. 5번으로 가고 유일 인접노드 6번으로 갑니다. 

 

말로 들으면 무슨 소린지 잘 모를 수 있습니다. 코드를 보겠습니다.

 

#include<iostream>
#include<vector>
#include<algorithm>
#define MAX 100

using namespace std;

int V, E;
int x, y;

vector<int> vertex[MAX];

bool visited[MAX] = { false, };

void setgraph() {
	cin >> V >> E;
	for (int i = 0; i < E; i++) {
		cin >> x >> y;
		vertex[x].push_back(y);
		vertex[y].push_back(x);
	}

	for (int j = 1; j <= V; j++) {
		sort(vertex[j].begin(), vertex[j].end());
	}
}

void DFS(int here) {
	if (visited[here] == true)
		return;

	visited[here] = true;

	cout << "현재 노드 : " << here << '\n';

	for (int i = 0; i < vertex[here].size(); i++) {
		int next = vertex[here][i];

		DFS(next);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	setgraph();
	DFS(1);
}

 

 결과를 보면 이론과 같은 결과를 보여줍니다. 코드를 분석해보면

void DFS(int here) {
	if (visited[here] == true)
		return;

	visited[here] = true;

	cout << "현재 노드 : " << here << '\n';

	for (int i = 0; i < vertex[here].size(); i++) {
		int next = vertex[here][i];

		DFS(next);
	}
}

1. 방문했던 노드라면 다시 돌아갑니다. 

2. 방문하지 않은 곳이라면 방문 표시합니다.

3. 현재 노드가 어딘지 보여줍니다.

4. 현재 노드의 인접노드를 차례로 재귀 방문합니다. 때문에 1의 인접노드 -> 2,5 중 2번 먼저 방문 (for문이 끝나지 않은 상태) -> 2의 인접노드 3, 4 중 3 방문(이번에도 for문이 끝나지 않은 상태) -> ... 이기 때문에 한 노드를 들어가면 그 노드의 끝까지 파고들어가기 때문에 DFS라는 이름이 붙었습니다.