广度优先遍历BFS（队列应用）（邻接矩阵）（C++实现）

广度优先遍历BFS（队列应用）（邻接矩阵）（C++实现）

实现代码

/*
author : eclipse
email  : eclipsecs@qq.com
time   : Mon Apr 13 20:13:55 2020
*/#include<bits/stdc++.h>
using namespace std;vector< vector<int> > matrix;
vector<int> BFSSequence;void createNet(vector< pair< pair<int,int>, int> > net){for(int i = 0; i < net.size(); i++){matrix[net[i].first.first - 1][net[i].first.second - 1] = net[i].second;matrix[net[i].first.second - 1][net[i].first.first - 1] = net[i].second;}
}void BFSTraverse(int start) {start--;vector<bool> tag;//标记是否访问过int vexNum = matrix.size();tag.resize(vexNum);queue<int> q;q.push(start);//起始节点入队tag[start] = true;//标记起始节点访问过while (!q.empty()) {BFSSequence.push_back(q.front());//队首元素加入广度优先遍历序列for (int i = 0; i < vexNum; i++) {if (matrix[q.front()][i] != INT_MAX && !tag[i]) {q.push(i);//将队首顶点的所有邻接点入队tag[i] = true;//标记该邻接点已访问}}q.pop();//出队，搜索下一个顶点的邻接点}
}int main(int argc, char const *argv[])
{int N, start;while (~scanf("%d%d", &N, &start)) {BFSSequence.clear();//清空广度优先遍历队列//构建无向网~~int vexNum = 0;vector< pair< pair<int,int>, int> > net;net.resize(N);for (int i = 0; i < N; i++) {int u, v, value;scanf("%d%d%d", &net[i].first.first, &net[i].first.second, &net[i].second);vexNum = max(vexNum, net[i].first.first);vexNum = max(vexNum, net[i].first.second);}matrix.resize(vexNum);for (int i = 0; i < vexNum; i++) {matrix[i].resize(vexNum);for (int j = 0; j < vexNum; j++) {matrix[i][j] = INT_MAX;}}createNet(net);//~~BFSTraverse(start);for (int i = 0; i < BFSSequence.size() ; i++) {printf("%d ", BFSSequence[i] + 1);}printf("\n");}return 0;
}

算法思路

  • 类似于树的层次遍历算法
  • 从起始顶点开始，访问其未访问过的顶点并将其依次入队，起始顶点的邻接点都访问过后，起始顶点出队，选择队首元素继续访问其未访问过顶点并依次入队，直至遍历所有顶点并检测其所有邻接点是否访问并作上述相应操作
  • 遍历结束可以得到遍历顺序序列和广度优先生成树
  • 上述实现访问所有顶点及其所有邻接点
  • 算法时间复杂度O(n ^ 2)
  • 上述实现代码中相应部分有较为详细的注释

样例图解

  • 广度优先遍历过程，遍历结束可以得到广度优先生成树
  • 上述示例参考王道考研数据结构，为测试数据中的第一个测试样例

测试数据

  • 广度优先遍历过程中， 权值与结果无关，可以忽略下列边带的权值，同时应调整相应代码
10 1
1 2 6
1 3 1
1 4 5
2 3 5
2 5 3
3 4 5
3 5 6
3 6 4
4 6 2
5 6 6
5 1
1 2 2
1 4 8
2 3 3
2 5 5
3 4 2
3 5 6

输出结果

1 2 3 4 5 6
1 2 4 3 5

鸣谢

感谢王道论坛及其产品提供的宝贵建议和测试样例

最后

  • 上述的例子采用了无向网，实际上，边的权值对广度优先搜索的过程和结果无影响，可以忽略不计
  • 给定图的邻接矩阵存储表示是唯一的，故其广度优先生成树也是唯一的，而邻接表存储方式不唯一，故其广度优先生成树也是不唯一的
  • 由于博主水平有限，不免有疏漏之处，欢迎读者随时批评指正，以免造成不必要的误解！