9-4. [C/C++] 그래프의 탐색 - 깊이 우선 탐색, DFS

그래프 탐색

그래프 탐색은 하나의 정점에서 시작해 모든 정점들은 한 번씩 방문하는 그래프의 가장 기본적인 연산이다.

그래프의 탐색 방법에는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)가 있다.

---

깊이 우선 탐색

깊이 우선 탐색(depth first search, DFS)는 그래프의 깊은 부분을 먼저 탐색하는 그래프 순회 방법이다.

DFS는 임의의 노드에서 가장 깊은(먼) 부분을 먼저 탐색한다.

 

멀리 있다면 당연하게 나중에 만나게 될 것이다.

"나중에 만난 노드를 먼저 탐색한다." 스택 자료구조의 특징과 비슷하다는 것을 알 수 있다.

그래서 DFS에서는 스택을 사용한다.

 

DFS의 동작 과정을 보자.

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다.
   방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.

아래 그림을 보며 DFS의 과정을 살펴보자.

DFS 시간 복잡도

DFS는 그래프의 모든 간선을 조사하므로 정점의 수가 n이고 간선의 수가 e인 그래프를 DFS하는 시간은 

인접 리스트를 이용한 그래프의 경우 O(n + e) 이고, 인접 행렬을 이용한 그래프의 경우 O(n²) 이다.

시간 복잡도에서도 알 수 있듯이, 희소 그래프인 경우 인접 리스트를 사용하는 것이 더 좋다.

---

위에서 DFS는 스택을 사용한다고 했다. 그렇지만 스택을 구현해서 사용하지는 않는다.

재귀 함수를 사용하면 시스템 스택이 사용된다. 그래서 재귀 함수를 이용할 것이다.

인접 행렬을 이용한 그래프의 DFS

전에 구현했던 AdjMatGraph 클래스를 상속해서 DFS를 위한 MatGraphForDFS 클래스를 구현했다.

// MatGraphForDFS.h
#include "AdjMatGraph.h"

class MatGraphForDFS : public AdjMatGraph {
    bool visited[MAX_SIZE];

public:
    MatGraphForDFS(int size) : AdjMatGraph(size) {}
    void reset() {
        for (int i = 0; i < size; i++) {
            visited[i] = false;
        }
    }

    bool isLinked(int u, int v) { return getEdge(u, v) == 1; }

    void dfs(int v) {
        visited[v] = true;
        cout << "[" << v << "] ";
        
        for (int u = 0; u < size; u++) {
            if (isLinked(v, u) && visited[u] == false)
                dfs(u);
        }
    }
};

// MatGraphForDFS.cpp
#include "MatGraphForDFS.h"

int main() {
    MatGraphForDFS graph(4);

    graph.insertEdge(0, 1);
    graph.insertEdge(0, 3);
    graph.insertEdge(1, 2);
    graph.insertEdge(1, 3);
    graph.insertEdge(2, 3);

    graph.display();
    graph.dfs(0); cout << endl;
}

/*
실행 결과:
Graph by Adjacency Matrix
0 1 0 1
1 0 1 1
0 1 0 1
1 1 1 0
[0] [1] [2] [3]
*/

인접 리스트를 이용한 그래프의 DFS

전에 구현했던 AdjListGraph 클래스를 상속해서 DFS를 위한 ListGraphForDFS 클래스를 구현했다.

// ListGraphForDFS.h
#include "AdjListGraph.h"

class ListGraphForDFS : public AdjListGraph {
    bool visited[MAX_SIZE];

public:
    ListGraphForDFS(int size) : AdjListGraph(size) {}

    void reset() {
        for (int i = 0 ;i < size; i++) {
            visited[i] = false;
        }
    }

    bool isLinked(int u, int v) {
        for (Node *cur = graph[u]; cur != NULL; cur = cur->getLink()) {
            if (cur->getVertex() == v) return true;
        }
        return false;
    }

    void dfs(int v) {
        visited[v] = true;
        cout << "[" << v << "] ";
        
        for (Node *cur = graph[v]; cur != NULL; cur = cur->getLink()) {
            if (visited[cur->getVertex()] == false)
                dfs(cur->getVertex());
        }
    }
};

// ListGraphForDFS.cpp
#include "ListGraphForDFS.h"

int main() {
    ListGraphForDFS graph(4);

    graph.insertEdge(0, 1);
    graph.insertEdge(0, 3);
    graph.insertEdge(1, 2);
    graph.insertEdge(1, 3);
    graph.insertEdge(2, 3);

    graph.display();
    graph.dfs(0); cout << endl;
}

/*
실행 결과:
Graph by Adjacency List
3 1
3 2 0
3 1
2 1 0
[0] [3] [2] [1]
*/

실행 결과가 인접 행렬을 이용했을 때와 다르다.

인접 리스트의 노드 순서때문에 결과는 다를 수 있다.

DFS는 그래프를 순회하는 방법일 뿐이라서 노드가 들어가 있는 순서에 따라 결과는 다를 수 있다.

하지만 과정은 동일하다.

 

위 코드는 아래 이미지를 클릭해 깃허브에서도 확인할 수 있다.