C++ BFS算法 |21xrx.com

C++ BFS算法

2023-07-09 05:19:31 深夜i -- --

C++程序设计 BFS图搜索算法数据结构与算法图论算法实现

C++ 中的 BFS 算法

BFS（Breadth First Search，广度优先搜索）算法是一种常见的图搜索算法，用于在图或树中遍历每个节点。这个算法从根节点开始，遍历和访问相邻的节点，然后移动到下一个级别。这种算法通常用于解决最短路径问题，最小生成树问题和进行图遍历。

使用 C++ 编程语言实现 BFS 算法很简单。下面是一个简单的示例代码：


#include <iostream>
#include <queue>
#include <vector>
using namespace std;
void bfs(vector<vector<int>>& graph, int starting_node)
{
  vector<bool> visited(graph.size(), false);
  queue<int> q;
  visited[starting_node] = true;
  q.push(starting_node);
  while (!q.empty())
  {
    int node = q.front();
    q.pop();
    cout<< node <<" ";
    for (auto i : graph[node])
    {
      if (!visited[i])
      {
        visited[i] = true;
        q.push(i);
      }
    }
  }
}
int main()
{
  vector<vector<int>> graph = {1, 2, 0, 1, 2};
  bfs(graph, 0);
  return 0;
}

在上面的代码中，我们首先创建了一个 vector > 类型的 graph 变量，表示了一个具有 5 个节点和 7 条边的无向图。然后我们定义了一个 bfs() 函数，这个函数使用了一个 bool 类型的 visited 数组和一个 int 类型的 starting_node 变量，表示起始节点。我们遍历和访问起始节点，然后将起始节点推入队列中。之后，我们从队列中依次推出每个节点，并访问它的每个未被访问过的邻居节点，并将这些节点都推入队列中。这个过程会一直持续，直到队列为空。

上面的代码输出结果为：

0 1 2 3 4

这与我们想要遍历的无向图的正确顺序相同，证明了 BFS 算法的正确性。

因此，上面的代码显示了如何在 C++ 中编写 BFS 算法。这个算法比较简单，使用了一个 bool 类型的 visited 数组和一个队列，因此，很容易理解和使用。

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

下一篇: C++保护成员函数的使用和作用

评论区

()

相似文章