C++笔记-基于邻接矩阵的BFS（宽度优先遍历）

ゝ一世哀愁。 2022-10-10 15:54 151阅读 0赞

邻接表是是用一个二维链表，表示顶点和顶点相邻的节点。

而邻接矩阵是，他的行，代表的是顶点，列也代表的顶点，如下：

![20210629084235808.png][]

第0行：这是第0个顶点，他可以去第1个和第2个顶点；

第1行：这是第1个顶点，他可以去第4个顶点；

第2行：这是第2个顶点，他可以去第0个和第2和第3个顶点；

第3行：这是第3个顶点，他可以去第0个和第4个顶点；

第4行，这是第4个顶点，他一个顶点也不能走。

思路BFS都一样，先选一个顶点，然后看他可以访问哪个顶点，然后依次访问：

运行截图：先访问0这个顶点，在1，2，4，3

![2021062908424472.png][]

代码是这样的：

#include <iostream>
    #include <list>
    
    using namespace std;
    
    int am[5][5] = {
    	0, 1, 1, 0, 0,
    	0, 0, 0, 0, 1,
    	1, 0, 1, 1, 0,
    	1, 0, 0, 0, 1,
    	0, 0, 0, 0, 0
    };
    
    //对第几个顶点开始bfs，顶点从0开始
    void bfs(int v) {
    
    	bool visited[5] = { false };
    
    
    	list<int> queue;
    	queue.push_back(v);
    
    
    	while (!queue.empty()) {
    
    		v = queue.front();
    		visited[v] = true;
    		cout << v << " ";
    
    		queue.pop_front();
    
    		//将从v顶点可以走到的顶点，都入队列
    		for (int i = 0; i < 5; i++) {
    
    			if (am[v][i] != 0 && visited[i] != true) {
    
    				queue.push_back(i);
    			}
    		}
    	}
    
    }
    
    void main() {
    
    	bfs(0);
    	getchar();
    }

bfs(0)代表从第0个顶点开始。

[20210629084235808.png]: /images/20221005/a0dddbb4d1f64f34b8a6bbf13904f4ff.png
[2021062908424472.png]: /images/20221005/c477fecf57ea40f1a7d4bbcceef75eae.png