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

深度优先算法C++代码

2023-07-02 18:10:28 深夜i -- --

深度优先算法 C++代码递归栈图搜索

深度优先算法是一种常见的图算法，它可以用来解决很多问题，比如连通性、路径、循环等。下面是一个基于C++语言的深度优先算法演示代码：


#include <iostream>
#include <vector>
#include <stack>
using namespace std;
vector<int> DFS(vector<vector<int>>& graph, int start) {
  vector<int> res;
  stack<int> st{{start}};
  vector<bool> visited(graph.size(), false);
  while (!st.empty()) {
    auto cur = st.top(); st.pop();
    if (visited[cur]) continue;
    visited[cur] = true;
    res.push_back(cur);
    for (const auto& neighbor : graph[cur]) {
      if (!visited[neighbor]) {
        st.push(neighbor);
      }
    }
  }
  return res;
}
int main() {
  vector<vector<int>> graph{1, 3, 1, 4, 2, {3}};
  int start = 0;
  auto res = DFS(graph, start);
  for (const auto& node : res)
    cout << node << " ";
  
  cout << endl;
  return 0;
}

这段代码实现了一个简单的深度优先遍历算法。它首先定义了一个`DFS`函数用来进行遍历，其中参数`graph`是一个邻接表，`start`表示从哪个节点开始遍历。函数内部定义了一个栈`st`，一个状态数组`visited`来记录哪些节点已经被遍历过。然后进入循环，如果栈不为空，就从栈中取出一个节点，判断是否已经被遍历过，若已经被遍历过，则跳过，否则将其加入结果数组中，将其`visited`标为已经遍历过，然后将其未被访问过的邻居加入栈中。不断重复以上操作，直到栈为空，所有节点都被遍历完毕。最后输出结果数组即可。

本篇文章介绍了一种常见的深度优先遍历算法C++代码实现。深度优先遍历算法具有一定的难度和复杂度，但只要熟悉基本的数据结构和语法，就可以轻松理解和应用。希望本篇文章对您有所帮助。

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

下一篇: 如何将C++二维数组全部设为0？

评论区

()

相似文章