ChatGPT体验 AI绘画体验

深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。在执行深度优先搜索时，它沿着一个分支走到底，然后回溯。以下是使用 C++ 实现深度优先搜索的一个基本模板： ```cpp #include <iostream> #include <vector> using namespace std; // 函数模板，用于执行深度优先搜索 void DFS(int node, vector<int> adj[], vector<bool>& visited) { // 当前节点标记为已访问 visited[node] = true; cout << node << " "; // 遍历当前节点的所有邻接节点 for (int i = 0; i < adj[node].size(); i++) { int nextNode = adj[node][i]; // 如果邻接节点未被访问，则递归地进行DFS if (!visited[nextNode]) { DFS(nextNode, adj, visited); } } } int main() { // 假设有5个节点的图 int nodes = 5; // 创建图的邻接表表示 vector<int> adj[nodes]; // 添加边，例如： // 节点0与节点1相连 adj[0].push_back(1); // 节点1与节点2相连 adj[1].push_back(2); // 节点2与节点0和节点3相连 adj[2].push_back(0); adj[2].push_back(3); // 节点3与节点4相连 adj[3].push_back(4); // 访问数组，初始所有节点都未被访问 vector<bool> visited(nodes, false); // 从节点0开始执行DFS DFS(0, adj, visited); return 0; } ``` 在这个模板中，我们使用了一个邻接表来表示图，其中`adj`是一个数组，数组的每个索引代表一个节点，而对应的数组元素是一个包含与该节点相连的所有节点列表的`vector`。我们还使用了一个`visited`数组来跟踪哪些节点已经被访问过，以避免重复访问。 在`DFS`函数中，我们首先将当前节点标记为已访问，并打印出来。然后，我们遍历当前节点的所有邻接节点，并对每个未被访问的邻接节点递归地调用`DFS`函数。 在`main`函数中，我们创建了一个示例图，并从节点0开始执行深度优先搜索。这个模板可以根据你的具体需求进行调整，例如处理不同的图结构或者执行不同的操作。