图
图（ Graph）是一种较线性表和树更为复杂的非线性结
构。在线性结构中，结点之间的关系是线性关系，除开
始结点和终端结点外，每个结点只有一个直接前趋和直
接后继。在树形结构中，结点之间的关系实质上是层次
关系，同层上的每个结点可以和下一层的零个或多个结
点（即孩子）相关，但只能和上一层的一个结点（即双
亲）相关（根结点除外）。然而在图结构中，对结点
（图中常称为顶点）的前趋和后继个数都是不加限制的，
即结点之间的关系是任意的。图中任意两个结点之间都
可能相关。由此，图的应用极为广泛，特别是近年来的
迅速发展，已渗透到诸如语言学、逻辑学、物理、化学、
电讯工程、计算机科学以及数学的其它分支中。
基本定义和术语
? 若图 G中的每条边都是有方向的，则称 G为 有向图
（ Digraph）。在有向图中，一条有向边是由两个顶点
组成的有序对，有序对通常用尖括号表示。例如，＜ vi，
vj＞表示一条有向边,vi是边的始点（起点）,vj是边
的终点。因此，＜ vi,vj＞和＜ vj,vi＞是两条不同的有
向边。有向边也称为弧（ Arc），边的始点称为弧尾
（ Tail），终点称为弧头（ Head）。
? 图 G由两个集合 V和 E组成，记为 G＝ (V,E)，其中 v是
顶点的有穷非空集合,E是 V中顶点偶对（称为边）的
有穷集。通常，也将图 G的顶点集和边集分别记为 V(G)
和 E(G)。 E(G)可以是空集，若 E(G)为空，则图 G只有顶
点而没有边，称为空图。
若 (vi,vj)是一条无向边，则称顶点 vi和 vj互为 邻接点
(Adjacent)，或称 vi和 vj相邻接；称 (vi,vj)关联 (Incident)
于顶点 vi和 vj，或称 (vi,vj)与顶点 vi和 vj相关联 。如图 7-
1中 G2，与顶点 vl相邻接的顶点是 v2,v3和 v4，而关联于
顶点 v2的边是 (vl,v2),(v2,v3)和 (v2,v4)。若＜ vi,vj
＞是一条有向边，则称顶点 vi邻接到 vj,顶点 vj邻接于顶
点 vi,并称边＜ vi,vj＞关联于 vi和 vj或称＜ vi,vj＞与顶
点 vi和 vj相关联。如图 7-1中 Gl，关联于顶点 v2的边是＜
v1,v2＞，＜ v2,vl＞和＜ v2,v3＞。
无向图中顶点 v的 度 (Degree)是关联于该顶点的边的数
目，记为 D(v)。若 G为有向图，则把以顶点 v为终点的
边的数目，称为 v的 人度 (1ndegree)，记为 ID(v)；把以
顶点 v为始点的边的数目，称为 v的 出度 (outdegree)，记
为 OD(v)；顶点 v的度则定义为该顶点的入度和出度之
和，即 D(v)＝ ID(v)十 OD(v)。
在无向图 G中，若存在一个顶点序列 vp,vi1,vi2…, vin,vq，
使得 (vp,vil),(vi1,vi2),…, (vin,vq)均属于 E(G)，则
称顶点 vp到 vq存在一条 路径 (Path)。若 G是有向图，则
路径也是有向的，它由 E(G)中的有向边＜ vp,vil＞，＜
vil,vi2＞,…,＜ vin,vq＞组成。 路径长度 定义为该路
径上边的数目。若一条路径上除了 vp和 vq可以相同外；
其余顶点均不相同，则称此路径为一条 简单路径 。起
点和终点相同 (vp＝ vq)的简单路径称为 简单回路 或 简单
环 (Cycle)。例如，在图 G2中顶点序列 vl,v2,v3,v4是一
条从顶点 vl到顶点 v4的长度为 3的简单路径；顶点序列
vl,v2,v4,vl,v3是一条从顶点 vl到顶点 v3的长度为 4的
路径，但不是简单路径；顶点序列 vl,v2,v4,vl是一
个长度为 3的简单环。在有向图 Gl中，顶点序列 vl,v2，
vl是一个长度为 2的有向简单环。
在一个有向图中，若存在一个顶点 v，从该顶点有路径可以到达图中
其它所有顶点，则称此有向图为 有根图, v称作图的 根 。
在无向图 G中，若从顶点 vi到顶点 vj有路径 (当然从 vj到 vi也一定有路
径 )，则称 vi和 vj是 连通 的。若 V(G)中任意两个不同的顶点 vi和 vj都
连通 (即有路径 )，则称 G为 连通图 (Connected Graph)。例如，图 G2
和 G3是连通图。
无向图 G的极大连通子图称为 G的 连通分量 (connected Component)。
显然，任何连通图的连通分量只有一个，即是其自身，而非连通
的无向图有多个连通分量。例如，图 7-4中的 G4是非连通图，它有
两个连通分量 Hl和 H2。
在有向图 G中，若对于 V(G)中任意两个不同的顶点 vi和 vj，都存在
从 vi到 vj以及从 vj到 vi的路径，则称 G是 强连通图 。有向图 G的极大
强连通子图称为 G的 强连通分量 。显然，强连通图只有一个强连
通分量，即是其自身。非强连通的有向图有多个强连通分量。例
如图 7-1中的 Gl不是强连通图，因为 v3到 v2没有路径，但它有两个
强连通分量，
若将图的每条边都赋上一个权，则称这种带权图为 网
络 (Network)。通常权是具有某种意义的数,
它们可以表示两个顶点
之间的距离，耗费等
图的存储结构
? 邻接矩阵 (Adjacency
Matrix)是表示顶点之
间相邻关系的矩阵 。
设 G＝ (V,E)是具有 n
个顶点的图, 则 G的
邻接矩阵是具有如下
性质的 n阶方阵：
? ? ??? ?? ??? ）中的边（不是）或：若（ ）中的边（是）或：若（ GEvvvv GEvvvv jiji jiji,,0,,1ji,A
? 用邻接矩阵表示法表示图, 除了存储用于表示顶点间
相邻关系的邻接矩阵外, 通常还需要用一个顺序表来
存储顶点信息 。 其形式说明如下：
? # define n 6 / * 图的顶点数 * /
? # define e 8 / * 图的边 （ 弧 ） 数 */
? typedef char vextype； / * 顶点的数据类型 * /
? typedef float adjtype； / * 权值类型 * /
? typedef struct
? {vextype vexs[n]；
? adjtype arcs[n][n]；
? }graph；
? 若图中顶点信息是 0至 n-1的编号, 则仅需令权值为 1,存储一个邻接矩阵就可以表
示图 。 若是网络, 则 adjtype为权的类型 。 由于无向图或无向网络的邻接矩阵是对
称的, 故可采用压缩存储的方法, 仅存储下三角阵 (不包括对角线上的元素 )中的
元素即可 。 显然, 邻接矩阵表示法的空间复杂度 S(n)＝ O(n2)。
? CREATGRAPH(ga) ／ * 建立无向网络 * ／
? Graph * ga；
? {
? int i,j,k；
? float w；
? for(i＝ 0； i＜ n； i++)
? ga ->vexs[i]＝ getchar()；／ * 读入顶点信息, 建立顶点表 *／
? for(i＝ 0； i＜ n； i++)
? for(j＝ 0； j＜ n； j++)
? ga ->arcs[i][j]＝ 0； ／ * 邻接矩阵初始化 *／
? for(k＝ 0； k＜ e； k++) ／ * 读入 e条边 *／
? (scanf(”％ d％ d％ f”,&I,&j,&w)；／ *读入边 (vi,vj)上的权 w *／
? ga ->arcs[i][j]＝ w；
? ga - >arcs[j][i]＝ w；
? }
? }／ *CREATGRAPH *／
? 该算法的执行时间是 O(n+n2+e),其中 O(n2)的时问耗费在邻接矩阵的初始化操作上 。
因为 e＜ n2,所以, 算法的时间复杂度是 O(n2)。
邻接表
这种表示法类似于树的孩子链表表示法 。
对于图 G中的每个顶点 vi，该方法把所有邻接于 vi的顶
点 vj链成一个单链表，这个单链表就称为顶点 vi的邻接
表 (Adjacency List)。邻接表中每个表结点均有两个域，
其一是邻接点域 (Adjvex)，用以存放与 vi相邻接的顶点
vj的序号；其二是链域 (Next)，用来将邻接表的所有表
结点链在一起。并且为每个顶点 vi的邻接表设置一个具
有两个域的表头结点：一个是顶点域 (vertex)，用来存
放顶点 vi的信息；另一个是指针域 (Link)，用于存入指
向 vi的邻接表中第一个表结点的头指针。为了便于随机
访问任一顶点的邻接表，将所有邻接表的表头结点顺
序存储在一个向量中，这样，图 G就可以由这个表头向
量来表示。
建立有向图的邻接表与此类似，只是更加简单，
每读入一个顶点对序号＜ i,j＞时，仅需生成
十个邻接点序号为 j的边表结点，将其插入到 vi
的出边表头部即可。若建立网络的邻接表，则
需在边表的每个结点中增加一个存储边上权的
数据域。
值得注意的是，一个图的邻接矩阵表示是唯一
的，但其邻接表表示不唯一，这是因为邻接表
表示中，各边表结点的链接次序取决于建立邻
接表的算法以及边的输入次序。
邻接矩阵和邻接表是图的两种最常用的存储结
构，它们各有所长。下面从空间及执行某些常
用操作的时间这两方面来作一比较。
在邻接表 (或逆邻接表 )表示中，每个边表对应于
邻接矩阵的一行 (或一列 )，边表中结点个数等
于一行 (或一列 )中非零元素的个数。对于一个
具有 n个顶点 e条边的图 G，若 G是无向图，则
它的邻接表表示中有 n个顶点表结点和 2e个边
表结点；若 G是有向图，则它的邻接表表示或
逆邻接表表示中均有 n个顶点表结点和 e个边表
结点。因此邻接表或逆邻接表表示的空间复杂
度为 S(n,e)＝ O(n+e)。若图中边的数目远远小
于 n2(即 e＜＜ n2)，此类图称作稀疏图 (Sparse
Graph)，这时用邻接表表示比用邻接矩阵表示
节省存储空间；若 e接近于 n2 (准确地说，无向
图 e接近于 n(n-1)／ 2，有向图 e接近于 n(n-1))，
此类图称作稠密图 (Dense Graph)，考虑到邻接
表中要附加链域，则应取邻接矩阵表示法为宜。
在无向图中求顶点的度, 邻接矩阵及邻接表两种存储结构都很容易
做到：邻接矩阵中第 i行 (或第 i列 )上非零元素的个数即为顶点 vi的
度；在邻接表表示中, 顶点 vi的度则是第 i个边表中的结点个数 。
在有向图中求顶点的度 。 采用邻接矩阵表示比邻接表表示更方便：
邻接矩阵中的第 i行上非零元素的个数是顶点 vi的出度 OD(vi),第 i
列上非零元素的个数是顶点 vi的入度 ID(vi),顶点 vi的度即是二者
之和；在邻接表表示中, 第 i个边表 (即出边表 )上的结点个数是顶
点 vi的出度, 求 vi的入度较困难, 需遍历各顶点的边表 。 若有向图
采用逆邻接表表示, 则与邻接表表示相反, 求顶点的入度容易,
而求顶点出度较难 。
在邻接矩阵表示中, 很容易判定 (vi,vj)或＜ vi,vj＞是否是图的一
条边, 只要判定矩阵中的第 i行第 j列上的那个元素是否为零即可；
但是在邻接表表示中, 需扫描第 i个边表, 最坏情况下要耗费 O(n)
时间 。
在邻接矩阵中求边的数目 e，必须检测整个矩阵，所耗费的时间是
0(n2)，与 e的大小无关；而在邻接表表示中，只要对每个边表的结
点个数计数即可求得 e，所耗费的时间是 0(e+n)。因此，当 e＜＜ n2
时，采用邻接表表示更节省时间。
图的遍历
和树的遍历类似，图的遍历也是从某个顶点出发，
沿着某条搜索路径对图中所有顶点各作一次访
问。若给定的图是连通图，则从图中任一顶点
出发顺着边可以访问到该图的所有顶点。然而，
图的遍历比树的遍历复杂得多，这是因为图中
的任一顶点都可能和其余顶点相邻接，故在访
问了某个顶点之后，可能顺着某条回路又回到
了该顶点。为了避免重复访问同一个顶点，必
须记住每个顶点是否被访问过。为此，可设置
一个布尔向量 visited[n]，它的初值为 false，一
旦访问了顶点 vi，便将 visited[i-1]置为 TRUE。
深度优先搜索 (Depth-First-Search)遍历类似于树的前序遍历。假设给
定图 G的初态是所有顶点均未访问过，在 G中任选一顶点 vi为初始
出发点，则深度优先搜索可定义如下：首先，访问出发点 vi，并
将其标记为已访问过，然后，依次从 vi出发搜索 vi的每一个邻接点
vj,若 vj未曾访问过，则以 vj为新的出发点继续进行深度优先搜索。
显然上述搜索法是递归定义的，它的特点是尽可能先对纵深方向
进行搜索，故称之为深度优先搜索。例如，设 x是刚访问过的顶点，
按深度优先搜索方法，下一步将选择一条从 x出发的未检测过的边
(x,y)。若发现顶点 y已被访问过，则重新选择另一条从 x出发的
未检测过的边。若发现顶点 y未曾访问过，则沿此边从 x到达 y，访
问 y并将其标记为已访问过，然后从 y开始搜索，直到搜索完从 y出
发的所有路径，才回溯到顶点 x，然后再选择一条从 x出发的未检
测过的边。上述过程直至从 x出发的所有边都已检测过为止。此时，
若 x不是初始出发点，则回溯到在 x之前被访问过的顶点；若 x是初
始出发点，则整个搜索过程结束。显然这时图 G中所有和初始出
发点有路径相通的顶点都已被访问过。因此，若 G是连通图，则
从初始出发点开始的搜索过程结束，也就意味着完成了对图 G的
遍历。
在该存储结构上执行 DFS算法的过程如下：设初始出发点是 v1，则
DFS（ 0）的执行结果是访问 v1，将其置上已访问标记，从 v1搜索
到的第 1个邻接点是 v2，因 v2未曾访问过，故调用 DFS(1)。执行
DFS(1)，首先访问 v2，将其标记为已访问过，然后从 v2搜索到的
第 1个邻接点是 vl，但 vl已访问过，故继续搜索到第 2个邻接点 v4，
v4未曾访过，因此调用 DFS(3)。类似地分析，访问 v4后调用
DFS(7)，访问 v：后调用 DPS(4)。执行 DFS(4)时，在访问 v5并作标
记后，从 v5搜索到的两个邻接点依次是 v2和 v8，因为它们均已被访
问过，所以 DFS(4)执行结束返回，回溯到 v8。又因为 v8的两个邻
接点已搜索过，故 DFS(7)亦结束返回，回溯到 v4。类似地由 v4回
溯到 v2。 V2的邻接点 vl和 v4已搜索过，但 v2的第 3个邻接点 v5还尚
未搜索，故接下来由 v2搜索到 v5，但因为 v5已访问过，所以 DFS(1)
也结束返回，回溯到 vl。 vl的第 1个邻接点已搜索过，故继续从 v1
搜索到第 2个邻接点 v3，因为 v3未曾访问过，故调用 DFS(2)。类似
地依次访问 v3,v6,v7后，又由 v7依次回溯到 v6,v3,vl。此时,vl
的所有邻接点都已搜索过，故 DFS(0)执行完毕。
宽度优先搜索法
宽度优先搜索 (Breadth-First-Search)遍历类似于树的按层次遍历 。 设
图 G的初态是所有顶点均未访问过, 在 G中任选一顶点 2为初始出
发点, 则宽度优先搜索的基本思想是：首先访问出发点 Vi,接着
依次访问 vi的所有邻接点 wl,w2,…, wt,然后, 再依次访问与 wl，
w2,…, wt邻接的所有未曾访问过的顶点, 依此类推, 直至图中
所有和初始出发点 v有路径相通的顶点都已访问到为止 。 此时, 从
vi开始的搜索过程结束, 若 G是连通图则遍历完成 。
显然，上述搜索法的特点是尽可能先对横向进行搜索，故称之为
宽度优先搜索。设 x和 y是两个相继被访问过的顶点，若当前是以 x
为出发点进行搜索，则在访问 x的所有未曾访问过的邻接点之后，
紧接着是以 y为出发点进行横向搜索，并对搜索到的 y的邻接点中
尚未被访问的顶点进行访问。也就是说，先访问的顶点其邻接点
亦先被访问。为此，需引进队列保存已访问过的顶点。
最小生成树
图的生成树不是唯一的, 从不同的顶点出发进行遍历,
可以得到不同的生成树 。 对于连通网络 G＝ (V,E),边
是带权的, 因而 G的生成树的各边也是带权的 。 我们把
生成树各边的权值总和称为生成树的权, 并把权最小
的生成树称为 G的 最小生成树 (Minimun Spanning Tree)。
生成树和最小生成树有许多重要的应用。令图 G的顶点
表示城市，边表示连接两个城市之间的通讯线路。 n个
城市之间最多可设立的线路有 n(n-1)／ 2条，把 n个城市
连接起来至少要有 n-1条线路，则图 G的生成树表示了
建立通讯网络的可行方案。如果给图中的边都赋予权，
而这些权可表示两个城市之间通讯线路的长度或建造
代价，那么，如何选择 n-1条线路，使得建立的通讯网
络其线路的总长度最短或总代价最小呢?这就是要构造
该图的一棵最小生成树。
以下我们只讨论无向图的最小生成树问题。构造最小生
成树可以有多种算法，其中大多数构造算法都是利用
了最小生成树的下述性质：设 G＝ (V,E)是一个连通网
络,U是顶点集 V的一个真子集。若 (u,v)是 G中所有
的一个端点在 U(即 u∈ U)里、另一个端点不在 U(即
v∈ V-U)里的边中，具有最小权值的一条边，则一定存
在 G的一棵最小生成树包含此边 (u,v)。这个性质称为
MST性质。 MST性质可用反证法证明：假设 G的任何
一棵最小生成树中都不含边 (u,v)。设 T是 G的一棵最
小生成树，但不包含边 (u,v)。由于 T是树，且是连通
的，因此有一条从 u到 v的路径；且该路径上必有一条
连接两个顶点集 U和 V-U的边 (u′,v′)，其中 u′∈ U，
v′∈ V-U，否则 u和 v不连通。当把边 (u,v)加入树 T时，
得到一个含有边 (u,v)的回路，见图 7-15。删去边 (u′，
v′)，上述回路即被消除，由此得到另一棵生成树 T′,T′
和 T的区别仅在于用边 (u,v)取代了 T中的边 (u′,v′)。
因为 (u,v)的权＜ (u′,v′)的权，故 T′的权＜ T的权，因
此 T′也是 G的最小生成树，它包含边 (u,v)，与假设矛
盾 !
假设 G＝ (V,E)是连通网络, 为简单起见, 我们用序号 1至 n来表示
顶点集合, 即 v＝ {1,2,…, n}。 设所求的最小生成树为 T＝ (U，
TE),其中 U是 T的顶点集, TE是 T的边集 。 并且将 G中边上的权看
做是长度 。
Prim算法的基本思想是：首先从 v中任取一个顶点 u0,将生成树 T
置为仅有一个结点 u0的树, 即置 U＝ {u0}；然后只要 U是 V的真子
集, 就在所有那些其一个端点 u己在 T(即 u∈ U),另一个端点 v还未
在 T(即 v∈ V— U)的边中, 找一条最短 (即权最小 )的边 (u,v),并
把该条边 (u,v)和其不在 T中的顶点 v,分别并入 T的边集 TE和顶
点集 U。 如此进行下去, 每次往生成树里并入一个顶点和一条边,
直到把所有顶点都包括进生成树 T为止 。 此时, 必有 U＝ V,TE中
有 n-1条边 。 MST性质保证上述过程求得的 T＝ (U,TE)是 G的一棵
最小生成树 。
显然,Prim算法的关键是如何找到连接 U和 V-U的最短边来扩充生
成树 T。为直观解释方便，设想在构造过程中,T的顶点集 U中顶
点和边集 TE中的边均被涂成红色,U之外的顶点集 V-U中的顶点
均被涂成蓝色，连接红点和蓝点的边均被涂成紫色，那么．最短
紫边就是连接 U和 V-U的最短边。
最短路径
交通网络中常常提出这样的问题：从甲地到乙地之间是
否有公路连通?在有多条通路的情况下, 哪一条路最短?
交通网络可用带权图来表示 。 顶点表示城市名称, 边
表示两个城市有路连通, 边上权值可表示两城市之间
的距离, 交通费或途中所花费的时间等 。 求两个顶点
之间的最短路径, 不是指路径上边数之和最少, 而是
指路径上各边的权值之和最小 。
另外，若两个顶点之间没有边，则认为两个顶点无通路，
但有可能有间接通路（从其他顶点达到 )）。路径上的
开始顶点 (出发点 )称为源点，路径上的最后一个顶点称
为终点，并假定讨论的权值不能为负数。
所有顶点对之间的最短路径
所有顶点对之间的最短路径是指：对于给
定的有向网 G=(V,E)，要对 G中任意一对
顶点有序对 V,W(V≠W)，找出 V到 W的
最短距离和 W到 V的最短距离。解决此问
题的一个有效方法是,轮流以每一个顶点
为源点，重复执行迪杰斯特拉算法 n次，
即可求得每一对顶点之间的最短路径,总
的时间复杂度为 O(n3)。
弗洛伊德算法 仍然使用 前面定义的 图的邻接 矩阵
cost[n+1][n+1]来存储带权有向图 。 算法的基本思想是,
设置一个 nxn的矩阵 A(k),其中除对角线的元素都等于 0
外, 其他元素 a(k)[i][j]表示顶点 i到顶点 j的路径长度, K
表示运算步骤 。 开始时, 以任意两个顶点之间的有向
边的权值作为路径长度, 没有有向边时, 路径长度为 ∞，
当 K=0时, A (0)[i][j]=arcs[i][j],
以后逐步尝试在原路径中加入其他顶点作为中间顶点，
如果增加中间顶点后，得到的路径比原来的路径长度
减少了，则以此新路径代替原路径，修改矩阵元素。
具体做法为：第一步，让所有边上加入中间顶点 1，取
A[i][j]与 A[i][1]+A[1][j]中较小的值作 A[i][j]的值，完成
后得到 A(1)，第二步，让所有边上加入中间顶点 2，取
A[i][j]与 A[i][2]+A[2][j]中较小的值，完成后得到 A(2)…,
如此进行下去，当第 n步完成后，得到 A(n),A(n)即为我
们所求结果,A(n)[i][j]表示顶点 i到顶点 j的最短距离。
拓扑排序
通常我们把计划、施工过程、生产流程、程序流程等都
当成一个工程，一个大的工程常常被划分成许多较小
的子工程，这些子工程称为活动，这些活动完成时，
整个工程也就完成了。例如，计算机专业学生的课程
开设可看成是一个工程，每一门课程就是工程中的活
动，图 7-24给出了若干门所开设的课程，其中有些课
程的开设有先后关系，有些则没有先后关系，有先后
关系的课程必须按先后关系开设，如开设数据结构课
程之前必须先学完程序设计基础及离散数学，而开设
离散数学则必须学完高等数学。在图 7-24（ b）中，我
们用一种有向图来表示课程开设，在这种有向图中，
顶点表示活动，有向边表示活动的优先关系，这有向
图叫做顶点表示活动的网络 (Active On Vertices)简称为
AOV网。
在 AOV网中,<i,j>有向边表示 i活动应先于 j活动开始，即
i活动必须完成后,j活动才可以开始，并称 i为 j的直接
前驱,j为 i的直接后继。这种前驱与后继的关系有传递
性，此外，任何活动 i不能以它自己作为自己的前驱或
后继，这叫做反自反性。从前驱和后继的传递性和反
自反性来看,AOV网中不能出现有向回路（或称有向
环）。在 AOV网中如果出现了有向环，则意味着某项
活动应以自己作为先决条件，这是不对的，工程将无
法进行。对程序流程而言，将出现死循环。因此，对
给定的 AOV网，应先判断它是否存在有向环。判断
AOV网是否有有向环的方法是对该 AOV网进行拓扑排
序，将 AOV网中顶点排列成一个线性有序序列，若该
线性序列中包含 AOV网全部顶点，则 AOV网无环，否
则,AOV网中存在有向环，该 AOV网所代表的工程是
不可行的。
本章小结
图是一种复杂的非线性结构, 具有广泛的应用背景 。 本章涉及到的基本概念有：
图,由两个集合 V和 E组成, 记为 G＝ (V,E),其中 v是顶点的有穷非空集合, E是 V中
顶点偶对 （ 称为边 ） 的有穷集 。 通常, 也将图 G的顶点集和边集分别记为 V(G)和
E(G)。 E(G)可以是空集, 若 E(G)为空, 则图 G只有顶点而没有边, 称为空图 。
有向图 （ Digraph）,若图 G中的每条边都是有方向的, 则称 G为有向图 。
无向图 （ Undigraph）, 若图 G中的每条边都是没有方向的, 则称 G为无向图 。
无向完全图 (Undirected Complete Graph),恰好有 n(n-1)／ 2条边的无向图称为无向完
全图 。
有向完全图 (DirectedComplete Graph)：恰有 n(n-1)条边的有向图称为有向完全图 。
邻接点 (Adjacent)：若 (vi,vj)是一条无向边, 则称顶点 vi和 vj互为邻接点 。
度 (Degree)：无向图中顶点 v的度是关联于该顶点的边的数目 。
人度 (1ndegree)若 G为有向图, 则把以顶点 v为终点的边的数目, 称为 v的人度, 记为
ID(v)。
出度 (outdegree)：把以顶点 v为始点的边的数目, 称为 v的出度, 记为 OD(v)。
子图 (Subgraph)：设 G＝ (V,E)是一个图，若 v′ 是 v的子集,E′ 是 E的子集，且 E′
中的边所关联的顶点均在 v′ 中，则 G′ ＝ (V′, E′ )也是一个图，并称其为 G的
子图。
路径 (Path)：在无向图 G中, 若存在一个顶点序列 vp,vi1,vi2…, vin,vq, 使得 (vp,vil)，
(vi1,vi2),…, (vin,vq)均属于 E(G),则称顶点 vp到 vq存在一条路径 。
路径长度,该路径上边的数目 。
简单路径,若一条路径上除了 vp和 vq可以相同外, 其余顶点均不相同, 则称此路径为一条简单路
径 。
简单回路或简单环 (Cycle)：起点和终点相同 (vp＝ vq)的简单路径称为简单回路或简单环 。
有根图,在一个有向图中, 若存在一个顶点 v,从该顶点有路径可以到达图中其它所有顶点, 则称
此有向图为有根图, v称作图的根 。
连通,在无向图 G中, 若从顶点 vi到顶点 vj有路径 (当然从 vj到 vi也一定有路径 ),则称 vi和 vj是连通
的 。
连通图 (Connected Graph)：若 V(G)中任意两个不同的顶点 vi和 vj都连通 (即有路径 ),则称 G为连通
图 。
连通分量 (connectedComponent)：无向图 G的极大连通子图称为 G的连通分量 。
强连通图,在有向图 G中, 若对于 V(G)中任意两个不同的顶点 vi和 vj,都存在从 vi到 vj以及从 vj到 vi
的路径, 则称 G是强连通图 。
强连通分量,有向图 G的极大强连通子图称为 G的强连通分量 。
网络 (Network)：若将图的每条边都赋上一个权, 则称这种带权图为网络 。
生成树 (Spanning Tree)：连通图 G的一个子图如果是一棵包含 G的所有顶点的树, 则该子图称为 G
的生成树 。
最小生成树 (MinimunSpanning Tree)：权最小的生成树称为 G的最小生成树 。
本章在介绍图的基本概念的基础上, 还介绍了图的两种常用的存储结构, 对图的遍历, 最小生成
树等问题做了较详细的讨论, 给出了相应的求解算法, 有的算法采用自顶向下, 逐步求精的
方法加以介绍, 也许能便于读者理解它们 。
相对而言之，图这一章内容较难，尤其是离散数学基础较差的读者，也许难度更大些。建议读者
知难而进，理解本章所介绍的算法实质，掌握图的有关术语和存储表示。面对实际问题时，
学会引用本章的有关内容。
图（ Graph）是一种较线性表和树更为复杂的非线性结
构。在线性结构中，结点之间的关系是线性关系，除开
始结点和终端结点外，每个结点只有一个直接前趋和直
接后继。在树形结构中，结点之间的关系实质上是层次
关系，同层上的每个结点可以和下一层的零个或多个结
点（即孩子）相关，但只能和上一层的一个结点（即双
亲）相关（根结点除外）。然而在图结构中，对结点
（图中常称为顶点）的前趋和后继个数都是不加限制的，
即结点之间的关系是任意的。图中任意两个结点之间都
可能相关。由此，图的应用极为广泛，特别是近年来的
迅速发展，已渗透到诸如语言学、逻辑学、物理、化学、
电讯工程、计算机科学以及数学的其它分支中。
基本定义和术语
? 若图 G中的每条边都是有方向的，则称 G为 有向图
（ Digraph）。在有向图中，一条有向边是由两个顶点
组成的有序对，有序对通常用尖括号表示。例如，＜ vi，
vj＞表示一条有向边,vi是边的始点（起点）,vj是边
的终点。因此，＜ vi,vj＞和＜ vj,vi＞是两条不同的有
向边。有向边也称为弧（ Arc），边的始点称为弧尾
（ Tail），终点称为弧头（ Head）。
? 图 G由两个集合 V和 E组成，记为 G＝ (V,E)，其中 v是
顶点的有穷非空集合,E是 V中顶点偶对（称为边）的
有穷集。通常，也将图 G的顶点集和边集分别记为 V(G)
和 E(G)。 E(G)可以是空集，若 E(G)为空，则图 G只有顶
点而没有边，称为空图。
若 (vi,vj)是一条无向边，则称顶点 vi和 vj互为 邻接点
(Adjacent)，或称 vi和 vj相邻接；称 (vi,vj)关联 (Incident)
于顶点 vi和 vj，或称 (vi,vj)与顶点 vi和 vj相关联 。如图 7-
1中 G2，与顶点 vl相邻接的顶点是 v2,v3和 v4，而关联于
顶点 v2的边是 (vl,v2),(v2,v3)和 (v2,v4)。若＜ vi,vj
＞是一条有向边，则称顶点 vi邻接到 vj,顶点 vj邻接于顶
点 vi,并称边＜ vi,vj＞关联于 vi和 vj或称＜ vi,vj＞与顶
点 vi和 vj相关联。如图 7-1中 Gl，关联于顶点 v2的边是＜
v1,v2＞，＜ v2,vl＞和＜ v2,v3＞。
无向图中顶点 v的 度 (Degree)是关联于该顶点的边的数
目，记为 D(v)。若 G为有向图，则把以顶点 v为终点的
边的数目，称为 v的 人度 (1ndegree)，记为 ID(v)；把以
顶点 v为始点的边的数目，称为 v的 出度 (outdegree)，记
为 OD(v)；顶点 v的度则定义为该顶点的入度和出度之
和，即 D(v)＝ ID(v)十 OD(v)。
在无向图 G中，若存在一个顶点序列 vp,vi1,vi2…, vin,vq，
使得 (vp,vil),(vi1,vi2),…, (vin,vq)均属于 E(G)，则
称顶点 vp到 vq存在一条 路径 (Path)。若 G是有向图，则
路径也是有向的，它由 E(G)中的有向边＜ vp,vil＞，＜
vil,vi2＞,…,＜ vin,vq＞组成。 路径长度 定义为该路
径上边的数目。若一条路径上除了 vp和 vq可以相同外；
其余顶点均不相同，则称此路径为一条 简单路径 。起
点和终点相同 (vp＝ vq)的简单路径称为 简单回路 或 简单
环 (Cycle)。例如，在图 G2中顶点序列 vl,v2,v3,v4是一
条从顶点 vl到顶点 v4的长度为 3的简单路径；顶点序列
vl,v2,v4,vl,v3是一条从顶点 vl到顶点 v3的长度为 4的
路径，但不是简单路径；顶点序列 vl,v2,v4,vl是一
个长度为 3的简单环。在有向图 Gl中，顶点序列 vl,v2，
vl是一个长度为 2的有向简单环。
在一个有向图中，若存在一个顶点 v，从该顶点有路径可以到达图中
其它所有顶点，则称此有向图为 有根图, v称作图的 根 。
在无向图 G中，若从顶点 vi到顶点 vj有路径 (当然从 vj到 vi也一定有路
径 )，则称 vi和 vj是 连通 的。若 V(G)中任意两个不同的顶点 vi和 vj都
连通 (即有路径 )，则称 G为 连通图 (Connected Graph)。例如，图 G2
和 G3是连通图。
无向图 G的极大连通子图称为 G的 连通分量 (connected Component)。
显然，任何连通图的连通分量只有一个，即是其自身，而非连通
的无向图有多个连通分量。例如，图 7-4中的 G4是非连通图，它有
两个连通分量 Hl和 H2。
在有向图 G中，若对于 V(G)中任意两个不同的顶点 vi和 vj，都存在
从 vi到 vj以及从 vj到 vi的路径，则称 G是 强连通图 。有向图 G的极大
强连通子图称为 G的 强连通分量 。显然，强连通图只有一个强连
通分量，即是其自身。非强连通的有向图有多个强连通分量。例
如图 7-1中的 Gl不是强连通图，因为 v3到 v2没有路径，但它有两个
强连通分量，
若将图的每条边都赋上一个权，则称这种带权图为 网
络 (Network)。通常权是具有某种意义的数,
它们可以表示两个顶点
之间的距离，耗费等
图的存储结构
? 邻接矩阵 (Adjacency
Matrix)是表示顶点之
间相邻关系的矩阵 。
设 G＝ (V,E)是具有 n
个顶点的图, 则 G的
邻接矩阵是具有如下
性质的 n阶方阵：
? ? ??? ?? ??? ）中的边（不是）或：若（ ）中的边（是）或：若（ GEvvvv GEvvvv jiji jiji,,0,,1ji,A
? 用邻接矩阵表示法表示图, 除了存储用于表示顶点间
相邻关系的邻接矩阵外, 通常还需要用一个顺序表来
存储顶点信息 。 其形式说明如下：
? # define n 6 / * 图的顶点数 * /
? # define e 8 / * 图的边 （ 弧 ） 数 */
? typedef char vextype； / * 顶点的数据类型 * /
? typedef float adjtype； / * 权值类型 * /
? typedef struct
? {vextype vexs[n]；
? adjtype arcs[n][n]；
? }graph；
? 若图中顶点信息是 0至 n-1的编号, 则仅需令权值为 1,存储一个邻接矩阵就可以表
示图 。 若是网络, 则 adjtype为权的类型 。 由于无向图或无向网络的邻接矩阵是对
称的, 故可采用压缩存储的方法, 仅存储下三角阵 (不包括对角线上的元素 )中的
元素即可 。 显然, 邻接矩阵表示法的空间复杂度 S(n)＝ O(n2)。
? CREATGRAPH(ga) ／ * 建立无向网络 * ／
? Graph * ga；
? {
? int i,j,k；
? float w；
? for(i＝ 0； i＜ n； i++)
? ga ->vexs[i]＝ getchar()；／ * 读入顶点信息, 建立顶点表 *／
? for(i＝ 0； i＜ n； i++)
? for(j＝ 0； j＜ n； j++)
? ga ->arcs[i][j]＝ 0； ／ * 邻接矩阵初始化 *／
? for(k＝ 0； k＜ e； k++) ／ * 读入 e条边 *／
? (scanf(”％ d％ d％ f”,&I,&j,&w)；／ *读入边 (vi,vj)上的权 w *／
? ga ->arcs[i][j]＝ w；
? ga - >arcs[j][i]＝ w；
? }
? }／ *CREATGRAPH *／
? 该算法的执行时间是 O(n+n2+e),其中 O(n2)的时问耗费在邻接矩阵的初始化操作上 。
因为 e＜ n2,所以, 算法的时间复杂度是 O(n2)。
邻接表
这种表示法类似于树的孩子链表表示法 。
对于图 G中的每个顶点 vi，该方法把所有邻接于 vi的顶
点 vj链成一个单链表，这个单链表就称为顶点 vi的邻接
表 (Adjacency List)。邻接表中每个表结点均有两个域，
其一是邻接点域 (Adjvex)，用以存放与 vi相邻接的顶点
vj的序号；其二是链域 (Next)，用来将邻接表的所有表
结点链在一起。并且为每个顶点 vi的邻接表设置一个具
有两个域的表头结点：一个是顶点域 (vertex)，用来存
放顶点 vi的信息；另一个是指针域 (Link)，用于存入指
向 vi的邻接表中第一个表结点的头指针。为了便于随机
访问任一顶点的邻接表，将所有邻接表的表头结点顺
序存储在一个向量中，这样，图 G就可以由这个表头向
量来表示。
建立有向图的邻接表与此类似，只是更加简单，
每读入一个顶点对序号＜ i,j＞时，仅需生成
十个邻接点序号为 j的边表结点，将其插入到 vi
的出边表头部即可。若建立网络的邻接表，则
需在边表的每个结点中增加一个存储边上权的
数据域。
值得注意的是，一个图的邻接矩阵表示是唯一
的，但其邻接表表示不唯一，这是因为邻接表
表示中，各边表结点的链接次序取决于建立邻
接表的算法以及边的输入次序。
邻接矩阵和邻接表是图的两种最常用的存储结
构，它们各有所长。下面从空间及执行某些常
用操作的时间这两方面来作一比较。
在邻接表 (或逆邻接表 )表示中，每个边表对应于
邻接矩阵的一行 (或一列 )，边表中结点个数等
于一行 (或一列 )中非零元素的个数。对于一个
具有 n个顶点 e条边的图 G，若 G是无向图，则
它的邻接表表示中有 n个顶点表结点和 2e个边
表结点；若 G是有向图，则它的邻接表表示或
逆邻接表表示中均有 n个顶点表结点和 e个边表
结点。因此邻接表或逆邻接表表示的空间复杂
度为 S(n,e)＝ O(n+e)。若图中边的数目远远小
于 n2(即 e＜＜ n2)，此类图称作稀疏图 (Sparse
Graph)，这时用邻接表表示比用邻接矩阵表示
节省存储空间；若 e接近于 n2 (准确地说，无向
图 e接近于 n(n-1)／ 2，有向图 e接近于 n(n-1))，
此类图称作稠密图 (Dense Graph)，考虑到邻接
表中要附加链域，则应取邻接矩阵表示法为宜。
在无向图中求顶点的度, 邻接矩阵及邻接表两种存储结构都很容易
做到：邻接矩阵中第 i行 (或第 i列 )上非零元素的个数即为顶点 vi的
度；在邻接表表示中, 顶点 vi的度则是第 i个边表中的结点个数 。
在有向图中求顶点的度 。 采用邻接矩阵表示比邻接表表示更方便：
邻接矩阵中的第 i行上非零元素的个数是顶点 vi的出度 OD(vi),第 i
列上非零元素的个数是顶点 vi的入度 ID(vi),顶点 vi的度即是二者
之和；在邻接表表示中, 第 i个边表 (即出边表 )上的结点个数是顶
点 vi的出度, 求 vi的入度较困难, 需遍历各顶点的边表 。 若有向图
采用逆邻接表表示, 则与邻接表表示相反, 求顶点的入度容易,
而求顶点出度较难 。
在邻接矩阵表示中, 很容易判定 (vi,vj)或＜ vi,vj＞是否是图的一
条边, 只要判定矩阵中的第 i行第 j列上的那个元素是否为零即可；
但是在邻接表表示中, 需扫描第 i个边表, 最坏情况下要耗费 O(n)
时间 。
在邻接矩阵中求边的数目 e，必须检测整个矩阵，所耗费的时间是
0(n2)，与 e的大小无关；而在邻接表表示中，只要对每个边表的结
点个数计数即可求得 e，所耗费的时间是 0(e+n)。因此，当 e＜＜ n2
时，采用邻接表表示更节省时间。
图的遍历
和树的遍历类似，图的遍历也是从某个顶点出发，
沿着某条搜索路径对图中所有顶点各作一次访
问。若给定的图是连通图，则从图中任一顶点
出发顺着边可以访问到该图的所有顶点。然而，
图的遍历比树的遍历复杂得多，这是因为图中
的任一顶点都可能和其余顶点相邻接，故在访
问了某个顶点之后，可能顺着某条回路又回到
了该顶点。为了避免重复访问同一个顶点，必
须记住每个顶点是否被访问过。为此，可设置
一个布尔向量 visited[n]，它的初值为 false，一
旦访问了顶点 vi，便将 visited[i-1]置为 TRUE。
深度优先搜索 (Depth-First-Search)遍历类似于树的前序遍历。假设给
定图 G的初态是所有顶点均未访问过，在 G中任选一顶点 vi为初始
出发点，则深度优先搜索可定义如下：首先，访问出发点 vi，并
将其标记为已访问过，然后，依次从 vi出发搜索 vi的每一个邻接点
vj,若 vj未曾访问过，则以 vj为新的出发点继续进行深度优先搜索。
显然上述搜索法是递归定义的，它的特点是尽可能先对纵深方向
进行搜索，故称之为深度优先搜索。例如，设 x是刚访问过的顶点，
按深度优先搜索方法，下一步将选择一条从 x出发的未检测过的边
(x,y)。若发现顶点 y已被访问过，则重新选择另一条从 x出发的
未检测过的边。若发现顶点 y未曾访问过，则沿此边从 x到达 y，访
问 y并将其标记为已访问过，然后从 y开始搜索，直到搜索完从 y出
发的所有路径，才回溯到顶点 x，然后再选择一条从 x出发的未检
测过的边。上述过程直至从 x出发的所有边都已检测过为止。此时，
若 x不是初始出发点，则回溯到在 x之前被访问过的顶点；若 x是初
始出发点，则整个搜索过程结束。显然这时图 G中所有和初始出
发点有路径相通的顶点都已被访问过。因此，若 G是连通图，则
从初始出发点开始的搜索过程结束，也就意味着完成了对图 G的
遍历。
在该存储结构上执行 DFS算法的过程如下：设初始出发点是 v1，则
DFS（ 0）的执行结果是访问 v1，将其置上已访问标记，从 v1搜索
到的第 1个邻接点是 v2，因 v2未曾访问过，故调用 DFS(1)。执行
DFS(1)，首先访问 v2，将其标记为已访问过，然后从 v2搜索到的
第 1个邻接点是 vl，但 vl已访问过，故继续搜索到第 2个邻接点 v4，
v4未曾访过，因此调用 DFS(3)。类似地分析，访问 v4后调用
DFS(7)，访问 v：后调用 DPS(4)。执行 DFS(4)时，在访问 v5并作标
记后，从 v5搜索到的两个邻接点依次是 v2和 v8，因为它们均已被访
问过，所以 DFS(4)执行结束返回，回溯到 v8。又因为 v8的两个邻
接点已搜索过，故 DFS(7)亦结束返回，回溯到 v4。类似地由 v4回
溯到 v2。 V2的邻接点 vl和 v4已搜索过，但 v2的第 3个邻接点 v5还尚
未搜索，故接下来由 v2搜索到 v5，但因为 v5已访问过，所以 DFS(1)
也结束返回，回溯到 vl。 vl的第 1个邻接点已搜索过，故继续从 v1
搜索到第 2个邻接点 v3，因为 v3未曾访问过，故调用 DFS(2)。类似
地依次访问 v3,v6,v7后，又由 v7依次回溯到 v6,v3,vl。此时,vl
的所有邻接点都已搜索过，故 DFS(0)执行完毕。
宽度优先搜索法
宽度优先搜索 (Breadth-First-Search)遍历类似于树的按层次遍历 。 设
图 G的初态是所有顶点均未访问过, 在 G中任选一顶点 2为初始出
发点, 则宽度优先搜索的基本思想是：首先访问出发点 Vi,接着
依次访问 vi的所有邻接点 wl,w2,…, wt,然后, 再依次访问与 wl，
w2,…, wt邻接的所有未曾访问过的顶点, 依此类推, 直至图中
所有和初始出发点 v有路径相通的顶点都已访问到为止 。 此时, 从
vi开始的搜索过程结束, 若 G是连通图则遍历完成 。
显然，上述搜索法的特点是尽可能先对横向进行搜索，故称之为
宽度优先搜索。设 x和 y是两个相继被访问过的顶点，若当前是以 x
为出发点进行搜索，则在访问 x的所有未曾访问过的邻接点之后，
紧接着是以 y为出发点进行横向搜索，并对搜索到的 y的邻接点中
尚未被访问的顶点进行访问。也就是说，先访问的顶点其邻接点
亦先被访问。为此，需引进队列保存已访问过的顶点。
最小生成树
图的生成树不是唯一的, 从不同的顶点出发进行遍历,
可以得到不同的生成树 。 对于连通网络 G＝ (V,E),边
是带权的, 因而 G的生成树的各边也是带权的 。 我们把
生成树各边的权值总和称为生成树的权, 并把权最小
的生成树称为 G的 最小生成树 (Minimun Spanning Tree)。
生成树和最小生成树有许多重要的应用。令图 G的顶点
表示城市，边表示连接两个城市之间的通讯线路。 n个
城市之间最多可设立的线路有 n(n-1)／ 2条，把 n个城市
连接起来至少要有 n-1条线路，则图 G的生成树表示了
建立通讯网络的可行方案。如果给图中的边都赋予权，
而这些权可表示两个城市之间通讯线路的长度或建造
代价，那么，如何选择 n-1条线路，使得建立的通讯网
络其线路的总长度最短或总代价最小呢?这就是要构造
该图的一棵最小生成树。
以下我们只讨论无向图的最小生成树问题。构造最小生
成树可以有多种算法，其中大多数构造算法都是利用
了最小生成树的下述性质：设 G＝ (V,E)是一个连通网
络,U是顶点集 V的一个真子集。若 (u,v)是 G中所有
的一个端点在 U(即 u∈ U)里、另一个端点不在 U(即
v∈ V-U)里的边中，具有最小权值的一条边，则一定存
在 G的一棵最小生成树包含此边 (u,v)。这个性质称为
MST性质。 MST性质可用反证法证明：假设 G的任何
一棵最小生成树中都不含边 (u,v)。设 T是 G的一棵最
小生成树，但不包含边 (u,v)。由于 T是树，且是连通
的，因此有一条从 u到 v的路径；且该路径上必有一条
连接两个顶点集 U和 V-U的边 (u′,v′)，其中 u′∈ U，
v′∈ V-U，否则 u和 v不连通。当把边 (u,v)加入树 T时，
得到一个含有边 (u,v)的回路，见图 7-15。删去边 (u′，
v′)，上述回路即被消除，由此得到另一棵生成树 T′,T′
和 T的区别仅在于用边 (u,v)取代了 T中的边 (u′,v′)。
因为 (u,v)的权＜ (u′,v′)的权，故 T′的权＜ T的权，因
此 T′也是 G的最小生成树，它包含边 (u,v)，与假设矛
盾 !
假设 G＝ (V,E)是连通网络, 为简单起见, 我们用序号 1至 n来表示
顶点集合, 即 v＝ {1,2,…, n}。 设所求的最小生成树为 T＝ (U，
TE),其中 U是 T的顶点集, TE是 T的边集 。 并且将 G中边上的权看
做是长度 。
Prim算法的基本思想是：首先从 v中任取一个顶点 u0,将生成树 T
置为仅有一个结点 u0的树, 即置 U＝ {u0}；然后只要 U是 V的真子
集, 就在所有那些其一个端点 u己在 T(即 u∈ U),另一个端点 v还未
在 T(即 v∈ V— U)的边中, 找一条最短 (即权最小 )的边 (u,v),并
把该条边 (u,v)和其不在 T中的顶点 v,分别并入 T的边集 TE和顶
点集 U。 如此进行下去, 每次往生成树里并入一个顶点和一条边,
直到把所有顶点都包括进生成树 T为止 。 此时, 必有 U＝ V,TE中
有 n-1条边 。 MST性质保证上述过程求得的 T＝ (U,TE)是 G的一棵
最小生成树 。
显然,Prim算法的关键是如何找到连接 U和 V-U的最短边来扩充生
成树 T。为直观解释方便，设想在构造过程中,T的顶点集 U中顶
点和边集 TE中的边均被涂成红色,U之外的顶点集 V-U中的顶点
均被涂成蓝色，连接红点和蓝点的边均被涂成紫色，那么．最短
紫边就是连接 U和 V-U的最短边。
最短路径
交通网络中常常提出这样的问题：从甲地到乙地之间是
否有公路连通?在有多条通路的情况下, 哪一条路最短?
交通网络可用带权图来表示 。 顶点表示城市名称, 边
表示两个城市有路连通, 边上权值可表示两城市之间
的距离, 交通费或途中所花费的时间等 。 求两个顶点
之间的最短路径, 不是指路径上边数之和最少, 而是
指路径上各边的权值之和最小 。
另外，若两个顶点之间没有边，则认为两个顶点无通路，
但有可能有间接通路（从其他顶点达到 )）。路径上的
开始顶点 (出发点 )称为源点，路径上的最后一个顶点称
为终点，并假定讨论的权值不能为负数。
所有顶点对之间的最短路径
所有顶点对之间的最短路径是指：对于给
定的有向网 G=(V,E)，要对 G中任意一对
顶点有序对 V,W(V≠W)，找出 V到 W的
最短距离和 W到 V的最短距离。解决此问
题的一个有效方法是,轮流以每一个顶点
为源点，重复执行迪杰斯特拉算法 n次，
即可求得每一对顶点之间的最短路径,总
的时间复杂度为 O(n3)。
弗洛伊德算法 仍然使用 前面定义的 图的邻接 矩阵
cost[n+1][n+1]来存储带权有向图 。 算法的基本思想是,
设置一个 nxn的矩阵 A(k),其中除对角线的元素都等于 0
外, 其他元素 a(k)[i][j]表示顶点 i到顶点 j的路径长度, K
表示运算步骤 。 开始时, 以任意两个顶点之间的有向
边的权值作为路径长度, 没有有向边时, 路径长度为 ∞，
当 K=0时, A (0)[i][j]=arcs[i][j],
以后逐步尝试在原路径中加入其他顶点作为中间顶点，
如果增加中间顶点后，得到的路径比原来的路径长度
减少了，则以此新路径代替原路径，修改矩阵元素。
具体做法为：第一步，让所有边上加入中间顶点 1，取
A[i][j]与 A[i][1]+A[1][j]中较小的值作 A[i][j]的值，完成
后得到 A(1)，第二步，让所有边上加入中间顶点 2，取
A[i][j]与 A[i][2]+A[2][j]中较小的值，完成后得到 A(2)…,
如此进行下去，当第 n步完成后，得到 A(n),A(n)即为我
们所求结果,A(n)[i][j]表示顶点 i到顶点 j的最短距离。
拓扑排序
通常我们把计划、施工过程、生产流程、程序流程等都
当成一个工程，一个大的工程常常被划分成许多较小
的子工程，这些子工程称为活动，这些活动完成时，
整个工程也就完成了。例如，计算机专业学生的课程
开设可看成是一个工程，每一门课程就是工程中的活
动，图 7-24给出了若干门所开设的课程，其中有些课
程的开设有先后关系，有些则没有先后关系，有先后
关系的课程必须按先后关系开设，如开设数据结构课
程之前必须先学完程序设计基础及离散数学，而开设
离散数学则必须学完高等数学。在图 7-24（ b）中，我
们用一种有向图来表示课程开设，在这种有向图中，
顶点表示活动，有向边表示活动的优先关系，这有向
图叫做顶点表示活动的网络 (Active On Vertices)简称为
AOV网。
在 AOV网中,<i,j>有向边表示 i活动应先于 j活动开始，即
i活动必须完成后,j活动才可以开始，并称 i为 j的直接
前驱,j为 i的直接后继。这种前驱与后继的关系有传递
性，此外，任何活动 i不能以它自己作为自己的前驱或
后继，这叫做反自反性。从前驱和后继的传递性和反
自反性来看,AOV网中不能出现有向回路（或称有向
环）。在 AOV网中如果出现了有向环，则意味着某项
活动应以自己作为先决条件，这是不对的，工程将无
法进行。对程序流程而言，将出现死循环。因此，对
给定的 AOV网，应先判断它是否存在有向环。判断
AOV网是否有有向环的方法是对该 AOV网进行拓扑排
序，将 AOV网中顶点排列成一个线性有序序列，若该
线性序列中包含 AOV网全部顶点，则 AOV网无环，否
则,AOV网中存在有向环，该 AOV网所代表的工程是
不可行的。
本章小结
图是一种复杂的非线性结构, 具有广泛的应用背景 。 本章涉及到的基本概念有：
图,由两个集合 V和 E组成, 记为 G＝ (V,E),其中 v是顶点的有穷非空集合, E是 V中
顶点偶对 （ 称为边 ） 的有穷集 。 通常, 也将图 G的顶点集和边集分别记为 V(G)和
E(G)。 E(G)可以是空集, 若 E(G)为空, 则图 G只有顶点而没有边, 称为空图 。
有向图 （ Digraph）,若图 G中的每条边都是有方向的, 则称 G为有向图 。
无向图 （ Undigraph）, 若图 G中的每条边都是没有方向的, 则称 G为无向图 。
无向完全图 (Undirected Complete Graph),恰好有 n(n-1)／ 2条边的无向图称为无向完
全图 。
有向完全图 (DirectedComplete Graph)：恰有 n(n-1)条边的有向图称为有向完全图 。
邻接点 (Adjacent)：若 (vi,vj)是一条无向边, 则称顶点 vi和 vj互为邻接点 。
度 (Degree)：无向图中顶点 v的度是关联于该顶点的边的数目 。
人度 (1ndegree)若 G为有向图, 则把以顶点 v为终点的边的数目, 称为 v的人度, 记为
ID(v)。
出度 (outdegree)：把以顶点 v为始点的边的数目, 称为 v的出度, 记为 OD(v)。
子图 (Subgraph)：设 G＝ (V,E)是一个图，若 v′ 是 v的子集,E′ 是 E的子集，且 E′
中的边所关联的顶点均在 v′ 中，则 G′ ＝ (V′, E′ )也是一个图，并称其为 G的
子图。
路径 (Path)：在无向图 G中, 若存在一个顶点序列 vp,vi1,vi2…, vin,vq, 使得 (vp,vil)，
(vi1,vi2),…, (vin,vq)均属于 E(G),则称顶点 vp到 vq存在一条路径 。
路径长度,该路径上边的数目 。
简单路径,若一条路径上除了 vp和 vq可以相同外, 其余顶点均不相同, 则称此路径为一条简单路
径 。
简单回路或简单环 (Cycle)：起点和终点相同 (vp＝ vq)的简单路径称为简单回路或简单环 。
有根图,在一个有向图中, 若存在一个顶点 v,从该顶点有路径可以到达图中其它所有顶点, 则称
此有向图为有根图, v称作图的根 。
连通,在无向图 G中, 若从顶点 vi到顶点 vj有路径 (当然从 vj到 vi也一定有路径 ),则称 vi和 vj是连通
的 。
连通图 (Connected Graph)：若 V(G)中任意两个不同的顶点 vi和 vj都连通 (即有路径 ),则称 G为连通
图 。
连通分量 (connectedComponent)：无向图 G的极大连通子图称为 G的连通分量 。
强连通图,在有向图 G中, 若对于 V(G)中任意两个不同的顶点 vi和 vj,都存在从 vi到 vj以及从 vj到 vi
的路径, 则称 G是强连通图 。
强连通分量,有向图 G的极大强连通子图称为 G的强连通分量 。
网络 (Network)：若将图的每条边都赋上一个权, 则称这种带权图为网络 。
生成树 (Spanning Tree)：连通图 G的一个子图如果是一棵包含 G的所有顶点的树, 则该子图称为 G
的生成树 。
最小生成树 (MinimunSpanning Tree)：权最小的生成树称为 G的最小生成树 。
本章在介绍图的基本概念的基础上, 还介绍了图的两种常用的存储结构, 对图的遍历, 最小生成
树等问题做了较详细的讨论, 给出了相应的求解算法, 有的算法采用自顶向下, 逐步求精的
方法加以介绍, 也许能便于读者理解它们 。
相对而言之，图这一章内容较难，尤其是离散数学基础较差的读者，也许难度更大些。建议读者
知难而进，理解本章所介绍的算法实质，掌握图的有关术语和存储表示。面对实际问题时，
学会引用本章的有关内容。
