深度优先算法是一种常用的图遍历算法，它可以遍历所有能够到达的节点，并且可以很好的应用于解决许多图论问题。在本文中，我们将提供深度优先算法的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;
}

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

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

相似文章
• C++实现深度优先算法
  深度优先算法（DFS）是一种非常重要的图遍历算法，可以帮助我们在一张图中快速查找到某个节点的路径或者其他相关信息。而在C++编程中，我们可以通过一些简单的代码来实现这个算法。
  
  

友情链接
• 网站定制开发
• 帮你发
• 小蓄群站获客
• 雅圣洁家政