2.2.5 图

图是由结点的有穷集合V和边的集合E组成的。为了与树结构区别，图结构中常常将结点称为顶点，边是顶点的有序偶对。若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。

图可分为有向图和无向图。在有向图中，通常将边称为弧，含箭头的一端称为弧头，另一端称为弧尾，记为<v_i,v_j>，表示从顶点vi到顶点vj有一条边。若有向图中有n个顶点，则最多有n(n-1)条弧。具有n(n-1)条弧的有向图被称为有向完全图。以顶点v为弧尾的弧的数目被称为顶点v的出度，以顶点v为弧头的弧的数目称为顶点v的入度。

在无向图中，边记为(v_i,v_j)，它蕴涵着存在<v_i,v_j>和<v_j, v_i>两条弧。若无向图中有n个顶点，则最多有n(n-1)/2条边。具有n(n-1)/2条边的无向图被称为无向完全图。与顶点v相关的边的条数被称为顶点v的度。

路径长度是指路径上边或弧的数目。若第一个顶点与最后一个顶点相同，则这条路径是一条回路。若路径中顶点没有重复出现，则称这条路径为简单路径。

在无向图中，如果从顶点v_i到顶点v_j有路径，则称v_i和v_j连通。如果图中任意两个顶点之间都连通，则称该图为连通图，否则将其中的极大连通子图称为连通分量。

在有向图中，如果对于每对顶点v_i和v_j，从vi到v_j和从v_j到v_i都有路径，则称该图为强连通图，否则将其中的极大强连通子图称为强连通分量。

图有两种常用的存储结构：邻接矩阵和邻接表。

1．邻接矩阵

邻接矩阵（Adjacency Matrix）的存储结构就是用一维数组存储图中顶点的信息，用矩阵表示图中各顶点之间的邻接关系。假设图G = (V,E)有 n 个确定的顶点，即V={v₀,v₁,…,v_n-1}，则G 中各顶点间的相邻关系表示为一个n×n的矩阵（如图2-22所示），矩阵的元素为

如果矩阵为带权图（即边/弧具有权重等信息，如图2-23所示），则矩阵的元素为

其中，W_ij表示边(vi,vj)或弧<v_i,v_j>上的权值；∞表示一个计算机允许的、大于所有边上权值的数。

从图的邻接矩阵存储方法容易看出这种表示具有以下特点：

① 无向图的邻接矩阵一定是一个对称矩阵。因此，在具体存放邻接矩阵时只需存放上（或下）三角矩阵的元素即可。

② 对于无向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的度TD(v_i)。

③ 对于有向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的出度OD(v_i)（或入度ID(vi)）。

④ 用邻接矩阵方法存储图，容易确定图中任意两个顶点之间是否有边相连；但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。

图邻接矩阵表示法的类型定义如下：

2．邻接表

邻接表（Adjacency List）是图的一种顺序存储与链式存储结合的存储方法，类似树的孩子表示法。对于图G中的每个顶点v_i，将所有邻接于v_i的顶点v_j链成一个单链表，这个单链表就称为顶点v_i的邻接表，再将所有顶点的邻接表表头放到数组中，就构成了图的邻接表。

邻接表中有两种结点结构：一种是顶点表的结点，它由顶点域（vertex）和指向第一条邻接边的指针域（firstedge）构成；另一种是边表（即邻接表）结点，它由邻接点域（adjvex）和指向下一条邻接边的指针域（next）构成。带权图的边表需再增设一个存储边上信息（如权值等）的域（info），如图2-25所示。

图的邻接表的类型定义如下：