Tag Archives: 邻接表

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

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

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

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

首先定义每个弧如下:

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

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

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

因此,图可以如下表示:
[[……]

继续阅读