[알고리즘] 깊이 우선 탐색(DFS, Depth-First Search)

너비 우선 탐색이 시작 정점에서 시작하여 점차 탐색 범위를 넓혀 나가는 방식이라면, 깊이 우선 탐색은 시작 정점에서 시작하여 특정 경로를 따라 가능한 멀리 있는 정점을 재귀적으로 먼저 방문하는 방식이다.

---

깊이 우선 탐색

 
깊이 우선 탐색은 시작 정점을 경계에 추가하는 것으로 시작한다.
너비 우선 탐색의 그림 예를 변형해서 가져왔다.

깊이 우선 탐색 예

 
하나의 지점에서 시작하여 가능한 멀리 있는 정점에 도달하고 재귀하는 방식을 가진다.

---

구현

 
깊이 우선 탐색은 두 가지의 코드를 사용할 수 있다.
 
1. Stack를 이용한 깊이 우선 탐색
2. 재귀 함수를 이용한 깊이 우선 탐색
 
이 두 가지가 있다.
 
(1)
 

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

bool visited[9];
vector<int> graph[9];

void dfs(int start) {
    stack<int> s;
    s.push(start);
    visited[start] = true;
    cout << start << endl;

    while (!s.empty()) {
        int x = s.top();
        s.pop();
        for (int i = 0; i < graph[x].size(); i++) {
            int y = graph[x][i];
            if (!visited[y]) {
                cout << y << endl;
                visited[y] = true;
                s.push(x);
                s.push(y);
                break;
            }
        }
    }
}

int main(void)
{
    graph[1].push_back(2);
    graph[1].push_back(5);

    graph[2].push_back(1);
    graph[2].push_back(4);
    graph[2].push_back(5);

    graph[3].push_back(4);
    graph[3].push_back(7);

    graph[4].push_back(2);
    graph[4].push_back(3);
    graph[4].push_back(5);
    graph[4].push_back(6);
    graph[4].push_back(8);

    graph[5].push_back(1);
    graph[5].push_back(2);
    graph[5].push_back(4);
    graph[5].push_back(8);

    graph[6].push_back(4);
    graph[6].push_back(7);
    graph[6].push_back(8);

    graph[7].push_back(3);
    graph[7].push_back(6);

    graph[8].push_back(4);
    graph[8].push_back(5);
    graph[8].push_back(6);

    dfs(1);

    return 0;
}

 
스택을 이용하여 도달했던 지점은 체크한다.
그리고 깊게 들어갔다가 다시 나와야 하므로 break를 사용해서 반복문을 빠져나간다.
 
(2)
 

#include <iostream>
#include <vector>
#define MAX 8
using namespace std;

vector<int> graph[MAX];
bool visited[MAX] = { false };

void dfs(int start) {
    cout << start << endl;
	visited[start] = true;

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

int main(void)
{
    graph[1].push_back(2);
    graph[1].push_back(5);

    graph[2].push_back(1);
    graph[2].push_back(4);
    graph[2].push_back(5);

    graph[3].push_back(4);
    graph[3].push_back(7);

    graph[4].push_back(2);
    graph[4].push_back(3);
    graph[4].push_back(5);
    graph[4].push_back(6);
    graph[4].push_back(8);

    graph[5].push_back(1);
    graph[5].push_back(2);
    graph[5].push_back(4);
    graph[5].push_back(8);

    graph[6].push_back(4);
    graph[6].push_back(7);
    graph[6].push_back(8);

    graph[7].push_back(3);
    graph[7].push_back(6);

    graph[8].push_back(4);
    graph[8].push_back(5);
    graph[8].push_back(6);

    dfs(1);

    return 0;
}

 
위 코드는 Stack과 결과는 똑같지만 과정이 조금 다르다. 재귀 함수를 사용해서 구현했다.