用c++写一个深度搜索算法

在C++中，深度优先搜索（Depth First Search，DFS）是一种用于图或树遍历的算法，它的基本思想是从起始节点开始，尽可能深地探索分支，直到找到目标节点或者所有可达节点都被访问过。以下是一个简单的无权图的邻接表表示的深度优先搜索实现：

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

using namespace std;

// 图节点
struct GraphNode {
    int value;
    vector<GraphNode*> neighbors; // 邻居列表
};

// 深度优先搜索函数
void dfs(GraphNode* start, bool visited[]) {
    stack<GraphNode*> stackNode;
    stackNode.push(start);
    visited[start->value] = true;

    while (!stackNode.empty()) {
        GraphNode* current = stackNode.top();
        cout << "Visiting: " << current->value << endl;
        stackNode.pop();

        for (GraphNode* neighbor : current->neighbors) {
            if (!visited[neighbor->value]) {  // 如果邻居未访问过
                visited[neighbor->value] = true;  // 标记为已访问
                stackNode.push(neighbor);  // 将邻居压入栈
            }
        }
    }
}

int main() {
    GraphNode graph[4] = {
        {1, {2, 3}},
        {2, {}},  // 与节点1相连
        {3, {4}},  // 与节点1和节点2相连
        {4, {}}   // 仅与节点3相连
    };

    bool visited[5] = {false};  // 初始化所有节点未访问
    dfs(graph[0], visited);

    return 0;
}

这个例子中，我们首先创建了一个邻接表表示的简单图，然后用`dfs`函数进行深度优先搜索。输入起始节点1，程序将依次访问并打印出路径：1 -> 2 -> 3 -> 4。