C++深度优先遍历算法 |21xrx.com

C++深度优先遍历算法

2023-07-05 04:52:58 深夜i -- --

C++ 深度优先遍历算法

C++语言是一种高级计算机编程语言，具有丰富的语法和各种数据结构。在数据结构中，深度优先搜索算法是非常有用的一种算法。本文将介绍深度优先搜索算法在C++中的实现。

深度优先搜索算法（DFS）是一种通过递归方式实现的搜索算法，用于解决许多问题，如路径查找、迷宫问题和图的连通性检查。在DFS算法中，我们从起点开始遍历整个图，并对每个顶点进行标记，以避免出现重复访问。然后，我们在当前路径上继续遍历，直到遍历所有可达节点或找到一个解决方案。

以下是C++中的深度优先搜索算法实现：


#include<bits/stdc++.h>
using namespace std;
bool visited[100];
vector<int> graph[100];
void dfs(int u){
  visited[u] = true;
  cout << u << " ";
  for(int v: graph[u]){
    if(!visited[v]){
      dfs(v);
    }
  }
}
int main(){
  int nodes, edges;
  cin >> nodes >> edges;
  for(int i = 0; i < edges; i++){
    int u, v;
    cin >> u >> v;
    graph[u].push_back(v);
    graph[v].push_back(u);
  }
  memset(visited, false, sizeof(visited));
  dfs(1); //从节点1开始遍历
  return 0;
}

在上面的代码中，我们使用一个布尔数组visited来记录每个顶点是否已经访问过。我们还使用vector来表示图中的顶点和边。在主函数中，我们通过读取输入数据来构建图。然后，我们初始化visited数组，并调用dfs函数从节点1开始遍历。

在dfs函数中，我们标记当前节点（u）为已访问，并输出其值。然后，我们对与当前节点相邻的所有未访问节点（v）进行递归调用dfs函数。

总之，C++中的深度优先搜索算法是一种非常有用的算法，可以解决很多问题。通过使用递归方式实现，我们可以轻松地遍历整个图，并避免出现重复访问。这个算法对于几乎所有的计算机领域都是非常有用的，包括网络、机器学习和人工智能。

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

下一篇: 使用C++求解x的y次幂

评论区

()

相似文章