[c++] 깊이 우선 탐색(DFS) 그래프 탐색 알고리즘

08 Dec 2023

깊이 우선 탐색(DFS, Depth-First Search)은 그래프 자료 구조에서 사용되는 탐색 알고리즘 중 하나로, 모든 노드를 방문하고자 할 때 사용됩니다. 이 알고리즘은 더 이상 방문할 수 있는 노드가 없을 때까지 최대한 깊이 들어가서 그래프를 탐색하는 방식을 취합니다.

알고리즘 동작 방식

시작 노드를 스택에 넣고 방문한 것으로 표시합니다.
스택에서 노드를 꺼내고, 그 노드와 연결된 방문하지 않은 인접 노드를 스택에 넣고 방문한 것으로 표시합니다.
스택이 빌 때까지 2단계를 반복합니다.

예제 코드

#include <iostream>
#include <vector>
#include <stack>

void DFS(int start, std::vector<std::vector<int>>& graph, std::vector<bool>& visited) {
    std::stack<int> stack;
    stack.push(start);

    while (!stack.empty()) {
        int current = stack.top();
        stack.pop();

        if (visited[current]) {
            continue;
        }

        visited[current] = true;
        std::cout << "Visited node: " << current << std::endl;

        for (int i = 0; i < graph[current].size(); i++) {
            if (!visited[graph[current][i]]) {
                stack.push(graph[current][i]);
            }
        }
    }
}

int main() {
    int numNodes = 6;
    std::vector<std::vector<int>> graph(numNodes);
    std::vector<bool> visited(numNodes, false);

    graph[0] = {1, 2};
    graph[1] = {0, 3, 4};
    graph[2] = {0, 5};
    graph[3] = {1};
    graph[4] = {1, 5};
    graph[5] = {2, 4};

    DFS(0, graph, visited);

    return 0;
}

위의 코드는 깊이 우선 탐색 알고리즘을 사용하여 그래프를 탐색하는 간단한 예제입니다.

시간 복잡도

DFS의 시간 복잡도는 O(V + E)입니다. 여기서 V는 노드의 수, E는 간선의 수를 나타냅니다.

이러한 알고리즘을 사용하면 그래프에서 모든 노드를 탐색하거나 특정 노드 간의 경로를 찾는 데 유용합니다.

참고 자료

깊이 우선 탐색 - 위키백과
Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne