深度优先算法的C++代码 |21xrx.com

深度优先算法的C++代码

2023-07-09 20:27:14 深夜i -- --

深度优先算法 C++ 代码

深度优先算法是一种常用的图遍历算法，它可以遍历所有能够到达的节点，并且可以很好的应用于解决许多图论问题。在本文中，我们将提供深度优先算法的C++代码实现，让大家可以更好的了解深度优先算法的实现过程。

深度优先搜索的基本思想是用栈来实现，从起始点开始不断往前走，每次走到一个新的节点，就把它存放在栈中，然后回溯到前面的节点，再往前找到下一个节点，知道找到目标节点或者无路可走。在进行深度优先搜索时，我们需要记录每个节点是否被访问过，以保证每个节点不被重复访问。

以下是深度优先搜索的C++代码实现：


#include <iostream>
#include <stack>
#include <vector>
using namespace std;
const int N = 100010;
int n, m;
vector<int> g[N]; //邻接表存图
bool st[N]; //记录每个节点是否已经被访问
void dfs(int u) //深度优先搜索函数
{
  stack<int> s;
  s.push(u); //将初始节点u加入栈中
  while (!s.empty())
  {
    int t = s.top(); //取出栈顶节点
    s.pop(); //弹出栈顶节点
    if (st[t]) continue; //如果该节点已被访问，跳过
    st[t] = true; //将该节点标记为已经访问
    cout << t << " ";
    for (int i = g[t].size() - 1; i >= 0; i--) //遍历该节点的所有子节点，将其加入栈中
    {
      int j = g[t][i];
      if (!st[j])
      {
        s.push(j);
      }
    }
  }
}
int main()
{
  cin >> n >> m;
  while (m--)
  {
    int a, b;
    cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  dfs(1); //从节点1开始进行深度优先搜索
  return 0;
}

上述代码中，我们用邻接表的方式存储了图结构，深度优先搜索函数中使用栈来实现搜索过程，同时标记每个节点是否已经被访问。最终得出的遍历结果是从初始节点开始遍历的连通块，如果需要遍历整张图，可在主函数中循环调用深度优先搜索函数，直到所有节点都被遍历过。

总之，深度优先搜索算法是一个非常实用和重要的算法，可以用于图遍历和求解图论问题，其代码实现思路比较简单，但需要熟练的掌握才能灵活应用。

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

下一篇: C++有哪些排序算法？

评论区

()

相似文章