图的表示

算法导论——第22章 图的基本算法

22.1 图的表示

搜索一个图是有序地沿着图的边访问所有节点。图的搜索技术是图算法领域的核心。

要表示一个图G=(V, E)，有两种标准的方法，即邻接表和邻接矩阵。这两种表示方法既可以用于有向图，也可以用于无向图。通常采用邻接表表示法，因为这种方法表示稀疏图（图中|E|远小于|V|*|V|）比较紧凑。但是当遇到稠密图（|E|接近于|V|*|V|）或必须很快判别两个给定定点是否存在连接边时，通常采用邻接矩阵表示法。

图G=(V, E)的邻接表表示由一个包含|V|个列表的数组Adj所组成，其中每个列表对应于V中的一个顶点。对于每一个属于V的u，邻接表Adj[u]包含所有满足条件(u, v)都属于E的顶点v。亦即，Adj[u]包含图G中所有和顶点u相邻的顶点。

如果G是一个有向图，则所有邻接表的长度之和为|E|。如果G是一个无向图，则所有邻接表的长度之和为2|E|。

邻接表稍作变动就能支持其他多种图的变体，因而具有很强的适应性。当然，邻接表表示法也有着潜在的不足之处，即如果要确定图中边(u, v)是否存在，只能在顶点u的邻接表Adj[u]中搜索v，除此之外，没有其他更快的方法。这一不足可以通过图的邻接矩阵表示法来弥补，但要(在渐进意义下)以占用更多的存储空间作为代价。

邻接矩阵所需的存储空间是(V*V)的函数，与图中的边数E是无关的；而邻接矩阵所需的存储空间是(V+E)的函数，与图中的顶点和边数都由关。

无向图的邻接矩阵就是它自己的转置矩阵，在某些应用中，可以只存储邻接矩阵的对角线及对角线以上的部分，这样一来，图所用的存储空间几乎可以减少一半。如果一个图不是加权的，采用邻接矩阵的存储形式还有一个优越性：在存储邻接矩阵的每个元素时，可以只用一个二进制位，而不必用一个字的空间。