数据结构
无向图G=(V, {E})中从顶点v到顶点v’的路径(Path)是一个顶点序列(v =vi,0,vi,1,…vi,m= v’)，其中(vi,j-1,vi,j) ∈E，1≤j≤m。如果G是有向图，则路径也是有向的，顶点序列应满足
9、连通图、连通分量
在无向图G中，如果从顶点v到顶点v’有路径，则称v和v’是连通的。如果对于图中任意两个顶点vi、vj∈V，vi和vj都是连通的，则称G是连通图(ConnectedGraph)。图7.1(b)中的G2就是一个连通图，而图7.3(a)中的G3则是非连通图，但G3有三个连通分量，如图7.3(b)所示。所谓连通分量(ConnectedComponent)，指的是无向图中的极大连通子图。
图7.3 无向图及其连通分量
在有向图G中，如果对于每一对vi,vj ∈V ，vi!=vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。有向图中的极大强连通子图称作有向图的强连通分量。[例如]图7.1(a)中的G1，不是强连通图，但它有两个强连通分量，如图7.4所示。
10、生成树
一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。图7.5是G3中最大连通分量的一棵生成树。
图7.5 G3的最大连通分量的一棵生成树
一棵有n个顶点的生成树有且仅有n-1条边。如果一个图有n个顶点和小于n-1条边，则是非连通图。如果它多于n-1条边，则一定有环。但是，有n-1条边的图不一定是生成树。
如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1， 则是一棵有向树。一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。
- 11 -
数据结构
图7.6 一个有向图及其生成森林
四、存储结构 1、数组表示法
对于无向图，顶点i的度是邻接矩阵中第i行(或第i列)的元素之和。 对于有向图，第i行的元素之和为顶点vi的出度OD(vi)，第j列的元素之和为顶点vj的入度ID(vj)。 网的邻接矩阵：
2、邻接表
在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边(对有向图是以顶点vi为尾的弧)。
每个结点由三个域组成，其中邻接点域(adjvex)指示与顶点vi邻接的点在图中的位置，链域(nextarc)指示下一条边或弧的结点；数据域(info)存储和边或弧相关的信息，如权值等。
在无向图的邻接表中，顶点vi的度恰为第i个链表中的结点数。
- 12 -
数据结构
而在有向图中，第i个链表中的结点个数只是顶点的出度，为求入度，必须遍历整个邻接表。在所有链表中其邻接点域的值为i的结点的个数是顶点vi的入度。有时，为了便于确定顶点的入度或以顶点vi为头的弧，可以建立一个有向图的逆邻接表，即对每个顶点vi建立一个链接以vi为头的弧的表。
3、十字链表（有向图）
在弧结点中有五个域：其中尾域(tailvex)和头域(headvex)分别指示弧尾和弧头这两个顶点在图中的位置，链域hlink指向弧头相同的下一条弧，而链域tlink指向弧尾相同的下一条弧，info域指向该弧的相关信息。弧头相同的弧在同一链表上，弧尾相同的弧也在同一链表上。
它们的头结点即为顶点结点，它由三个域组成：其中data域存储和顶点相关的信息，如顶点的名称等；firstin和firstout为两个链域，分别指向以该顶点为弧头或弧尾的第一个弧结点。
4、邻接多重表（无向图）
在邻接多重表中，每一条边用一个结点表示，它由如下所示的六个域组成：
其中，mark为标志域，可用以标记该条边是否被搜索过；ivex和jvex为该边依附的两个顶点在图中的位置；ilink指向下一条依附于顶点ivex的边；jlink指向下一条依附于顶点 jvex的边，info为指向和边相关的各种信息的指针域。每一个顶点也用一个结点表示，它由如下所示的两个域组成：
其中，data域存储和该顶点相关的信息，firstedge域指示第一条依附于该顶点的边。[例如]无向图G2的邻接多重表。
五、图的遍历
图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。 深度优先搜索和广度优先搜索。对无向图和有向图都适用。 1、深度优先搜索（类似于树的先根遍历）
从某个顶点v出发，依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
无向图G4，假设从顶点v1出发进行搜索。过程如图：
- 13 -
数据结构
2、广度优先搜索（类似于树的按层次遍历）
从图中某顶点v出发，在访问v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。换句话说，广度优先搜索遍历图的过程是以v为起始点，由近至远，依次访问和v有路径相通且路径长度为1，2，…的顶点。
对图G4进行广度优先搜索遍历的过程如图7.13(c)所示，首先访问v1和v1的邻接点v2和v3，然后依次访问v2的邻接点v4和v5及v3的邻接点v6和v7，最后访问v4的邻接点v8。由于这些顶点的邻接点均已被访问，并且图中所有顶点都被访问，由此完成了图的遍历。得到的顶点访问序列为：
v1->v2->v3->v4->v5->v6->v7->v8
- 14 -