Tag Archives: 邻接表

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

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

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

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

首先定义每个弧如下:

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

next是一条链表,即某个顶点i的所有邻接结点的弧组成。
// Arc
struct Arc
{
int ivex; // The vex position in vexs array
struct Arc* next;
};
然后对于每[......]

继续阅读