图的存储

邻接矩阵

其中： 则表示 是图中的一条边。

邻接矩阵的优缺点：

• 适合存放稠密的图，不适合稀疏的图
• 优点：判断两个顶点之间是否存在边
• 缺点：找到一个顶点的所有邻边，需要扫描一行。

邻接矩阵表示法的数量关系：非带权图的邻接矩阵， 表示从顶点 到 长度为 的路径的数目

邻接表

无向图：

• 顶点存放在「顶点表」中，附着在每个顶点上的边以链表「边表」存放
• 每条边出现了2次

有向图：

• 顶点存放在「顶点表」中，从每个顶点发出的边存放在链表「出边表」中
• 计算一个顶点的「入度」非常困难，「逆邻接表」可以补足这个缺点。

邻接表的优缺点：

• 优点：找到一个顶点的所有邻边
• 缺点：判断两个顶点之间是否有边，需要扫描某个顶点的整个「边表」。

十字链表（有向图）

十字链表相当于邻接表和逆邻接表的结合。

• 同一行表示顶点的所有「出边」
• 同一列表示顶点的所有「入边」

通过十字链表，可以很容易求得有向图中一个顶点的「入度」和「出度」。

示意图为：

邻接多重表（无向图）

在邻接表中，每个边需要用两个节点表示；在邻接多重表中，每个边只需要用一个节点表示。
一个顶点的所有边：一个顶点的所有边可能并不在同一行，例如下图顶点 的所有边。但这些边位于同一个链表中。