数据结构图结构动态

本章主要介绍图的基本概念、图的存储结构和有关图的一些常用算法。通过本章学习，读者应该：1)

了解图的定义和术语

2)掌握图的各种存储结构3)

掌握图的深度优先搜索和广度优先搜索遍历算法

4)

理解最小生成树、最短路径、拓扑排序、关键路径等图的常用算法

本章学习导读

当前第1页\共有141页\编于星期五\0点1

图（Graph）是一种较线性表和树更为复杂的非线性结构。在线性结构中，结点之间的关系是线性关系，除开始结点和终端结点外，每个结点只有一个直接前趋和直接后继。在树形结构中，结点之间的关系实质上是层次关系，同层上的每个结点可以和下一层的零个或多个结点（即孩子）相关，但只能和上一层的一个结点（即双亲）相关（根结点除外）。然而在图形结构中，对结点（图中常称为顶点）的前趋和后继个数都是不加限制的，即结点之间的关系是任意的。图中任意两个结点之间都可能相关。图的应用极为广泛，特别是近年来的迅速发展，已渗透到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其它分支中。

当前第2页\共有141页\编于星期五\0点2

7.1图的定义

7.2图的存储结构

7.3图的遍历

7.4图的连通性问题

7.5有向无环图及其应用

7.6最短路径

第七章图当前第3页\共有141页\编于星期五\0点3

图定义

图G由两个集合V和E组成，记为G=(V,E)

其中，V是顶点的有穷非空集合，

E是V中顶点偶对的有穷集，这些顶点偶对称为边。通常V(G)和E(G)分别称为图的顶点集合和边集合。注：E(G)可以为空集。7.1图的定义和术语当前第4页\共有141页\编于星期五\0点47.1图的定义和术语图的数据结构的形式化定义（p156）

G=(V,E)

其中V={x|xdataobject}

E={VR}VR={<x,y>|p(x,y)(x,yV)}VR是两顶点间的关系的集合，即边的集合。当前第5页\共有141页\编于星期五\0点5图的术语有向图:

对一个图G，若边集E(G)为有向边的集合，则称该图为有向图。①②③④G1G1=（V，E）V={v1,v2,v3,v4}E={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}其中<x,y>表示从x到y的一条弧（arc），A为弧集合，x为弧尾（tail），y为弧头（head)x弧尾y弧头当前第6页\共有141页\编于星期五\0点6图的术语无向图:对一个图G，若边集E(G)为无向边的集合，则称该图为无向图。

①②G2③④⑤

G2=（V，E）V={v1,v2,v3,v4,v5}E={(v1,v2),(v1,v3),(v2,v3),(v3,v4),(v2,v5),(v3,v5)}其中，(x,y)表示x与y之间的一条连线，称为边（edge）当前第7页\共有141页\编于星期五\0点7图的术语设n为顶点数，e为边或弧的条数

对无向图有：0≤e≤

n(n-1)/2

有向图有：0≤e≤n(n-1)证明：对有向图，每个顶点至多有n-1条边与其它的n-1个顶点相连，则n个顶点至多有n(n-1)条边。但对无向图，每条边连接2个顶点，故最多为n(n-1)/2

当前第8页\共有141页\编于星期五\0点8图的术语端点和邻接点

在一个无向图中，若存在一条边<vi,vj>,则称vi，vj为该边的两个端点，并称它们互为邻结点。

21453G2当前第9页\共有141页\编于星期五\0点9图的术语起点和终点

在一个有向图中，若存在一条边<vi,vj>,则称该边是顶点vi的一条出边，是vj的一条入边，称vi是起始端点（或起点），称vj是终止端点（或终点）,并称它们互为邻结点.2134G1当前第10页\共有141页\编于星期五\0点10图的术语度

图中每个顶点的度是以该顶点为一端点的边的数目。记为D(V)。入度和出度

对于有向图，入度为以该顶点为终点的边的数目，出度为以该顶点为起点的边的数目。例D(v1)=3

无向图的度数为依附于顶点v的边数；有向图的度数等于以顶点v为弧头的弧数与以顶点v为弧尾的弧数之和21453G22134G1例D(v1)=2

当前第11页\共有141页\编于星期五\0点11图的术语子图

设有两个图G=（V，E）

G’=（V’，E’）中，若V’是V的子集，E’是E的子集，则称G’是G子图。①①④①③④⑤

①②③④⑤

①②G2③④⑤

当前第12页\共有141页\编于星期五\0点12图的术语简单图

对不含多重边和自环的图。2145321453简单图非简单图当前第13页\共有141页\编于星期五\0点13图的术语完全图

边达到最大的图无向完全图：具有n(n-1)/2条边的简单图称为无向完全图有向完全图：具有n(n-1)条边的有向图。稀疏图：

边或弧很少的图。稠密图：

边或弧很多的图。

权：与图的边或弧相关的数。

网：边或弧上带有权值的图。当前第14页\共有141页\编于星期五\0点14图的术语路径

非空有限点、弧交替序列，

W=v0,a1,v1,…,ak,vk

使得i=1,2,…k,

弧ai的头vi,尾为vi-1

。

路径长度：路径上边或弧的数目当前第15页\共有141页\编于星期五\0点15图的术语简单路径：除首尾两点外，其他各点都不相同的路径称为简单路径。简单路径当前第16页\共有141页\编于星期五\0点16图的术语回路:无重复边的闭路径。环：闭的简单路径，称为环。回路但不是环环当前第17页\共有141页\编于星期五\0点17图的术语连通图：任何两点都有路径的图。

无向图：若图中任意两个顶点vi,vj都是连通

的，则称该图是连通图(vi<>vj)有向图：若图中任意两个顶点vi,vj，都存在

从vi到vj和从vj到vi的路径，则称

该有向图为强连通图

(vi<>vj)当前第18页\共有141页\编于星期五\0点18图的术语连通分量：

无向图：无向图中极大连通子图，称为

连通分量

有向图：有向图中极大强连通子图，称为

强连通分量当前第19页\共有141页\编于星期五\0点19生成树图的术语生成树

一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。

①②④⑤

①②④⑤

①②④⑤

①②④⑤

有向树

如果一个有向图恰有一个顶点入度为0，其余顶点的入度均为1，则是一棵有向树。

当前第20页\共有141页\编于星期五\0点20生成树、生成森林生成树一个连通图的生成树是它的极小连通子图，在n个顶点的情形下，有n-1条边。生成树是对连通图而言的是连通图的极小连通子图包含图中的所有顶点有且仅有n-1条边

非连通图的生成树则组成一个生成森林。若图中有n个顶点，m个连通分量，则生成森林中有n-m条边。

一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。当前第21页\共有141页\编于星期五\0点21图有两种存储结构

邻接矩阵邻接表7.2图的存储结构当前第22页\共有141页\编于星期五\0点227.2.1邻接矩阵邻接矩阵(AdjacencyMatrix)是表示顶点之间相邻关系的矩阵。设G＝(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵。7.2图的存储结构

无向图的邻接矩阵是以主对角线对称的，有向图的邻接矩阵可能是不对称的。在有向图中：第i行1的个数就是顶点i的出度，第j列1的个数就是顶点j的入度。在无向图中,第i行(列)1的个数就是顶点i的度。当前第23页\共有141页\编于星期五\0点23一、邻接矩阵（用二维数组表示）例如：G1的邻接矩阵例如：G2的邻接矩阵无向图的邻接矩阵为对称矩阵G212345G11234当前第24页\共有141页\编于星期五\0点24

对于无向图，（vi，vj）和（vj，vi）表示同一条边，因此，在邻接矩阵中Aij=Aji。无向图的邻接矩阵是（关于主对角线）对称矩阵，可用主对角线以上（或以下）的部分表示。对有向图，弧<vi，vj>和<vj，vi>表示方向不同的两条弧，Aij和Aji表示不同的弧，所以有向图的邻接矩阵一般不具有对称性。

邻接矩阵表示法适合于以顶点为主的运算。

当前第25页\共有141页\编于星期五\0点25

对于有向图，顶点vi的出度OD(vi)等于邻接矩阵第i行元素之和；顶点vi的入度ID(vi)等于邻接矩阵第i列元素之和，即：

对于无向图，顶点vi的度等于邻接矩阵第i行的元素之和，即：

OD(vi)=

ID(vi)=

TD（vi）=当前第26页\共有141页\编于星期五\0点26若G是网（有权图），邻接矩阵定义为V2V1V3V435214如图：

Wij若<vi,vj>

或<vj,vi>

∈E(G)A[i，j]=

0或若其它V1V2V3V4V1V2V3V4当前第27页\共有141页\编于星期五\0点27

顶点表:一个记录各个顶点信息的一维数组，

邻接矩阵：一个表示各个顶点之间的关系（边或弧）的二维数组。

使用邻接矩阵存储结构，可用一维数组表示图的顶点集合，用二维数组表示图的顶点之间关系（边或弧）的集合，数据类型定义如下：

#defineMAX_VERTEX_NUM20//最大顶点数typedefintAdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵类型typedefstruct{ VertexTypevexs[MAX_VERTEX_NUM];//顶点表

AdjMatrixarcs;//邻接矩阵

intvexnum，arcnum;//图的顶点数和弧数}MGraph;

由于一般图的边或弧较少，其邻接矩阵的非零元素较少，属稀疏矩阵，因此会造成一定存储空间的浪费。

当前第28页\共有141页\编于星期五\0点28

邻接表

图的链式存储结构1)为每个顶点建立一个单链表，2)第i个单链表中包含顶点Vi的所有邻接顶点。

邻接表是图的一种链式存储结构。类似于树的孩子链表表示法。在邻接表中为图中每个顶点建立一个单链表，用单链表中的一个结点表示依附于该顶点的一条边（或表示以该顶点为弧尾的一条弧），称为边（或弧）结点。

当前第29页\共有141页\编于星期五\0点2925341543533412212123451.无向图邻接表G212345adjvexnextarcvexdatafirstarc当前第30页\共有141页\编于星期五\0点302.有向图邻接表234143121234如图G1的邻接表为：G11234当前第31页\共有141页\编于星期五\0点31

在邻接表的边链表中，各个边结点的链入顺序任意，视边结点输入次序而定。设图中有n个顶点，e条边，则用邻接表表示无向图时，需要n个顶点结点，2e个边结点；用邻接表表示有向图时，若不考虑逆邻接表，只需n个顶点结点，e个边结点。建立邻接表的时间复杂度为O(n*e)。若顶点信息即为顶点的下标，则时间复杂度为O(n+e)。当前第32页\共有141页\编于星期五\0点32存储表示typedefstructArcNode{ intadjvex;//该弧所指向的顶点的位置 structArcNode*nextarc;//指向下一条弧的指针int*

info;//该弧相关信息的指针}ArcNode;//边结点类型typedefstructVNode{ VertexTypedata;//顶点信息 ArcNode*firstarc;//指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];//邻接表typedefstruct{ AdjListvertices;intvexnum,arcnum;//图的当前顶点数和弧数intkind;

//图的种类标志}ALGraph;当前第33页\共有141页\编于星期五\0点3325341543533412212123451.无向图邻接表二、邻接表G212345adjvexnextarcvexdatafirstarc当前第34页\共有141页\编于星期五\0点341.无向图邻接表对图中每个顶点Vi建立一个单链表，链表中的结点表示依附于顶点Vi的边，每个链表结点为两个域.其中：邻接点域（adjvex）记载与顶点Vi邻接的顶点信息；链域（nextarc）指向下一个与顶点Vi邻接的链表p结点每个链表设一个头结点，

头结点结构为：其中：vexdata存放顶点信息（姓名、编号等）；

firstarc指向链表的第一个结点。二、邻接表adjvexnextarcvexdatafirstarc当前第35页\共有141页\编于星期五\0点35二、邻接表（adjacencylist）如图G2的邻接表为：2534154353341221212345G212345当前第36页\共有141页\编于星期五\0点36BACDFE例20A141B0452C353D254E015F123当前第37页\共有141页\编于星期五\0点372.有向图邻接表234143121234特点：1.n个顶点，e条弧的有向图，需n个表头结点，e个表结点2.第i条链表上的结点数，为Vi的出度（求顶点的出度易，求入度难）如图G1的邻接表为：G11234当前第38页\共有141页\编于星期五\0点38142301201234

ABCDE2.有向图的邻接表ABECF可见，在有向图的邻接表中不易找到指向该顶点的弧。当前第39页\共有141页\编于星期五\0点393.有向图逆邻接表123411431234此时，第i条链表上的结点数，为Vi的入度如图G1的逆邻接表为：①②③④G1当前第40页\共有141页\编于星期五\0点40ABECD有向图的逆邻接表ABCDE30342001234在有向图的邻接表中，对每个顶点，链接的是指向该顶点的弧。在有向图的邻接表中，第i

个链表中结点的个数是顶点Vi的出度。在有向图的逆邻接表中，第i

个链表中结点的个数是顶点Vi

的入度。当前第41页\共有141页\编于星期五\0点414.带权有向图的邻接表链表中每个结点为三个域.

邻接点权带权图的边结点中info保存该边上的权值。当前第42页\共有141页\编于星期五\0点42ABECD4.带权有向图的邻接表ABCDE0123411037^04

4223^28^102254837125^顶点Vi的边链表的头结点存放在下标为i的顶点数组中。当前第43页\共有141页\编于星期五\0点43

十字链表

十字链表(OrthogonalList)是有向图的另一种链式存储结构。

可看作是将有向图的邻接表和逆邻接表结合的一种链表。

在十字链表中，为每个顶点vi设置一个结点，它包含数据域data和两个链域firstout、firstin，称为顶点结点。数据域data用于存放顶点vi的有关信息；链域firstin指向以顶点vi为弧头的第一个弧结点；链域firstout指向以顶点vi为弧尾的第一个弧结点。

弧结点包括四个域：尾域tailvex、头域headvex，链域hlink和tlink。

hlink指向弧头相同的下一条弧，tlink指向弧尾相同的下一条弧；data顶点信息，firstin以该顶点为头的第一个弧结点，firstout以该结点为尾的第一个弧结点。

起点vi终点vjhlinktlink弧结构顶点结构

datafirstinfirstout当前第44页\共有141页\编于星期五\0点44图7-8十字链表

图7-8为图7-6(a)有向图的十字链表。见右图

采用十字链表表示有向图，很容易找到以顶点vi为弧尾的弧和以顶点vi为弧头的弧，因此顶点的出度、入度都很容易求得。

当前第45页\共有141页\编于星期五\0点45十字链表的数据类型定义如下：

#defineMAXV<最大顶点个数>typedefstructArcbox//弧结点{inttailvex,headvex;//弧尾和弧头顶点位置

structArcNode*hlink,*tlink;//弧头相同和弧尾相同的弧的链域}ArcBox;typedefstructVexNode//顶点结点{VertexTypedata;//顶点信息

ArcNode*firstin,*firstout;//分别指向该顶点的第一条入弧和出弧}VexNode;当前第46页\共有141页\编于星期五\0点467.2.4邻接多重表

邻接多重表是无向图的另一种链式存储结构。在邻接多重表中设置一个边结点表示图中的一条边。边结点包含五个域，结构如下所示：

其中:mark域

标志域，用于对该边进行标记；ivex域

存放该边依附的一个顶点vi的位置信息；ilink域

该链域指向依附于顶点vi的另一条边的边结点；jvex域

存放该边依附的另一个顶点vj的位置信息；jlink域

该链域指向依附于顶点vj的另一条边的边结点。邻接多重表为每个顶点设置一个结点，其结构如下：

当前第47页\共有141页\编于星期五\0点47图7-9邻接多重表

图7-9为图7-5(a)无向图的邻接多重表。

由邻接多重表可以看出，表示边（vi，vj）的边结点通过链域ilink和jlink链入了顶点vi和顶点vj的两个链表中，实现了用一个边结点表示一个边的目的，克服了在邻接表中用两个边结点表示一个边的缺点。因此邻接多重表是无向图的一种很有效的存储结构。

当前第48页\共有141页\编于星期五\0点48邻接多重表的结点数据类型定义如下：

#defineMAXV<最大顶点个数>typedefstruct//边结点类型{intmark;//访问标识

intivex,jvex;//该边的两个顶点位置信息

structEnode*ilink,*jlink;//分别指向依附这两个顶点的下一条边}Enode;typedefstruct//顶点结点类型{VertexTypedata;//顶点数据域

ENode*firstedge;//指向第一条依附该顶点的边}Vnode;

当前第49页\共有141页\编于星期五\0点497.3图的遍历

和树的遍历相似，若从图中某顶点出发访遍图中每个顶点，且每个顶点仅访问一次，此过程称为图的遍历。(TraversingGraph)。

图的遍历远比树的遍历复杂。因为从树根到达树的某个结点只有一条路径，而图的两个顶点之间可能有多条路径。

因此，在图的遍历过程中，可能会出现下面的现象，即在顺着一条路径访问了某个顶点后，可能会沿着另一条路径又回到该顶点。

为避免一个顶点被多次访问，我们设置一个标志数组

intvisited[MAX_VERTEX_NUM];它的元素初值为0。一旦vi被访问了，便置相应数组元素为1.

图的遍历方法有：这两种方法对无向图和有向图都适用。

深度优先搜索遍历（简称DFS）广度优先搜索遍历（简称BFS）当前第50页\共有141页\编于星期五\0点50

深度优先搜索（DFS）1．深度优先搜索遍历过程：

DFS在访问图中某一起始顶点v后，由

v出发，访问它的任一邻接顶点w1；再从w1出发，访问与w1邻接但还没有访问过的顶点w2；然后再从w2出发，进行类似的访问，…如此进行下去，直至到达所有的邻接顶点都被访问过的顶点u为止。

接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。当前第51页\共有141页\编于星期五\0点51

深度优先搜索的示例

图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组visited[]，它的初始状态为0，在图的遍历过程中，一旦某一个顶点i

被访问，就立即让visited[i]为1，防止它被多次访问。当前第52页\共有141页\编于星期五\0点52

对上图，深度优先搜索遍历的顺序（之一）为：

v1

→v2→v4→v8→v5→v6→v3→v7。

图7-10深度优先搜索

当前第53页\共有141页\编于星期五\0点53深度优先搜索算法：intvisited[MAX_VERTEX_NUM];voidDFS(ALGraphG,intv){ArcNode*p;printf("%c",G.vertices[v].data);visited[v]=1;p=G.vertices[v].firstarc;while(p)

{if(!visited[p->adjvex])DFS(G,p->adjvex);p=p->nextarc;

}}//从第v个顶点出发DFS

当前第54页\共有141页\编于星期五\0点54整个图的DFS遍历voidDFSTraverse(ALGraphG){for(intv=0;v<G.vexnum;++v)visited[v]=0;for(v=0;v<G.vexnum;++v)if(!visited[v])DFS(G,v);}

对于连通图，从一个顶点出发，调用DFS函数即可将所有顶点都遍历到。当前第55页\共有141页\编于星期五\0点55

广度优先搜索（BFS）1．广度优先搜索思想

广度优先搜索遍历类似于树的按层次遍历。对于无向连通图，广度优先搜索是从图的某个顶点v0出发，在访问v0之后，依次搜索访问v0的各个未被访问过的邻接点w1，w2，…。然后顺序搜索访问w1的各未被访问过的邻接点，w2的各未被访问过的邻接点，…。即从v0开始，由近至远，按层次依次访问与v0有路径相通且路径长度分别为1，2，…的顶点，直至连通图中所有顶点都被访问一次。广度优先搜索的顺序不是唯一的，例如图7-10(a)连通图的广度优先搜索遍历顺序可为v1，v2，v3，v4，v5，v6，v7，v8

也可为v1，v3，v2，v7，v6，v5，v4，v8。

当前第56页\共有141页\编于星期五\0点56

广度优先搜索在搜索访问一层时，需要记住已被访问的顶点，以便在访问下层顶点时，从已被访问的顶点出发搜索访问其邻接点。所以在广度优先搜索中需要设置一个队列Queue，使已被访问的顶点顺序由队尾进入队列。在搜索访问下层顶点时，先从队首取出一个已被访问的上层顶点，再从该顶点出发搜索访问它的各个邻接点。

广度优先搜索过程 广度优先生成树广度优先搜索的示例当前第57页\共有141页\编于星期五\0点57广度优先搜索过程可描述为：（1）f=0;r=0;//队列初始化，空队列；f-队首指针，r-队尾指针（2）访问v0;（3）visited[v0]=1;（4）insert(Queue,f,r,v0);//v0进入队尾（5）whilef>0do(i)delete(Queue,f,r,x);//队首元素出队并赋于x(ii)对所有x的邻接点wifvisited[w]=0then（a）访问w;（b）visited[w]=1;（c）insert(Queue,f,r,w);//w进队列

当前第58页\共有141页\编于星期五\0点58

voidBFSseach(GraphG,intVisited[],intn){for(v=0;v<n;++v)visited[v]=0;//初始化访问标志

InitQueue(Q);//置空的辅助队列Qfor(v=0;v<G.vexnum;++v)if(!visited[v]){//v尚未访问visited[v]=1;Visit(v);//访问uEnQueue(Q,v);

//v入队列while(!QueueEmpty(Q)){u=DeQueue(Q,u);//队头元素出队并置为ufor(w=FirstAdjVex(G,u);w!=0;w=NextAdjVex(G,u,w))

if(!visited[w])

{

visited[w]=1;Visit(w);EnQueue(Q,w);

//访问的顶点w入队列

}//if}//while}//BFSTraverse当前第59页\共有141页\编于星期五\0点59课堂练习练习1、写出右图的邻接矩阵表示。ACBDEF当前第60页\共有141页\编于星期五\0点60课堂练习练习2、写出右图的邻接表表示。ACBDEF543210FE∧DCBA

1

2∧

0

4

5∧

3

5∧

3∧

4∧当前第61页\共有141页\编于星期五\0点61课堂练习练习3、根据右图的如下存储表示，写出以顶点A为出发点进行DFS的顶点访问序列。ACBDEF543210FE∧DCBA

1

2∧

0

4

5∧

3

5∧

3∧

4∧A，B，D，E，F，C当前第62页\共有141页\编于星期五\0点62课堂练习ACBDEF543210FE∧DCBA

1

2∧

0

4

5∧

3

5∧

3∧

4∧A，B，C，D，E，F练习4、根据右图的如下存储表示，写出以顶点A为出发点进行BFS的顶点访问序列。当前第63页\共有141页\编于星期五\0点63使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。按照生成树的定义，n个顶点的连通网络的生成树有n个顶点、n-1条边。构造最小生成树的准则必须使用且仅使用该网络中的n-1条边来联结网络中的n个顶点；不能使用产生回路的边；各边上的权值的总和达到最小。7.4

最小生成树

当前第64页\共有141页\编于星期五\0点64普里姆(Prim)算法普里姆算法的基本思想：从连通网络N={V,E}中的某一顶点u0出发,选择与它关联的具有最小权值的边(u0,v),将其顶点加入到生成树顶点集合U中。 以后每一步从一个顶点在U中,而另一个顶点不在U中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合U中。如此继续下去,直到网络中的所有顶点都加入到生成树顶点集合U中为止。采用邻接矩阵作为图的存储表示。当前第65页\共有141页\编于星期五\0点65252510504613228102514242216185046132504613210原图(a)(b)504613210(c)(d)(e)(f)50461321022125046121025142216123252212当前第66页\共有141页\编于星期五\0点66普里姆(Prim)算法在构造过程中，还设置了两个辅助数组：

lowcost[]存放生成树顶点集合内顶点到生成树外各顶点的各边上的当前最小权值；nearvex[]记录生成树顶点集合外各顶点距离集合内哪个顶点最近(即权值最小)。5046132281025142422161812当前第67页\共有141页\编于星期五\0点67普里姆(Prim)算法若选择从顶点0出发，即u0=0，则两个辅助数组的初始状态为：02810

-1000000

lowcostnearvex01234565046132281025142422161812当前第68页\共有141页\编于星期五\0点68然后反复做以下工作在lowcost[]中选择nearvex[i]-1&&lowcost[i]最小的边,用v标记它。则选中的权值最小的边为(nearvex[v],v),相应的权值为lowcost[v]。将nearvex[v]改为-1,表示它已加入生成树顶点集合,将边(nearvex[v],v,lowcost[v])加入生成树的边集合。取lowcost[i]=min{lowcost[i],Edge[v][i]}，即用生成树顶点集合外各顶点i到刚加入该集合的新顶点v的距离Edge[v][i]与原来它们到生成树顶点集合中顶点的最短距离lowcost[i]做比较,取距离近的作为这些集合外顶点到生成树顶点集合内顶点的最短距离。如果生成树顶点集合外顶点i到刚加入该集合的新顶点v的距离比原来它到生成树顶点集合中顶点的最短距离还要近，则修改nearvex[i]:nearvex[i]=v。表示生成树外顶点i到生成树内顶点v当前距离最近。当前第69页\共有141页\编于星期五\0点6902810

-1000000

lowcostnearvex0123456选v=5选边(0,5)当前第70页\共有141页\编于星期五\0点70顶点v=5加入生成树顶点集合：02825

10

-10005

-10

lowcostnearvex0123456选v=4选边(5,4)50461322810251424221618原图边(0,5,10)

加入生成树1204613210255当前第71页\共有141页\编于星期五\0点710123456顶点v=4加入生成树顶点集合：02822

2510

24

-100

4

-1-1

4

lowcostnearvex选v=3选边(4,3)50461322810251424221618原图边(5,4,25)

加入生成树125046132102522当前第72页\共有141页\编于星期五\0点72顶点v=3加入生成树顶点集合：02812

222510

18

-103

-1-1-1

3

lowcostnearvex0123456选v=2选边(3,2)50461322810251424221618原图边(4,3,22)

加入生成树12504613210252212当前第73页\共有141页\编于星期五\0点73lowcostnearvex0123456顶点v=2加入生成树顶点集合：0

16

1222251018

-1

2

-1-1-1-13

选v=1选边(2,1)50461322810251424221618原图边(3,2,12)

加入生成树125041321025221612当前第74页\共有141页\编于星期五\0点74顶点v=1加入生成树顶点集合：01612222510

14

-1-1

-1

-1-1-1

1

lowcostnearvex0123456选v=6选边(1,6)50461322810251424221618原图边(2,1,16)

加入生成树125046132102514221612当前第75页\共有141页\编于星期五\0点75lowcostnearvex0123456顶点v=6加入生成树顶点集合：0161222251014

-1-1

-1

-1-1-1-1

50461322810251424221618原图边(1,6,14)

加入生成树125046132102514221612最后生成树中边集合里存入得各条边为：

(0,5,10),(5,4,25),(4,3,22), (3,2,12),(2,1,16),(1,6,14)当前第76页\共有141页\编于星期五\0点76采用邻接表作为存储结构：设置一个辅助数组closedge[]：

lowcost域存放生成树顶点集合内顶点到生成树外各顶点的各边上的当前最小权值；即存放在V-U中各个顶点到集合U中的当前最小权值；

adjvex域记录生成树顶点集合外各顶点距离集合内哪个顶点最近(即权值最小)。即记录该边所依附的在U中的顶点。当前第77页\共有141页\编于星期五\0点77利用普里姆算法建立最小生成树:---了解（P175）typedefintVRType;struct{ VertexTypeadjvex; VRTypelowcost;}closedge[MAX_VERTEX_NUM];voidMiniSpanTree_PRIM(MGraphG,VertexTypeu){ intk,j,i,minCost; k=LocateVex(G,u); for(j=0;j<G.vexnum;++j) if(j!=k){ closedge[j].adjvex=u; closedge[j].lowcost=G.arcs[k][j];}当前第78页\共有141页\编于星期五\0点78closedge[k].lowcost=0;for(i=1;i<G.vexnum;++i){k=minimum(closedge);minCost=INFINITY;for(j=0;j<G.vexnum;++j){if(closedge[j].lowcost<minCost&&closedge[j].lowcost!=0){minCost=closedge[j].lowcost; k=j;}}printf("(%c,%c)\n",closedge[k].adjvex,G.vexs[k]);closedge[k].lowcost=0;for(j=0;j<G.vexnum;++j)if(G.arcs[k][j]<closedge[j].lowcost){closedge[j].adjvex=G.vexs[k]; closedge[j].lowcost=G.arcs[k][j];}}}当前第79页\共有141页\编于星期五\0点79

普里姆算法中的第二个for循环语句频度为n-1，其中包含的两个内循环频度也都为n-1，因此普里姆算法的时间复杂度为O(n2)。普里姆算法的时间复杂度与边数e无关，该算法更适合于求边数较多的带权无向连通图的最小生成树。

当前第80页\共有141页\编于星期五\0点80克鲁斯卡尔(Kruskal)算法克鲁斯卡尔算法的基本思想：设一个有n个顶点的连通网络N={V,E},最初先构造一个只有n个顶点,没有边的非连通图T={V,},图中每个顶点自成一个连通分量。当在

E中选到一条具有最小权值的边时,若该边的两个顶点落在不同的连通分量上，则将此边加入到T中;否则将此边舍去，重新选择一条权值最小的边。如此重复下去,直到所有顶点在同一个连通分量上为止。当前第81页\共有141页\编于星期五\0点81应用克鲁斯卡尔算法构造最小生成树的过程10504613228102514242216181250461325046132原图(a)(b)当前第82页\共有141页\编于星期五\0点821012504613228102514242216181250461325046132101412原图(c)(d)504613210141612(e)(f)(g)504613210142216125046121025142216123当前第83页\共有141页\编于星期五\0点83为实现克鲁斯卡尔算法需要设置一维辅助数组E，按权值从小到大的顺序存放图的边，数组的下标取值从0到e-1（e为图G边的数目）。了解----假设数组E存放图G中的所有边，且边已按权值从小到大的顺序排列。n为图G的顶点个数，e为图G的边数。克鲁斯卡尔算法如下：#defineMAXE<最大边数>#defineMAXV<最大顶点数>typedefstruct{intvex1;//边的起始顶点intvex2;//边的终止顶点intweight;//边的权值}Edge;

当前第84页\共有141页\编于星期五\0点84

Voidkruskal(EdgeE[],intn,inte){inti,j,m1,m2,sn1,sn2,k;intvset[MAXV];for(i=0;i<n;i++)//初始化辅助数组

vset[i]=i;k=1;//表示当前构造最小生成树的第k条边，初值为1

j=0;//E中边的下标，初值为0

while(k<e)//生成的边数小于e时继续循环{ml=E[j].vex1;m2=E[j].vex2;//取一条边的两个邻接点

sn1=vset[m1];sn2=vset[m2];//分别得到两个顶点所属的集合编号

if(sn1!=sn2)//两顶点分属于不同的集合，该边是最小生成树的一条边当前第85页\共有141页\编于星期五\0点85

{printf(“(m1，m2)：％d＼n”,E[j].weight);k++;//生成边数增lfor(i=0;i<n;i++)//两个集合统一编号

if(vset[i]=i)//集合编号为sn2的改为sn1vset[i]=sn1;}j++;//扫描下一条边}}

如果给定带权无向连通图G有e条边，且边已经按权值递增的次序存放在数组E中，则用克鲁斯卡尔算法构造最小生成树的时间复杂度为O(e)。克鲁斯卡尔算法的时间复杂度与边数e有关，该算法适合于求边数较少的带权无向连通图的最小生成树。

当前第86页\共有141页\编于星期五\0点867.５有向无环图及其应用１、有向无环图的定义有向无环图是描述一项工程或系统的进行过程的有效工具。因为几乎所有的工程均可以分为若干个称为活动的子工程，而这些子工程之间，通常受着一定条件的约束，如其中某些子工程的开始必须在另一些子工程完成之后。因此对整个工程和系统而言，最为关心的两个问题：

一是工程能否顺利进行；

二是估算整个工程完成所必须的最短时间。对应于有向图，即是探讨拓扑排序和关键路径问题。当前第87页\共有141页\编于星期五\0点87一个无环的有向图称作有向无环图(DirectidAcyclineGragp)称为DAG图。有向无环图是描述一项工程或系统的进行过程的有效工具当前第88页\共有141页\编于星期五\0点88课程代号课程名称先修棵C1C2C3C4C5C6C7C8C9C10C11C12无C1C1,C2C1C3,C4C11C3.C5C3,C6无C9C9C1,C9,C10程序设计基础离散数学数据结构汇编语言语言的设计和分析计算机原理编译原理操作系统高等数学线性代数普通物理数值分析C1C2C3C4C5C6C7C8C9C10C11C12学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业？？？顶点

——表示课程有向弧

——若课程i是课程j的先决条件，则图中有弧<i,j>学生选修课程问题当前第89页\共有141页\编于星期五\0点89AOV网——

用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网(ActivityOnVertexnetwork)，简称AOV网。拓扑排序——

把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫~检测AOV网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环。当前第90页\共有141页\编于星期五\0点90在有向图中选一个没有前驱的顶点且输出之从图中删除该顶点和所有以它为尾的弧拓扑排序的方法重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止当前第91页\共有141页\编于星期五\0点91C1C2C3C4C5C6C7C8C9C10C11C12拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8或：C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8一个AOV网的拓扑序列不是唯一的当前第92页\共有141页\编于星期五\0点92C1C2C3C4C5C6C7C8C9C10C11C12拓扑序列：C1（1）当前第93页\共有141页\编于星期五\0点93C2C3C4C5C6C7C8C9C10C11C12拓扑序列：C1--C2（2）C9C3C4C5C6C7C8C10C11C12拓扑序列：C1--C2--C3（3）当前第94页\共有141页\编于星期五\0点94C4C5C6C7C8C9C10C11C12拓扑序列：C1--C2--C3--C4（4）C5C6C7C8C9C10C11C12拓扑序列：C1--C2--C3--C4--C5（5）当前第95页\共有141页\编于星期五\0点95C6C8C10C11C12拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10C6C7C8C9C10C11C12拓扑序列：C1--C2--C3--C4--C5--C7（6）C11拓扑序列：C1--C2--C3--C4--C5--C7--C9C6C8C9C10C12C6C8C11C12拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11当前第96页\共有141页\编于星期五\0点96C6C8C12拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6C8C12拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12C8拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8当前第97页\共有141页\编于星期五\0点97算法实现重复上述操作直至栈空为止。若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕。以邻接表作存储结构把邻接表中所有入度为0的顶点进栈栈非空时，输出栈顶元素Vj并退栈；在邻接表中查找Vj的直接后继Vk，把Vk的入度减1；若Vk的入度为0则进栈。当前第98页\共有141页\编于星期五\0点98在实现拓扑排序的算法中，采用邻接表作为有向图的存储结构，每个顶点设置一个单链表，每个单链表有一个表头结点，在表头结点中增加一个存放顶点入度的域count，这些表头结点构成一个数组，表头结点定义如下：typedefstruct//表头结点{Vertexdata;//顶点信息

intcount;//存放顶点入度

ArcNode*firstarc;//指向第一条弧}Vnode;

在执行拓扑排序的过程中，当某个顶点的入度为零(没有前驱顶点)时，就将此顶点输出，同时将该顶点的所有后继顶点的入度减1，相当于删除所有以该顶点为尾的弧。为了避免重复检测顶点的入度是否为零，需要设立一个栈来存放入度为零的顶点。执行拓扑排序的算法如下：当前第99页\共有141页\编于星期五\0点99

voidtopsort(VNodeadj[],intn){inti,j;intstack[MAXV],top=0;//栈stack的指针为topArcNode*p;for(i=0;i<n;i++)if(adj[i].count==0)//建入度为0的顶点栈{top++;stack[top]=i;}while(top>0)//栈不为空{i=stack[top];top--;//顶点vi出栈

printf(“％d”,i);//输出vip=adj[i].firstarc;//指向以vi为弧尾的第一条弧

while(p!=NULL){j=p->adjvex;//以vi为弧尾的弧的另一顶点vj

当前第100页\共有141页\编于星期五\0点100

while(p!=NULL){j=p->adjvex;//以vi为弧尾的弧的另一顶点vjadj[j].count--;//顶点vj的入度减1

if(adj[j].count==0)//入度为0的相邻顶点入栈{top++;stack[top]=j;}p=p->nextarc;//指向以vi为弧尾的下一条弧}}}

可见，对于有n个顶点和e条边的有向图而言，for循环中建立入度为0的顶点栈时间为O（n）；若在拓扑排序过程中不出现有向环，则每个顶点出栈、入栈和入度减1的操作在while(top>0)循环语句中均执行e次，因此拓扑排序总的时间花费为O(n+e)。

当前第101页\共有141页\编于星期五\0点101例设一个工程有11项活动，9个事件事件V1——表示整个工程开始事件V9——表示整个工程结束987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4AOE网（ActivityOnEdge）边表示活动用顶点表示事件，弧表示活动，权表示活动持续的时间；网中只有：唯一一个入度为0的点源点唯一一个出度为0的点汇点完成整项工程至少需要多少时间？哪些活动是影响工程进度的关键？7.5.2关键路径当前第102页\共有141页\编于星期五\0点102Ve(j)——表示事件Vj的最早发生时间Vl(j)——表示事件Vj的最迟发生时间ee(i)——表示活动ai的最早开始时间el(i)——表示活动ai的最迟开始时间

el(i)-ee(i)——表示完成活动ai的时间余量关键活动就是时间余量el(i)-ee(i)＝0的活动关键路径

——

路径长度最长的路径叫~关键活动

——

关键路径上的活动叫~987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4AOE网常用于表示工程的计划或进度。由于实际工程只有一个开始点和一个结束点，同时AOE网应当是无环的。

当前第103页\共有141页\编于星期五\0点103如何找ee(i)=el(i)的关键活动？设活动ai用弧<j,k>表示，其持续时间记为：dut(<j,k>)则有：（1）ee(i)=Ve(j)

（2）el(i)=Vl(k)-dut(<j,k>)jkai如何求Ve(j)和Vl(j)？(1)从Ve(1)=0开始向前递推(