C++实现广度优先搜索（BFS）算法 |holyya.com

C++实现广度优先搜索（BFS）算法

2023-07-08 14:36:42 深夜i -- --

C++ 广度优先搜索 BFS 算法

广度优先搜索算法（BFS）是一种常用的图算法，用于在图中寻找从起始点到目标点的最短路径。C++是一种高效的编程语言，可以很方便地实现BFS算法。

BFS算法的基本思路是，从起始点开始，依次遍历所有与该点相邻的点，再依次遍历这些相邻点的相邻点，直到找到目标点为止。为了避免重复遍历已经遍历过的点，我们需要用一个标记数组来记录每个点是否已经被访问过。

以下是C++语言实现BFS算法的示例代码：


#include<iostream>
#include<queue>
#include<vector>
using namespace std;
const int MAXN=10000;
bool visited[MAXN];
vector<int> adj[MAXN]; // 存储邻接表
void bfs(int start) {
  queue<int> q;
  q.push(start);
  visited[start] = true;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int v : adj[u]) {
      if (!visited[v]) {
        visited[v] = true;
        q.push(v);
      }
    }
  }
}
int main() {
  int n,m,s;
  cin>>n>>m>>s; // n表示点的数量，m表示边的数量，s表示起始点
  for(int i=0;i<m;i++) {
    int u,v;
    cin>>u>>v; // 读入一条边的信息
    adj[u].push_back(v);
    adj[v].push_back(u); // 无向图需要在两个点的邻接表里都添加对方
  }
  bfs(s);
  return 0;
}

在上述代码中，我们用一个邻接表来存储图中每个点的相邻点。在`bfs()`函数中，我们首先将起始点加入队列中，并标记为已访问。然后进入循环，从队头取出一个点，遍历它的所有相邻点。如果该相邻点未被访问过，则将其加入队列中，并标记为已访问。重复以上步骤，直到队列为空，搜索过程结束。

C++的STL库中提供了队列、向量等数据结构的支持，使得代码实现更加简洁、高效。通过样例代码的学习，我们可以很方便地在C++中实现广度优先搜索算法。

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

下一篇: 如何在C++中使用Python.h头文件

评论区

()

相似文章