설명

• DFS : Depth-First Search
• 그래프나 트리에서 시작 정점으로부터 갈 수 있는 깊이까지 탐색하는 알고리즘
• 더 이상 갈 수 없으면 되돌아와 다른 경로를 탐색하는 알고리즘
• 스택이나 재귀호출을 사용하여 구현
• 경로 탐색, 사이클 검출, 연결 요소 찾기 등

예제

#include <iostream>
#include <vector>

using namespace std;

void dfs(int node, vector<vector<int>>& graph, vector<bool>& visited) {
    visited[node] = true;
    cout << node << " ";

    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, graph, visited);
        }
    }
}

int main() {
    int n = 6;
    vector<vector<int>> graph(n);
    graph = { {1, 2}, {0, 3, 4}, {0, 4}, {1}, {1, 5}, {4} };
    vector<bool> visited(n, false);
    
    dfs(0, graph, visited);

    return 0;
}

결과

• 0 1 3 4 5 2

탐색 순서 설명

1. 0에서 시작하여 1로 이동합니다.
2. 1에서 3으로 이동합니다.
3. 3에서 더 이상 갈 수 없으므로 1로 돌아옵니다.
4. 1에서 4로 이동합니다.
5. 4에서 5로 이동합니다.
6. 5에서 더 이상 갈 수 없으므로 4로 돌아옵니다.
7. 4에서 2로 이동합니다.
8. 2에서 더 이상 갈 수 없으므로 탐색을 종료합니다.

예제 그래프