C++深度优先搜索 |21xrx.com

C++深度优先搜索

2023-07-05 09:30:12 深夜i -- --

C++ 深度优先搜索算法图回溯算法

C++深度优先搜索是一种常用的算法，它经常被用于解决搜索问题、图问题等。这种算法的基本思想是：从某一起点出发，递归地搜索其可达的所有节点，并标记已经搜索过的节点，直到无法搜索为止。下面，我们将通过一个简单的例子来了解深度优先搜索的实现。

假设有一张无向图，其中包括5个节点和5条边。我们需要使用深度优先搜索算法来找到从第一个节点开始的所有路径：

![image.png](https://cdn.luogu.com.cn/upload/image_hosting/cb210b9r.png)

首先，我们需要定义一个数据结构来表示这张图的邻接表，如下：


const int MAXN = 1000005;
vector<int> adj[MAXN];

接下来，我们定义两个函数。第一个函数用来递归地搜索当前节点的所有邻居：


void dfs(int x) {
  printf("%d ", x); // 输出当前节点
  for (int i = 0; i < adj[x].size(); i++) { // 遍历当前节点的邻居
    int v = adj[x][i];
    if (vis[v]) continue; // 如果邻居节点已经被搜索过，则跳过
    vis[v] = true; // 标记邻居节点为已经搜索
    dfs(v); // 递归搜索邻居节点
  }
}

第二个函数是主函数，用来遍历所有节点，并对没有被搜索过的节点进行搜索：


void solve() {
  for (int i = 1; i <= n; i++) { // 遍历所有节点
    if (vis[i]) continue; // 如果当前节点已经被搜索过，则跳过
    vis[i] = true; // 标记当前节点为已经搜索
    dfs(i); // 递归搜索当前节点的邻居
  }
}

在主函数中，我们遍历所有节点，并对没有被搜索过的节点进行搜索。具体实现过程如下：


int main() {
  n = 5, m = 5;
  addEdge(1, 2);
  addEdge(2, 3);
  addEdge(2, 4);
  addEdge(3, 4);
  addEdge(4, 5);
  solve();
  return 0;
}

这样，我们就完成了从第一个节点开始的所有路径的搜索。

总结一下，使用C++深度优先搜索算法来解决搜索问题、图问题等，需要定义邻接表来表示图的结构，然后通过递归遍历当前节点的邻居来完成搜索过程。在遍历过程中，需要使用vis数组来标记已经搜索过的节点，防止重复搜索。

上一篇: idea打包java可执行jar包

下一篇: 现代操作系统——visual c++ 6.0不能兼容的原因和解决方法

评论区

()

相似文章