Algorithm-算法导论(22.1)：图的表示

杂

对图算法进行讨论需要引入一些约定。
给定 图G = (V, E)
当对此图上的算法的运行时间进行描述时，我们通常以
图的结点数|V| 和 边的条数|E|作为输入规模
仅在渐进记号中可用符号V、E代替
此外，伪码中用G.V表示图G的结点集，G.E表示图G的边集

两种表示方法

邻接链表和邻接矩阵，都可用于表示有向图和无向图。

邻接链表

通常使用邻接链表表示稀疏图，即 |E| << |V|^2 的图。

无论表示有向图还是无向图，邻接链表的存储空间需求都是 Θ(V+E)

邻接链表的一个缺陷是无法快速判断一条 边(u, v)是否存在于图中
唯一的办法是在邻接链表Adj[u]中查找结点v

邻接矩阵

通常使用邻接矩阵表示稠密图。

无论一个图有多少条边，邻接矩阵的存储空间需求都是 Θ(V^2)
在表示无向图时可利用压缩矩阵来存储，其存储空间需求减少为邻接矩阵需求的一半

邻接矩阵克服了上述邻接链表的缺陷，但付出的存储代价增大。

在图规模比较小时，一般用邻接矩阵表示法更优
一是较简单，二是每个记录项仅需1位空间

无向图

以2号结点为例，在图上与1 5 4 3 相连
则邻接链表中，代表2号结点的链表由指向1 5 4 3结点的指针组成
邻接矩阵为对称矩阵
其他类似

所有邻接链表的长度和等于 2|E|，因为每条边都被计算了两次

有向图

以2号结点为例
邻接链表中，边 (2, 5)的5结点出现在2的链表中，而边(4, 2)的2结点会出现在4的链表中
邻接矩阵中，坐标为(2, 5)即代表边(2, 5)
其他类似

所有邻接链表的长度等于|E|，每条边在邻接链表表示法中仅计算一次

权重图

权重图是图中每条边都带有一个相关权重的图

用邻接链表表示时
边(u, v)的权重可以放在u的邻接链表里

用邻接矩阵表示时
边(u, v)的权重可以放在坐标为(u, v)的位置，如不存在则放None或0或…