C++图的广度优先遍历 |21xrx.com

C++图的广度优先遍历

2023-07-01 13:03:18 深夜i -- --

C++ 图广度优先遍历

在计算机科学中，图是一种表示物件之间关系的数据结构。图可以被用来模拟实际世界中许多场景，例如社交网络、电子商务和铁路系统等。在C++中，可以使用邻接矩阵或邻接表等数据结构来表示图。

广度优先搜索是图的遍历算法之一。该算法从图中的某个顶点开始，依次访问与该顶点直接相邻的顶点，并以此类推。该算法使用队列存储待访问的顶点，每次从队列中取出一个顶点进行访问，访问完成后将该顶点的所有邻接点加入队列。重复此过程直到所有边都被访问。

下面是C++中基于邻接矩阵的广度优先搜索实现：


#include <iostream>
#include <queue>
using namespace std;
const int MAXSIZE = 10; // 图的最大顶点数
int graph[MAXSIZE][MAXSIZE]; // 图的邻接矩阵
bool visited[MAXSIZE]; // 记录顶点是否已访问
// 广度优先搜索
void BFS(int start) {
  queue<int> q; // 存储待访问的顶点
  visited[start] = true; // 将起点标记为已访问
  q.push(start); // 将起点加入队列
  while (!q.empty()) { // 当队列非空时
    int curr = q.front(); // 取出队首顶点
    cout << curr << " "; // 访问该顶点
    q.pop(); // 将该顶点从队列中移除
    // 遍历该顶点所有未访问的邻接点
    for (int i = 0; i < MAXSIZE; i++) {
      if (graph[curr][i] != 0 && !visited[i]) {
        visited[i] = true; // 标记为已访问
        q.push(i); // 将该邻接点加入队列
      }
    }
  }
}
int main() {
  // 初始化邻接矩阵
  for (int i = 0; i < MAXSIZE; i++) {
    for (int j = 0; j < MAXSIZE; j++) {
      graph[i][j] = 0; // 初始化为0
    }
  }
  // 添加边
  graph[0][1] = 1;
  graph[0][2] = 1;
  graph[1][3] = 1;
  graph[1][4] = 1;
  graph[2][4] = 1;
  graph[3][5] = 1;
  graph[4][5] = 1;
  // 初始化visited数组
  for (int i = 0; i < MAXSIZE; i++) {
    visited[i] = false;
  }
  // 从顶点0开始广度优先搜索
  BFS(0);
  return 0;
}

上述代码中，邻接矩阵使用二维数组表示。例如，graph[0][1]表示顶点0和1之间有一条边。visited数组用于记录顶点是否已访问，初始化为false。BFS函数接受一个起始顶点作为参数，首先将该顶点标记为已访问，并将其加入队列。接着循环遍历队列，每次取出队首顶点并访问，然后遍历该顶点所有未访问的邻接点并将其加入队列。

在实际应用中，图的广度优先搜索可以应用于路线建立、网络消息传输、遗传算法等多个领域。掌握此算法对于计算机科学领域的工程人员来说是非常重要的。

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

下一篇: C++如何输入一维数组？

评论区

()

相似文章