深度优先搜索 Depth-First Search DFS

深度优先搜索（Depth-First Search，DFS）是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索图的分支，当节点v的所在边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点，继续探寻其他分支。深度优先搜索既可以用在无权图中，也可以用在有权图上，后者通常使用广度优先搜索（BFS）。

深度优先搜索的特点：

顺序性：深度优先搜索按照节点的深度顺序进行遍历。
回溯：当路径的末端没有未访问的节点时，算法会回溯到上一个节点继续搜索。
栈的使用：可以手动使用栈数据结构来实现回溯，或者利用递归的系统调用栈来模拟。

深度优先搜索的实现：

递归实现

递归是实现深度优先搜索的自然方式。每次递归调用都会访问一个节点的所有邻接节点。

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

class Graph {
private:
    int V; // 顶点的数量
    std::vector<std::vector<int>> adj; // 邻接表

public:
    Graph(int V) : V(V), adj(V) {}

    void addEdge(int v, int w) {
        adj[v].push_back(w); // 添加从v到w的边
    }

    void DFS(int v, std::vector<bool>& visited) {
        visited[v] = true;
        std::cout << v << " "; // 访问节点v

        for (int i : adj[v]) {
            if (!visited[i]) {
                DFS(i, visited); // 递归访问未访问的邻接节点
            }
        }
    }
};

int main() {
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);

    std::vector<bool> visited(g.V, false);
    g.DFS(0, visited); // 从顶点0开始深度优先搜索

    return 0;
}

非递归实现

非递归的深度优先搜索使用显式的栈来模拟递归过程。

void DFSIterative(Graph& g, int start) {
    std::stack<int> stack;
    std::vector<bool> visited(g.V, false);

    stack.push(start);
    visited[start] = true;

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

        std::cout << v << " "; // 访问节点v

        for (int i = g.adj[v].size() - 1; i >= 0; --i) {
            int next = g.adj[v][i];
            if (!visited[next]) {
                stack.push(next);
                visited[next] = true;
            }
        }
    }
}

深度优先搜索的应用：

拓扑排序：在有向无环图（DAG）中，可以使用DFS进行拓扑排序。
路径寻找：在图或树中寻找从一点到另一点的路径。
连通分量：识别图中的所有连通分量。
解决谜题：如数独、迷宫等，DFS可以用来尝试所有可能的解决方案。

深度优先搜索是一种强大的算法，适用于许多需要探索所有可能路径的场景。

(责任编辑：admin)

热门: