数据结构重读 – 图的链式存储(邻接表)和BFS图遍历算法

前面实现的邻接矩阵面临一个巨大的问题:对于稀疏矩阵,将耗费巨大的资源,而大部分都是0。

现实中,绝大多数矩阵都是稀疏的!

我们可以采用如下的邻接表方法存储。

首先定义每个弧如下:

ivex是在顶点在数组中的下标。

next是一条链表,即某个顶点i的所有邻接结点的弧组成。

然后对于每个顶点,定义如下:

因此,图可以如下表示:

以书上的这个图为例:

实际上用邻接表存储是如下效果:

邻接表上很容易找到任意一个顶点的第一个邻接点和下一个。这对于dfs、bfs等遍历很有优势。

但是要判定任意两个顶点vi和vj是否有边或者弧,必须搜索第i个和/或第j个链表,不如邻接矩阵方便。

BFS算法

BFS(Breadth First Search),又叫广度优先搜索。使得“先被访问的顶点的邻接点”限于“后被访问的顶点的邻接点”。

其实就是类似于树中的层次遍历,也是借助队列实现。

例如如下的图:

先访问v1,然后是v1的邻接点v2和v3,然后是v2的邻接点v4, v5,然后v3的邻接点。。。

最终次序:v1 -> v2 -> v3 -> v4 -> v5 -> v6 -> v7 -> v8

伪代码如下:

最终,使用循环队列+邻接表存储+BFS的代码如下:

测试数据:

 

 

 

 

Leave a Reply

Your email address will not be published.