图算法：深度优先搜索 (DFS)

什么是深度优先搜索？

深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索图的分支。当节点v的所在边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。

算法思想

DFS 的核心是栈（可以是显式的栈，也可以是函数调用栈）。

1. 从起始节点开始，访问它。
2. 将其一个未被访问的邻居节点压入栈中，并访问它。
3. 重复步骤 2，直到当前路径没有未被访问的邻居。
4. 如果当前节点没有未访问的邻居，就从栈中弹出一个节点，回溯。
5. 重复步骤 2-4，直到栈为空。

代码实现 (C++，递归)

#include <iostream>
#include <vector>
#include <map>
#include <list>

class Graph {
    std::map<int, std::list<int>> adj;
    void DFSUtil(int v, std::map<int, bool>& visited);

public:
    void addEdge(int v, int w);
    void DFS(int v);
};

void Graph::addEdge(int v, int w) {
    adj[v].push_back(w);
}

void Graph::DFSUtil(int v, std::map<int, bool>& visited) {
    visited[v] = true;
    std::cout << v << " ";

    for (int i : adj[v]) {
        if (!visited[i]) {
            DFSUtil(i, visited);
        }
    }
}

void Graph::DFS(int v) {
    std::map<int, bool> visited;
    DFSUtil(v, visited);
}

应用场景

• 寻找图中的路径。
• 拓扑排序。
• 检测图中的环。
• 寻找连通分量。