图的基本概念

1第7章图7.1图的基本概念7.2图的存储结构7.3图的遍历7.4图的连通性问题7.5有向无环图及其应用7.6最短路径2

图是比树形结构更为复杂的非线性结构。在线性结构中，除了开始结点和终端结点外，每个结点只有唯一的直接前趋和直接后继，结点之间存在一对一的线性关系；在树形结构中，结点之间存在一对多的层次关系，除根结点外，每个结点只能有一个直接前趋（即双亲），但每个结点允许有零或多7.1图的基本概念3个直接后继（即孩子），即每一层上的结点可以与它下面一层中的多个结点相关，但是只能和它上面一层的一个结点（双亲结点）相关。而在图结构中，数据元素之间的关系是一种多对多的网状关系，任意两个数据元素之间都可能相关。4

图的应用已渗透到语言学、逻辑学、物理、化学、电子、通讯、数学、计算机科学等诸多学科领域。

本章首先介绍图的概念，然后重点介绍图的存储结构及常用算法。5

图是由非空的有穷顶点集合V和表示顶点间关系的弧或边的有穷集合E组成的二元组，一般记为：

G＝（V，E）其中，V={vi|vi∈dataobject}，E={<vi,vj>或（x，y）|vi,vj∈V}，dataobject是具有相同性质的数据元素（即顶点）的集合；

1图的定义6

有序对<vi,vj>表示从顶点vi到vj有一条边单向相连称作弧，且称vi为弧尾（始点），vj为弧头（终点），此时称图为有向图。如图7.1（a）中的G2为有向图。若<vi,vj>∈E，且有<vj,vi>∈E，则可以用无序对（vi,vj）代替这两个有序对，即图中的每条边都是没有方向的，则称G为无向图。如图7.1（b）中的G1为无向图。2有向图与无向图7有向图——对于一个图G，若边集合E（G）为有向边的集合，则称该图为有向图。如图7.1(a).无向图——对于一个图G，若边集合E（G）为无向边的集合，则称该图为无向图。如图7.1(b).（a）有向图（b）无向图图7.1G8常用术语：(1)一条弧——在有序图中，<v,w>表示从v到w的一条弧，v为弧尾，w为弧头。即尖括号表示有序对。(2)一条边——在无序图中，(v,w)表示v和w之间的一条边，即圆括号表示无序对。(3)完全图——对于无向图，设顶点数目为n，则有n(n-1)/2条边的无向图（即每对顶点间均存在有边）。尾VW头9(4)完全有向图——对于有向图，设顶点数目为n，则有n(n-1)条弧的有向图（即每对顶点间均存在有弧）。(5)稀疏图、稠密图、子图、邻接点、网络;

(6)顶点的度TD（v）——（对无向图）是与顶点有关的边的数目，如G2中顶点v2的度为3;

入度ID(v）和出度OD（v）——（对有向图）入度为该顶点的弧头数目，出度为该顶点的弧尾数目，该顶点的度TD（v）=入度+出度，如图G1中顶点V1:TD(v1)=ID(v1)+OD(v1)=1+2=310对于一个有n个顶点，e条边或弧的图，满足如下关系：(7)路径和路径长度——如图7.3(a)中A—B有三条路径，分别是：(8)简单路径、回路或环——(9)连通、连通图和连通分量——(10)强连通图和强连通分量——(11)权和网——1112

将具有最大的边数n(n-1)／2条边的无向图称为无向完全图；具有n(n-1)条弧的有向图称为有向完全图。而将具有很少条边或弧的图称为稀疏图，反之称为稠密图。假设有两个图G=（V，E）和G’=（V’，E’），如果V’V且E’E，则称G’为G的子图。例如，图7.2为图7.1中图G1和G2的一些子图。3完全图与子图1314

对于无向图G=（V，E），若（x，y）∈E，则称x和y互为邻接点，即x和y相邻接，边（x，y）依附于顶点x和y，或者说边（x，y）和顶点x和y相关联。同样，对于有向图，若<x，y>是一条弧，则称顶点x邻接到顶点y，顶点y邻接于顶点x，或者称弧<x，y>关联于顶点x和y，也可以称弧<x，y>与顶点x和y相关联。

4邻接与关联15

在无向图中，顶点V的度是与该顶点相关联的边的数目，记为D(v)。而在有向图中要区别顶点的入度和出度的概念。入度是指以顶点V为头或终点的弧的数目，记为ID(v)；出度是指以顶点V为尾或始点的弧的数目，记为OD(v)，并将出度为0的顶点称为终端顶点(或叶子)；顶点V的度则定义为该顶点的入度和出度之和，即D(v)＝ID(v)十OD(v)。

5度、入度和出度16

在无向图G中，若存在一个顶点序列Vp，Vi1，Vi2，…，Vin，Vq，使得(Vp，Vi1)，(Vi1，Vi2)，…，(Vin，Vq)都是E中的边，或者在有向图中，若<Vp,Vi1>，<Vi1,Vi2>，…，<Vin,Vq>都是E中的弧，则称Vp，Vi1，Vi2，…，Vin，Vq为从顶点Vp到顶点Vq的一条路径，而将该路径上边或弧的数目称为路径长度。如果在一条路径上，除了Vp和Vq相同外，其他顶点都不相同，则称此路径为一条简单路径，而将起点和终点相同（即Vp=Vq）的简单路径称为简单回路或环。

6路径与回路17

在无向图G中，如果从顶点Vi到Vj有路径，则称Vi和Vj是连通的。如果图G中任意两个不同的顶点Vi和Vj（即Vi≠Vj）都存在路径连通，则称该图G是连通图。一个无向图G的极大连通子图称为此图的连通分量。在有向图G中，如果对于任意两个不同的顶点Vi，Vj（即Vi≠Vj），都存在从Vi到Vj和从Vj到Vi的路径，则称该有向图G是强连通图。一个有向图G的极大强连通子图称作该有向图G的强连通分量。例如，图7.1中的图G2不是强连通图。如无向图图7.3及它的3个连通分量（P159）。7连通图与强连通18如下图（a）中有两个强连通分量，分别如图（b）和（c）所示：19

有时在实际应用中，图的边或弧具有与它相关的数称作权。权可以表示一个顶点到另一个顶点的距离、花费的代价等。带权的图称为网络。

8网络20

一个连通图的生成树是一个极小连通子图，它包含有图中全部的n个顶点和n-1条边。如果在一棵生成树上添加一条边，则必定构成一个环。例如，图7.1中的G1即为其本身的生成树。一个有n个顶点的连通图的生成树有且仅有n-1条边。9生成树217.2图的存储结构

本节讨论三种常用的图与网的存储结构：邻接矩阵、邻接表和邻接多重表。

22

1、邻接矩阵对一个具有n个顶点的图或网，可以用一个一维数组表示其顶点信息，用邻接矩阵来表示顶点间是否相邻的关系。若G是一个具有n个顶点的图，则G的邻接矩阵A应是具有如下性质的n阶方阵:

1(Vi，Vj)或〈Vi，Vj〉∈E（G）（即两顶点相关联）

A[i，j]＝

0(Vi，Vj)或〈Vi，Vj〉E（G）（即两顶点无关联）7.2.1邻接矩阵（数组表示法）23例如，图7.1中Gl和G2的邻接矩阵A1和A2分别为：24

借助于邻接矩阵很容易判断出两个顶点是否相邻，并计算出各顶点的度。在无向图中，顶点Vi的度是邻接矩阵A中第i行的非零元素个数之和，即25

在有向图中，顶点Vi的出度是邻接矩阵A中第i行非零元素个数之和，而顶点Vi的入度是邻接矩阵A中第i列非零元素个数之和，即网络的邻接矩阵A定义为:（Wij为权值）

wij (Vi，Vj)或〈Vi，Vj〉∈EA[i，j]=∞ (Vi，Vj)或〈Vi，Vj〉E2627

2、邻接矩阵表示

#defineMAXVAL99999/*设最大值∞为99999*/#defineMAXNUM20/*最大顶点数*/typedefcharvertextype;/*顶点数据类型，此处设为char类型*/typedeffloatadjtype；/*权值类型*/typedefstruct{vertextypevex[MAXNUM];/*用一维数组表示顶点*/ adjtypearcs[MAXNUM][MAXNUM]；/*邻接矩阵用二维数组表示*/ intn，e；/*图的当前顶点数和弧或边数*/}*mgraph;

28voidcreatgraph(mgraphg) /*

采用邻接矩阵表示法构造无向网g*/{inti，j，k；floatw；

scanf(“%d%d”，&g->n，&g->e)；/*输入图的顶点数和边数*/for(i=1；i<=g->n；i++)scanf(“%c”，&g->vex[i])；/*构造顶点向量*/for(i=1；i<=g->n；i++) for(j=1；j<=g->n；j++)g->arcs[i][j]=MAXVAL；/*初始化邻接矩阵*/for(k=1；k<=g->e；k++){scanf(“%d%d%f”，&i，&j，&w)；

g->arcs[i][j]=w；g->arcs[j][i]=w；/*权值赋予邻接矩阵的相应元素*/}}/*creagraph*/3、邻接矩阵表示法构造无向网291、结点结构

邻接表（AdjdcencyList）是图或网的一种链式存储结构。在邻接表中，对图或网中的每个顶点建立一个单链表，单链表中的结点表示该顶点的所有邻接点。在有向图中，某顶点所对应的单链表中的结点是以该顶点为弧尾的顶点。每一个结点由三个域组成，其中，邻接点域（adjvex）指示与顶点vi邻接的顶点在图中的序号，指针域（link）指示vi的下一个邻接结点，有时，可以在结点中添加7.2.2邻接表30

信息域（info）用于存储和边或弧相关的信息，如权值等。为了能够随机访问任一个顶点的邻接链表，可以在每一个邻接链表前增设一个表头结点，然后将所有邻接表的表头结点存放在一个一维数组中。表结点和表头结点结构如下所示：31表结点类型定义：

#defineM50typedefstructnode{intadjvex；/*邻接点域*/structnode*link；/*指针域*/}edgenode；

2、类型定义32typedefstructheadnode{vextypevexdata；/*顶点数据域*/structnode*firstarc；/*指针域指向链表中第一个结点*/}vexnode；邻接表类型：

typedefvexnodeadjlist[M]；/*adjlist为邻接表类型*/表头结点类型定义：33

图7.5（a）给出了图7.1中无向图G1的邻接表，图7.5（b）、（c）给出了图7.1中有向图G2的邻接表和逆邻接表。若要表示网的邻接表，则只需在链表的每个结点中增加一个存放边或弧的权值的数据域（info）即可。利用邻接表可以很容易地查找到任一个顶点的邻接点，但要判定任意两个顶点vi和vj之间是否有边或弧相连，则需要搜索第i个或第j个链表，在这一点上不及邻接矩阵方便。

3、邻接表与逆邻接表34例：图G1、G2的邻接矩阵表示：（1）给每个顶点编号；（2）以每个顶点为头建立一个单链；（3）单链中后继结点为与该头结点关联的各结点。3536G2的逆邻接矩阵：在有向图中，以入度为链中后继。37

voidcreatlist(vexnodeag[]，intn){edgenode*p;inti，j，k；charch；

for(i=1；i<=n；i++){scanf(“%c”，&ch)；/*读入顶点信息*/ag[i].vexdata=ch；/*设顶点为字符型*/ag[i].firstarc=NULL；/*将每个链表初始化为空*/}scanf(“％d，％d”，&i，&j)；

while((i＞0)&&(j＞0))/*输入的(i,j)为(0,0)作为结束标记*/

4、无向图的邻接表生成算法38

{p=(edgenode*)malloc(sizeof(edgenode))；

p->adjvex=j；

p->link=ag[i].firstarc；

ag[i].firstarc=p；/*结点j插入到第i个链表*/p=(edgenode*)malloc(sizeof(edgenode))；

p->adjvex=i；

p->link=ag[j].firstarc；

ag[j].firstarc=p；/*结点i插入到第j个链表的头部*/scanf(“％d，％d”，&i，&j)；

}}/*creatlist*/39

该算法的时间复杂度是O(n+e)（e为边数）。有向图邻接表的建立算法与建立邻接矩阵的算法相似，但在输入一条弧的顶点序号<i，j>时只需生成一个结点（其adjvex域为j）并将其插入到第i个顶点的链表中即可。407.2.3十字链表

十字链表是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。在十字链表中，对应于有向图中每一条弧有一个结点，对应于每个顶点也有一个结点。弧结点结构为5个域，分别是：尾结点位置（tailvex）、头结点位置（headvex）、弧头链域（hlink）指向弧头相同的下一弧、弧尾链域（tlink）指向弧尾相同的下一弧、相关信息域（info）存放权值。41顶点结点有3个域，分别是：data域、指向以该顶点为弧头或弧尾的第一个弧结点（firtin、firsout）。弧结点tailvexheadvexhlinktlinkinfoDataFirstifirstout顶点结点42例：有向图的十字链表表示方法为：V1V2^V3V402^0131^32^^23^^30^20有向图10230123以此类推，得出P165的有向图的十字链表图7.11以V1为弧头的结点以V1为弧尾的结点弧头相同者431、结点结构

邻接多重表是无向图的另一种链式存储结构。在邻接多重表中，每条边用一个结点表示，每个结点由5个域组成，其结点结构如下图所示。其中，mark是标志域，可用来标记这条边是否访问过；ivex和jvex为该边依附的两个顶点vi、vj的序号；ilink指向依附于顶点vi的下一条边；jlink指向依附于顶点vj的下一条边。

7.2.4邻接多重表44

而图或网中每一个顶点的结点结构由数据域(data)和指针域(firstarc)组成，数据域存放与该顶点有关的信息，指针域指示依附于该顶点的第一条边。其结点结构如下所示：

45

typedefstructarcnode {intmark，ivex，jvex；

structarcnode*ilink，*jlink；

}edgenode；

typedefstructvexnode{intdata；

structarcnode*firstarc；

}vexnode；2、类型定义：46图7.6邻接多重表示例例：无向图的邻接多重表。依附于1的下一条边是依附于2的下一条边是47作业基础知识：题集7.1。48

和树的遍历运算类似，图的遍历（TraversingGraph）是指从图中的任一个顶点出发访问图中所有顶点，并且使每个顶点仅被访问一次的运算。由于图结构本身的复杂性，使得图的遍历要比树的遍历复杂得多。图的遍历是图的一种重要操作，对图的许多操作都可在遍历过程中完成，如求解图的连通性、拓扑排序和求关键路径等问题。

7.3图的遍历49

根据搜索路径的方向不同，通常有两种遍历图的方法：深度优先搜索遍历和广度优先搜索遍历，这两种遍历方法对无向图或有向图都适用。50

7.3.1深度优先搜索遍历

1、图的深度优先搜索图的深度优先搜索（DepthFirstSearch）遍历类似于树的前序遍历。假设给定图G的初始状态是所有顶点都未被访问过，在图G中任选一个顶点v0为初始出发点，则深度优先搜索遍历的基本思想是：首先访问顶点v0，并将其标记为已被访问过，然后，依次从v0出发搜索v0的每一个邻接点，若未被访问过，则以该邻接点为出发点继续进行深度优先搜索。具体作法是：首先访问顶点v0，并将其标记为已被访问过，再访问一个与v0相邻的未被访问过的顶点vi，接着访问一个与vi相邻接且未被访问过的顶点.51具体作法是：首先访问顶点v0，并将其标记为已被访问过，再访问一个与v0相邻的未被访问过的顶点vi，接着访问一个与vi相邻接且未被访问过的顶点Vj，……，依此类推，直到某个被访问的顶点的所有邻接点均被访问过为止，然后退回到尚有邻接点未被访问过的顶点vr，再从顶点vr的一个未被访问的邻接点出发，重复上述过程，直到图中所有和v0有路径相通的顶点都已被访问过为止。例如，图7.7中图G，若从v1出发深度优先搜索遍历，结点的访问顺序可为:v1→v2→v5→v8→v4→v3→v6→v7。52例如，图7.7中图G，若从v1出发深度优先搜索遍历，结点的访问顺序可为（不是唯一的）:v1→v2→v5→v8→v4→v3→v6→v7。演示深度优先遍历图.swf53voiddfs(vexnodeag[]，intv，intflag[])/*从v出发对图g深度优先搜索*/{edgenode*p；inti；flag[v]=l；/*作标志用

printf(“％c＼n”，ag[v].vexdata)；/*访问顶点v，设顶点类型为字符型*/p=ag[v].firstarc；/*p最初指向V的第一个邻接点*/while（p!=NULL）

{i=p->adjvex；/*取出p指针所指邻接点的序号*/

2、深度优先搜索遍历的递归算法54

if(flag[i]==0)dfs(ag，i，flag)；p=p->link；/*查找下一个邻接点*/}}

对整个图深度优先搜索遍历的算法blt如下：

voidblt(vexnodeag[]，intn)/*对图g按深度优先搜索遍历*/{inti；

intflag[M]；

for(i=1；i<=n；i++)flag[i]＝0；/*初始化标志数组flag*/for(i=1；i<=n；i++)if(flag[i]==0)dfs(ag，i，flag)；/*调用深度优先搜索算法dfs*/}551、图的广度优先搜索广度优先搜索（BreadthFirstSearch）遍历类似于树的按层次遍历。假设给定图G的初始状态是所有顶点都未被访问过，在图G中任选一个顶点v0为初始出发点，则广度优先搜索遍历的基本思想是：首先访问顶点v0，并将其标记为已被访问过，接着依次访问v0的所有未被访问过的邻接点vl、v2、…、vd，然后，再依次访问vl、v2、…、vd的所有未被访问过的邻接点，依此类推，直到图中所有被访问过的顶点的7.3.2广度优先搜索遍历56

邻接点都被访问过为止；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问过的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。例如，图7.7中图G，从v1出发得到的广度优先搜索遍历顶点序列为:v1→v2→v3→v4→v5→v6→v7→v8演示57

2、广度优先搜索遍历算法

voidbfs(vexnodeag[]，intv，intflag[]){intq[M]，r=0，f=0；

edgenode*p;printf(“％c＼n”，ag[v].vexdata)；

flag[v]=l；

q[0]=v；/*刚访问过的顶点序号入队列*/while(f<=r)/*当队列不空时*/{v=q[f++]；/*访问过的顶点（序号）出队列*/p=ag[v].firstarc；/*p指向v的第一个邻接点*/while(p!＝NULL)/*依次搜索v的邻接点*/{v=p->adjvexif(flag[v]==0)58

{flag[v]＝l；/*置已被访问过标志*/printf(“％c＼n”，ag[v].vexdata)；/*访问顶点v*/ q[++r]=v；/*被访问过的顶点入队列*/ }p=p->link；/*查找下一个邻接点*/}}}/*bfs*/59作业基础知识：题集7.3；601、生成树在一个连通图中,如果取它的全部顶点和一部分边构成一个子图G`，即，若边集中的边既将G中的所有顶点连通又不形成回路，则称子图G`是原图G的一棵生成树。一个含n个顶点的连通图的生成树是图的一个极小连通子图，它包含图中全部的n个顶点和足以保证任意两顶点连通所需的n-1条边。若从一个连通图的任何一个顶点出发对图进行搜索遍历，遍历过程中经过的边（不7.4图的连通性问题7.4.1生成树和最小生成树61含回边）加上图的所有顶点就可以构成图的生成树。例如，深度优先生成树和广度优先生成树。图7.8给出了连通图G及其生成树。622、最小生成树

若将一个带权图（网）的其对应生成树上的各边权值之和称为该生成树的代价，那么，最小代价生成树（简称最小生成树）就是指各边权值的总和最小的生成树。例如，图7.9（a）所示的网G，其最小生成树如图7.9（b）所示。显然，一个连通网的最小生成树可能不是唯一的，但它们的总代价一定相同。

最小生成树在实际应用中有广泛的用途。例如，假设要在n个城市之间建立通讯网络，若用图的顶点表示城市，边表示连接两城市之间的通信线路，则图的生成树就表示了可行的通讯网络的方案。如果图中的边都带上权，而且边上的权值表示两个城市之间的63通信线路，则图的生成树就表示了可行的通讯网络的方案。如果图中的边都带上权，而且边上的权值表示两个城市之间的距离，或者表示两个城市之间建立通讯网络所花的代价等。上面的问题就是要求构造一个连通网的最小生成树的问题。又如，在某个地区的一些村庄间要修建公路。公路的修建计划可以用一个网来表示，用顶点表示村庄，边表示连接两个村庄间的公路，边上的权值表示修建该条公路所需的代价，如果希望修建公路总费用最小且各村庄间都有公路相通，则问题转化为只要找到该公路网的一棵最小代价生成树即可。

6465

3、最小生成树的MST性质设G=（V，E）是一个连通网络，U是顶点集V的一个真子集（即）。若（u，v）是一条具有最小权值的边，其中一个端点在U里，另一个端点不在U里（即u∈U，v∈V-U），则一定存在一棵包含此边（u，v）的最小生成树。这个性质称为MST性质。那如何利用MST性质来构造最小生成树呢？普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法就是其中较常用的两种。66

1、普里姆（Prim）算法

普里姆（Prim）算法是从连通网中的一个顶点开始，以此作为生成树的初始状态，然后不断地将网中的其它顶点添加到生成树上而最终得到最小生成树。假设一个具有n个顶点的连通网络N=（V，E），T=（U，TE）是N的最小生成树，U和TE的初值均为空集。首先从网N中任选一个顶点（设为u0），把这个顶点包括在生成树里，即令U={u0}，TE=Φ，然后在那些其一个端点已在生成树中另一个端点还未在生成树里的边（设为（u，v），7.4.2普里姆算法67

且u∈U，v∈V-U）中查找权值最小的一条边（设为（u0，v0）），并把这条边和边所依附的那个不在生成树中的端点添加进生成树中，即将（u0，v0）加入到TE中，同时把v0也加入到U中，如此进行，每次往生成树里加一个顶点和一条权值最小的边，直到把所有的顶点都包括进生成树中为止，从而

T=（U，TE）即为N的最小生成树。68

利用普里姆算法从顶点v1开始构造连通网G的最小生成树的过程。69

设立一个辅助数组closedge用以记录每一次选择的从U到V-U中具有最小权值的边。设closedge数组下标从1开始，数组中的元素closedge[i]对应于序号为i的顶点vi，它包含adjvex和lowcost域。若顶点vi已在生成树U中，则置closedge[i].lowcost=0；若顶点vi不在生成树中，则用closedge[i].lowcost存放vi与生成树中的顶点构成的最小代价边的权值，而用closedge[i].adjvex存放该最小边所关联的已在生成树上的另一个顶点的序号。假设无向连通网以邻接矩阵g存储，从序号为k的顶点vk开始构造最小生成树，则辅助数组的初始2、普里姆（Prim）算法实现70情况为：closedge[k].lowcost=0，closedge[i].lowcost=g[k][i]，losedge[i].adjvex=k然后从数组中选出某一个j，若它满足closedge[j].lowcost不等于0且是最小的值，则将vj添加到生成树中，并修改closedge数组中的值，如此不断进行下去，直到全部的n个顶点都在生成树中，从而就得到了要求的最小生成树。71普里姆（Prim）算法描述：

#defineM50#defineMAXVAL999/*设MAXVAL为权值的上限*/struct{intadjvex；

floatlowcost；

}closedge[M]；

voidprim(mgraphg，intk){inti，j，p，v；

floatmin；

for(i=1；i<=g->n；i++)/*辅助数组初始化*/72

if(i!=k){closedge[i].adjvex=k；

closedge[i].lowcost=g->arcs[k][i]；

}closedge[k].lowcost=0；

for(j=1；j<=g->n；j++) {p=1；min=MAXVAL；

for(v=1；v<=g->n；v++)/*选取最小的权值及对应的顶点Vp*/ if（（closedge[v].lowcost!=0）&&（closedge[v].lowcost<min））

{min=closedge[v].lowcost；p=v；

}73

printf(“%d%d%f\n”，closedge[p].adjvex，p，min)； closedge[p].lowcost=0；for(j=1；j<=g->n；j++)if(g->arcs[p][j]<closedge[j].lowcost){closedge[j].lowcost=g->arcs[p][j]；/*修改权值*/closedge[j].adjvex=p；

}}}/*prim*/

图7.11给出了从顶点V1出发算法实现过程中辅助数组中各分量的值。普里姆算法的时间复杂度是O（n2），它适用于求边稠密的网的最小生成树。74757.4.3克鲁斯卡尔算法

克鲁斯卡尔（Kruskal）算法的基本思想是：假设连通网N=（V，E），令最小生成树的初始状态为无边相连的n个相互独立的顶点组成的非连通图T=（V，{Φ}），图中每个顶点自成一个连通分量，并将e条边按权值大小由小到大排序；在网的边集E中从权值最小的边开始依权值递增顺序查看每一条边，如果该边所依附的两个顶点在不同的连通分量上，则选定此边连接两个连通分量为一个连通分量，即将此边加入到T中，否则舍弃此边而再76

选择下一条权值次小的边，依此类推，直至T中所有的顶点都在同一个连通分量上为止，此时，这个连通分量T就是一棵最小生成树。Kruskal算法适合于求边稀疏的无向连通网的最小生成树。图7.12给出了按克鲁斯卡尔算法构造连通网（图（a））的最小生成树的过程。77(c)(d)(e)78作业基础知识：题集7.7；797.5有向无环图及其应用7.5.1拓扑排序

1、有向无环图有向无环图（简称为DAG图）是指无环的有向图，它是一类比有向树更一般的特殊有向图。如图7.18给出了有向树、DAG图和有向图的例子，（a）、（b）、（c）都是有向图，（a）、（b）都是DAG图，只有（a）是有向树。利用有向无环图可实现对相同子式的共享，从而节省存储空间（如P179图7.22、7.23所示）。8081

有向无环图常用于描述任务安排问题。一般地说，一个较大的工程往往被划分成许多子工程，这些子工程称为活动(Activity)，这些子工程之间通常受到一定条件的约束，但有些子工程没有先决条件。只有这些子工程都顺利完成后，整个工程才能完成。例如，一件设备的生产过程包含着许多工序；一个教学计划包含许多课程等等。在每个计划包含的许多活动之间，各种计划的执行之间可能存在着先决条件。2、AOV网82

这种各个活动之间的次序关系可以用一个有向图来表示，图中的每个顶点代表一个活动。如果从顶点vi到vj之间存在弧<vi,vj>，则表示活动i必须先于活动j进行，这种用顶点表示活动，弧表示活动间先后关系的有向图叫做顶点活动网(ActivityOnVertexNetwork)，简称AOV网。例如，图7.19是关于计算机专业教学计划中各课程之间的关系。它对应的AOV网如图7.20所示8384

AOV网应该是有向无环图，即不应该出现回路。若带有回路，从而使回路上的所有活动都无法进行，如图7.21所示。85

3、拓扑排序在AOV网中，若不存在回路，则可将所有活动排列成一个线性序列，使得每个活动的所有先决活动都排在该活动的前面。将一个有向无环图中所有顶点在不违反先决条件的基础上排成线性序列的过程称为拓扑排序，并称此线性序列为拓扑序列。由AOV网构造拓扑序列的实际意义在于若按照拓扑序列中的顶点次序进行每一项活动，就能保证在开始每一项活动时，它的所有前趋或先决活动都已完成，从而使得整个工程按顺序进行。86

AOV网拓扑排序：（1）在AOV网中选择一个入度为0的顶点(即没有前趋的顶点)，并将其输出；（2）从网中删除该顶点及以它为尾（即以该顶点为出发点）的所有弧即所有出边；（3）重复执行上述两步，直到全部顶点被输出，即拓扑排序完成，或者当前的有向图中不存在无前趋（入度为0）的顶点，说明该有向图中存在有向环，拓扑排序不能继续进行下去。图7.22给出了对有向无环图G进行拓扑排序得到顶点的输出序列的过程。87对于此图也可以构造得其它的拓扑有序序列。88

4、拓扑排序算法实现采用邻接表（如图7.23所示）作为给定AOV网的存储结构，并在表头结点中增设一个入度域in，用于存放各个顶点当前的入度值，这样，要选择并输出一个入度为0的顶点只要对顶点表的入度域进行扫描即可实现，而删除顶点和以它为尾的弧的操作只要将弧头顶点的入度减1就可实现，即在输出某个顶点后，要将该顶点的所有邻接点的入度值减1。如在图7.23中。8990

设置一个链栈来存放所有入度为0的顶点，每当输出顶点就从栈中弹出一个，每当出现新的入度为0的顶点便将其入栈保存，并利用该顶点的入度域作为链栈单元使用，用于存放下一个入度为0的顶点序号。这样，通过所有入度为0的表头结点中的入度域就可以把入度为0的顶点（对应表头结点）都静态链接起来。用邻接表表示的AOV网的拓扑排序算法步骤如下：（1）扫描邻接表，把所有入度值为0的顶点入栈；91

（2）当栈非空时，将栈顶顶点元素出栈并输出，然后在邻接表中检查该顶点的直接后继即邻接点，并把各邻接顶点的入度值减l；（3）将新产生的入度为0的顶点入栈；（4）重复步骤（2）、（3），直至栈空时为止，若栈空时输出的顶点个数不是n（即小于n），则说明有向图中有环，不可进行拓扑排序，否则，拓扑排序完成。92#defineM50typedefstructnode/*边表结点*/{intadjvex；/*邻接点域*/structnode*next；/*指针域*/}edgenode；typedefstructheadnode/*顶点表头结点*/{vextypevex；

intin；/*入度域*/edgenode*firstarc；/*指针域指向链表中第一个结点*/}vexnode；typedefvexnodeadjlist；/*adjlist为邻接表类型*/AOV网的邻接表的表结点和表头结点的类型定义如下：93拓扑排序的算法：

inttopsort(adjlistg[]，intn){inttop，m，k，i，j；edgenode*p；

m=0；top=0；

for(i=1；i<=n；i++)if(g[i].in==0){g[i].in=top；top=i；

}while(top!=0){j=top；top=g[top].in；

printf(“％d＼t”，g[j].vex)；

m++；

p=g[j].firstarc；94

while(p!=NULL){k=p->adjvex；

g[k].in--；

if(g[k].in==0){g[k].in=top；top=k；

}p=p->next；

}}printf(“m=％d＼t”，m)；if（m<n）{printf(“thenetworkhasacycle\t”)；return(0)；

}95

elsereturn(1)；

}/*topsort*/

对拓扑排序而言，具有n个顶点e条边的AOV网建立邻接表需O(n+e)的时间，搜索入度为０的顶点需O(n)的时间。在拓扑排序过程中若AOV网无环路，每个顶点入栈和出栈各n次，入度减１的操作共执行e次，所需时间为Ｏ(n+e)，所以算法总的时间复杂度为Ｏ(n+e)。967.5.2关键路径

与AOV网相对应的是AOE网（ActivityOnEdge），用事件作顶点，用活动作有向边，这样的图称为事件结点网。AOE网是一个带权的有向无环图，（Event），弧表示活动，权表示活动持续时间，通常，AOE网在工程计划上可用来估算工程完成的时间。97V1V2V3V4V5V6V7V8V9a1=6a2=4a3=5a5=1a4=1a6=2a8=7a7=9a9=4a11=4a10=2图7.29一个AOE网

例如，P183图7.29是一个有9件事情（顶点），11项活动（弧）的AOE网。与每个活动相联系的数是执行该活动所需的时间，比如，活动a1需要6天，活动a2需要4天等。98

事件V1表示整个工程可以开始，事件V5表示活动a4,a5已经完成，活动a7,a8可以开始这个状态，事件V9表示整个工程结束。整个工程一开始，活动a1,a2,a3就可以并行地进行，而活动a4,a5,a6只有当事件V2,V3,V4分别发生后才能进，当活动a10,a11完成后，整个工程就可以完成了。V1V2V3V4V5V6V7V8V9a1=6a2=4a3=5a5=1a4=1a6=2a8=7a7=9a9=4a11=4a10=2图7.29一个AOE网

99

表示实际工程计划的事件网络应该是无环的，且存在唯一的入度为0的开始结点（如图中的V1）及唯一的出度为0的完成结点（如图中的V9）。利用事件结点网络可以进行工程安排估算，研究完成整个工程至少需要多少时间，为缩短整个工程的完成时间应该加快哪些活动的速度。为解决这问题，可采用PERT、CMP等技术。

V1V2V3V4V5V6V7V8V9a1=6a2=4a3=5a5=1a4=1a6=2a8=7a7=9a9=4a11=4a10=2图7.29一个AOE网

100

因为在事件结点网络中，活动可以并行地进行，所以完成整个工程的最少时间是从开始结点到完成结点的最长路径的长度（路径长度等于路径上各边的权值之和）。具有最大长度的路径称作关键路径。如图中路径V1，V2，V5，V8，V9是一条关键路径，长度为18，也就是说整个工程至少要18天才能完成。

V1V2V3V4V5V6V7V8V9a1=6a2=4a3=5a5=1a4=1a6=2a8=7a7=9a9=4a11=4a10=2图7.29一个AOE网

101

分析关键路径的目的是找出关键活动，即不按期完成就会影响整个工程的完成的时间的活动，例如图中a1,a4等。找到了关键活动就可以适当调度，投入较多的人力和物力在关键活动上，才能保证整个工程按期完成，并可争取提前完成。V1V2V3V4V5V6V7V8V9a1=6a2=4a3=5a5=1a4=1a6=2a8=7a7=9a9=4a11=4a10=2图7.29一个AOE网

102

为找关键活动，先定义几个相关的量：（1）事件Vi的最早发生时间e(i)是从结点V1到Vi的最长路径长度，这个时间决定了所有以Vi为尾的弧所表示的活动的最早开始时间。例如：事件v9最早发生时间为：

从v1到v9的最长路径长度18；例如：活动a6最早开始时间为:e(6)=5；头k尾jai顶点vi103（2）事件Vi的最迟开始时间l(i)，这是在不推迟整个工程完成的前提下，活动ai最迟必须开始的时间，例如活动a6最迟开始时间为8。即如果a6推迟3天开始或者延迟3天完成，都不会影响整个工程的完成。头k尾jai104最迟开始时间计算方法为：l(i)=关键路径长度-（Vi到Vn的最长路径长度）。例如：a6最迟开始时间为l(i)=18-（2+4+4）=8。两者之差l(i)-e(i)意味着完成ai的时间余量。即如果a6推迟3天开始或者延迟3天完成，都不会影响整个工程的完成。头k尾jai105将l(i)=e(i)的活动叫做关键活动。显然，关键路径上的所有活动都是关键活动。求关键路径的算法及分析P184、185。106

最短路径是指路径长度（即路径上边的权值之和或边的条数）最小的路径。在实际应用中存在着许多有关有向带权图的最短路径问题。例如，若用一个图表示城市之间的运输网，如何能够使得从一个城市到另一个城市的运输时间最少或代价最少呢？这就是一个求两个城市之间的最短路径问题。本节讨论求带权有向图的最短路径的两个常用算法，且假定所有的权值都是7.6最短路径

107

正数。一般的，求带权有向图的最短路径包括两种情况：（1）求图中一个顶点到其余各顶点的最短路径；（2）求图中每对顶点之间的最短路径。1087.6.1单源最短路径

1、单源最短路径将路径上的起始顶点称为源点，路径上的最后一个顶点称为终点。单源最短路径是指从一个顶点（源点）出发到其它各顶点的最短路径，即给定有向网G和源点vi，求从vi到G中其它各顶点vj（j=1，2，…，n，j≠k）的最短路径。

2、Dijkstra算法描述迪杰斯特拉(E.WDijkstra)提出了求单源最短路径的一般算法——按路径长度递增的次序产生最短路径。109

基本思路是：

按照从源点到其余每一个顶点的最短路径长度的递增顺序依次求出从源点到其它各顶点的最短路径及长度，每次求出从源点vi到一个终点vj的最短路径及长度后，都要以vj作为新考虑的中间点，用vi到vj的最短路径和最短路径长度对vi到其它尚未最后求出最短路径的那些终点的当前最短路径及长度作必要的修改，使之成为当前新的最短路径和最短路径长度，当进行n-2次后算法结束。110

具体做法：把图中所有顶点分成两组，第一组由已确定最短路径的顶点组成（设为集合S），第二组包括尚未确定最短路径的顶点（设为集合V），开始时，第一组S只包括顶点vi，第二组包括其余的所有顶点，若令vi对应的距离值为0，则第二组V中的顶点对应的距离值可以按下列方式确定：若图中有弧<vi，vj>，则将此弧的权值作为vj的距离值，否则vj的距离值为∞（或用一个很大的数MAXVAL表示），然后每次从第二组V的顶点中选一个其距离值为最小的顶点（设为vmin）加入到第一组S中，每次往第一组S中加入一个顶点111vmin，就要对第二组V中的各个顶点的距离值进行一次修改。若以加入的顶点vmin做中间顶点，使得从vi到vj的最短路径比未加入顶点vmin的路径更短，则要修改vj的距离值，然后再继续选取距离值最小的顶点加入到第一组S中，如此进行下去，直到图中所有顶点都包括在第一组S中，或不存在可加入到第一组S中的顶点为止。112

用dist[j]（设下标从1开始）表示在当前时刻所找到的从源点vi到终点vj的最短路径长度，其初始值为：dist[i]=0，若存在弧<vi，vj>，则dist[j]为其弧上的权值，若不存在弧<vi，vj>，则dist[j]=∞。这样，最短路径长度就可通过dist数组各元素得到。若用数组pre的每个单元存放从起始顶点vi到以下标为序号的顶点的路径上此顶点的前一个顶点的序号，如用pre[j]表示从源点vi到顶点vj的最短路径上vj前一个顶点的序号即前趋顶点，若从

3、Dijkstra算法实现113vi到vj没有路径可达，则用0作为vj的前一个顶点的序号，这样，就可利用pre数组将最短路径也记下来。在算法结束前，可根据pre数组找到源点到顶点vj的最短路径上每个顶点的前趋顶点，即沿着顶点vj对应的pre[j]回溯，从而得到从顶点vi出发到vj的最短路径，且其最短路径长度等于dist[j]。

Dijkstra算法描述如下：114

#defineMAXVAL99999voiddijkstra(mgraphg，floatdist[]，intpre[]，inti){intj，k，p，v；floatmin；

for(j=1；j<=g->n；j++)/*数组dist和pre初始化，即置初始距离值*/{dist[j]=g->arcs[i][j]；

if(dist[j]<MAXVAL)pre[j]＝i；

elsepre[j]=0；

} pre[i]=0；dist[i]=0；/*数组dist和pre初始化*/g->arcs[i][i]=1；115

for(k=1；k<=g->n-1；k++){min=MAXVAL；/*设MAXVAL为最大数/*j=-1；

for(p=1；p<=g->n；p++) if((g->arcs[p][p]==0)&&(dist[p]<min)){j=p；min=dist[p]；

}/*if*/ if(j==-l)break；/*已没有顶点可往第一组加入，则退出*/else{g->arcs[j][j]=1；

for(v=1；v<=g->n；v++)116if((g->arcs[v][v]==0)&&(min+g->arcs[j][v]<dist[v])) {dist[v]=min+g->arcs[j][v];pre[v]=j；

}}/*else*/}/*for*/}/*dijkstra*/

用Dijkstra算法求图7.13所示的带权有向图G从顶点V1到其它各顶点的最短路径，其算法执行过程中dist数组和pre数组的变化情况如图7.14所示。可得路径为：V1→V3→V4→V5，路径长度为dist[5]=13。

Dijkstra算法的时间复杂度为O(n2)。117118直接路径间接路径1197.6.2所有顶点对之间的最短路径

1、所有顶点对之间的最短路径是指图中任意两个顶点vi和v