深度优先搜索算法c++模板

深度优先搜索（DFS）是一种常用的图遍历算法，用于遍历或搜索图中的节点。下面是一个使用C++模板实现的深度优先搜索算法：

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

using namespace std;

// 图的节点结构
struct Node {
    int value;
    vector<Node*> neighbors;
    bool visited;
};

// 深度优先搜索函数
void dfs(Node* start) {
    stack<Node*> s;
    s.push(start);
    
    while (!s.empty()) {
        Node* current = s.top();
        s.pop();
        
        if (!current->visited) {
            cout << current->value << " ";
            current->visited = true;
            
            for (Node* neighbor : current->neighbors) {
                if (!neighbor->visited) {
                    s.push(neighbor);
                }
            }
        }
    }
}

int main() {
    // 创建图的节点
    Node* node1 = new Node{1, {}, false};
    Node* node2 = new Node{2, {}, false};
    Node* node3 = new Node{3, {}, false};
    Node* node4 = new Node{4, {}, false};
    
    // 构建图的连接关系
    node1->neighbors.push_back(node2);
    node1->neighbors.push_back(node3);
    node2->neighbors.push_back(node4);
    node3->neighbors.push_back(node4);
    
    // 从节点1开始进行深度优先搜索
    dfs(node1);
    
    return 0;
}

上述代码中，我们首先定义了一个`Node`结构来表示图的节点，其中包含了节点的值、邻居节点的指针以及一个标记是否已访问的布尔值。然后，我们使用一个栈来辅助进行深度优先搜索，将起始节点压入栈中，并在循环中不断弹出栈顶节点进行处理。如果当前节点未被访问过，则输出其值，并将其标记为已访问。接着，将当前节点的未访问过的邻居节点压入栈中，以便后续继续遍历。直到栈为空时，搜索结束。