数据结构课件：第7章 图

教学内容第1章绪论第2章线性表第3章栈和队列第4章串第5章数组和广义表第6章树和二叉树第7章图第8章查找第9章排序第7章图图(Graph)是一种比线性表和树更为复杂的数据结构。线性结构：是研究数据元素之间的一对一关系。在这种结构中，除第一个和最后一个元素外，任何一个元素都有唯一的一个直接前驱和直接后继。树结构：是研究数据元素之间的一对多的关系。在这种结构中，每个元素对下(层)可以有0个或多个元素相联系，对上(层)只有唯一的一个元素相关，数据元素之间有明显的层次关系。图结构：是研究数据元素之间的多对多的关系。在这种结构中，任意两个元素之间可能存在关系。即结点之间的关系可以是任意的，图中任意元素之间都可能相关。图的应用极为广泛，已渗入到诸如语言学、逻辑学、物理、化学、电讯、计算机科学以及数学的其它分支。第7章图7.1图的基本概念7.2图的存储结构7.3图的遍历7.4图的连通性问题7.5有向无环图及其应用7.6最短路径7.1图的基本概念7.1.1

图的定义和术语定义：图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：Graph＝(V,E)其中:V={x|x∈某个数据对象}是顶点的非空有穷集合；E1={(x,y)|x,y∈V}或E2={<x,y>|x,y∈V}E1是顶点间关系的有穷集合，也叫做边(edge)集合，此时的图称为无向图(Digraph)。E2表示从x到y的一条弧(Arc),且称x为弧尾,y为弧头，这样的图称为有向图(Undigraph)。例1：设有有向图G1和无向图G2，形式化定义分别是：G1=(V1，E1)V1={a,b,c,d,e}E1={<a,b>,<a,c>,<a,e>,<c,d>,<c,e>,<d,a>,<d,b>,<e,d>}G2=(V2，E2)V2={a,b,c,d}E2={(a,b),(a,c),(a,d),(b,d),(b,c),(c,d)}它们所对应的图如下图所示。abcd(b)无向图G2(a)有向图G1acbde我们用n表示图中顶点数目，用e表示边或弧的数目。下面的讨论中，不考虑顶点到其自身的弧或边，即若<vi,vj>VR,则vi≠vj。对于无向图，e的取值范围是[0，n(n-1)/2]，那么具有n(n-1)/2条边的无向图称为完全无向图，即图中任意两个不同的顶点间都有一条无向边。对于有向图，e的取值范围是[0，n(n-1)]，那么具有n(n-1)条边的有向图称为完全有向图，即图中任意两个不同的顶点间都有两条弧。有很少边或弧的图(e<n㏒n)的图称为稀疏图(Sparsegraph)，反之称为稠密图(Densegraph)。有时图的边或弧具有与它相关的数，这种与图的边或弧相关的数叫做权(Weight)。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网(Network)。abcd(b)无向图G2(a)有向图G1acbde子图：设有图G=(V，E)和G’=(V’，E’)，若V’V且E’E，则称图G’是G的子图。ABCD无向图G2AACDACABCD有向图G1的子图ABCDEABDEAABCDABCDE无向图G2的子图有向图G1顶点的邻接(Adjacent)：对于无向图G=(V，E)，若边(v,w)E，则称顶点v和w互为邻接点，即v和w相邻接。边(v,w)依附(incident)与顶点v和w。对于有向图G=(V，E)，若有向弧<v,w>E，则称顶点v“邻接到”顶点w，顶点w“邻接自”顶点v，弧<v,w>与顶点v和w“相关联”。顶点的度、入度、出度：以顶点v为头的弧的数目称为v的入度(InDegree)，记为ID(v);以v为尾的弧的数目称为v的出度(OutDegree)，记为OD(v);顶点v的度为TD(v)=ID(v)+OD(v)。

V0

V1

V2

V3一般地，如果顶点vi的度记为TD(v),那么一个有n个顶点，e条边或弧的图满足如下关系：路径、回路(环)无向图G1=（V1，E1）中从顶点v到顶点v’的路径(Path)是一个顶点序列(v=vi0，vi1，…,vim=v’),其中(vi,vi+1)E1(i=1,2,…k-1)。第一个顶点和最后一个顶点相同的路径称为回路或环。在G1中，v0,v1,v2,v3

是v0到v3的路径；

v0,v1,v2,v3,

v0是回路。如果是有向图G2=（V2，E2），则路径也是有向的。在G2中，v0,v2,v3是v0到v3的路径；v0,v2,v3,v0是回路。无向图G1有向图G2

V0

V4

V3

V1

V2

V0

V1

V2

V3序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称简单回路或环。连通、连通分量和连通图、生成树在无向图G中：如果从顶点Vi

到顶点Vj有路径，则称Vi与Vj是连通的。如果图中任意两个顶点都连通，则称G为连通图，否则称为非连通图。在非连通图G中，任何一个极大连通子图称为G的连通分量。任何连通图的连通分量只有一个，即其自身，而非连通图有多个连通分量。在一个连通图中，含有全部顶点的极小(边数最少)连通子图，称为该连通图的生成树。(包含图的所有n个结点，但只含图的n-1条边。在生成树中添加一条边之后，必定会形成回路或环)非连通图G4ABCDEFGIJKABCDE非连通图G4的三个连通分量连通图G5连通图G5的两棵生成树强连通、强连通分量和强连通图在有向图G中：存在从顶点Vi

到顶点Vj的路径，也存在从顶点Vj

到顶点Vi的路径，则称Vi与Vj是强连通的。如果图中任意两个顶点都是强连通，则称G为强连通图，否则称为非强连通图。在非强连通图G中，任何一个极大强连通子图称为G的强连通分量。任何强连通图的强连通分量只有一个，即其自身，而非强连通图有多个强连通分量。有向图G和强连通分量示例：ABCDEFABCDEF(a)有向图G(c)强连通分量2(b)强连通分量1(d)强连通分量37.1.2图的抽象数据类型定义ADTGraph{数据对象V：具有相同特性的数据元素的集合，称为顶点集。数据关系R：R={VR}VR={<v,w>|<v,w>|v,wV∧p(v,w)，<v,w>表示从v到w的弧，P(v,w)定义了弧<v,w>的信息}基本操作P：…}ADTGraph基本操作P:结构的建立和销毁:CreateGraph(&G,V,VR);//按V和VR的定义构造图G。DestroyGraph(&G);//销毁图G。对顶点的访问操作:LocateVex(G,u);//若G中存在顶点u，则返回该顶点在图中位置；否则返回其它信息。GetVex(G,v);//返回v的值。PutVex(&G,v,value);//对v赋值value。对邻接点的操作:FirstAdjVex(G,v);//返回v的第一个邻接点。若该顶点//在G中没有邻接点，则返回“空”。NextAdjVex(G,v,w);//返回v的（相对于w的）下一个邻接点。若w是v的最后一个邻接点，则返回“空”。

插入或删除顶点InsertVex(&G,v);//在图G中增添新顶点v。DeleteVex(&G,v);//删除G中顶点v及其相关的弧。插入和删除弧InsertArc(&G,v,w);//在G中增添弧<v,w>，若G是无向的，则还增添对称弧<w,v>。DeleteArc(&G,v,w);//在G中删除弧<v,w>，若G是无向的，则还删除对称弧<w,v>。遍历DFSTraverse(G,v,Visit());//从顶点v起深度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次。BFSTraverse(G,v,Visit());//从顶点v起广度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次。7.2图的存储结构

图的存储结构比较复杂，其复杂性主要表现在：任意顶点之间可能存在联系，无法以数据元素在存储区中的物理位置来表示元素之间的关系。图中顶点的度不一样，有的可能相差很大，若按度数最大的顶点设计结构，则会浪费很多存储单元，反之按每个顶点自己的度设计不同的结构，又会影响操作。

图的存储结构至少要保存两类信息：

(1)顶点的数据；

(2)顶点间的关系。

如何表示顶点间的关系？

V0

V4

V3

V1

V2

V0

V1

V2

V3常用图的存储表示图的数组(邻接矩阵)存储表示图的邻接表存储表示有向图的十字链表存储表示无向图的邻接多重表存储表示7.2.1邻接矩阵(数组)表示法基本思想：对于有n个顶点的图，用一维数组vexs[n]存储顶点信息，用二维数组A[n][n]存储顶点之间关系的信息。该二维数组称为邻接矩阵。在邻接矩阵中，以顶点在vexs数组中的下标代表顶点，邻接矩阵中的元素A[i][j]存放的是顶点i到顶点j之间关系的信息。1无向图的数组表示(1)无权图的邻接矩阵

无向无权图G=(V，E)有n(n≧1)个顶点，其邻接矩阵是n阶对称方阵，如图下图所示。其元素的定义如下：1若(vi,vj)E，即vi,vj邻接0若(vi,vj)E，即vi,vj不邻接A[i][j]=(a)无向图abcd无向无权图的数组存储(b)顶点矩阵vexsabcd0111101111011110(c)邻接矩阵(2)带权图的邻接矩阵

无向带权图G=(V，E)的邻接矩阵如下图所示。其元素的定义如下：(a)带权无向图(b)顶点矩阵无向带权图的数组存储(c)邻接矩阵354126abcde3vexsabcde∞62∞∞6∞34323∞1∞∞43∞5∞3∞5∞Wij若(vi,vj)E，即vi,vj邻接，权值为wij∞若(vi,vj)E，即vi,vj不邻接时A[i][j]=(3)无向图邻接矩阵的特性

◆邻接矩阵是对称方阵；

◆

对于顶点vi，其度数是第i行的非0元素的个数；

◆

无向图的边数是上(或下)三角形矩阵中非0元素个数。0111101111011110∞62∞∞6∞34323∞1∞∞43∞5∞3∞5∞2有向图的数组表示(1)无权图的邻接矩阵

若有向无权图G=(V，E)有n(n≧1)个顶点，则其邻接矩阵是n阶方阵，如下图所示。元素定义如下：1若<vi,vj>E，从vi到vj有弧A[i][j]=0若<vi,vj>E从vi到vj没有弧(a)有向图acbde

有向无权图的数组存储(b)顶点矩阵vexsabcde(c)邻接矩阵0110100000000111100000010(2)带权图的邻接矩阵有向带权图G=(V，E)的邻接矩阵如下图所示。其元素的定义如下：wij

若<vi,vj>E，即vi,vj邻接，权值为wij∞若<vi,vj>E，即vi,vj不邻接时A[i][j]=带权有向图的数组存储(b)顶点矩阵vexsabcde(c)邻接矩阵∞62∞∞∞∞

∞

∞

3∞

3∞1∞∞4

∞∞5∞∞

∞∞∞(a)带权有向图354126abcde3⑶有向图邻接矩阵的特性◆对于顶点vi，第i行的非0元素的个数是其出度OD(vi)；第i列的非0元素的个数是其入度ID(vi)。◆邻接矩阵中非0元素的个数就是图的弧的数目。0110100000000111100000010∞62∞∞∞∞

∞

∞

3∞

3∞1∞∞4

∞∞5∞∞

∞∞∞7.2.2邻接链表法

基本思想：对图的每个顶点建立一个单链表，存储该顶点所有邻接顶点及其相关信息。每一个单链表设一个表头结点。第i个单链表中的结点表示依附于顶点Vi的边(对有向图是以顶点Vi为尾的弧)。1结点结构与邻接链表示例

链表中的结点称为表结点，每个结点由三个域组成，如下图所示。邻接点域(adjvex)指示与顶点Vi邻接的顶点在图中的位置(顶点编号)；链域(nextarc)指向下一个与顶点Vi邻接的表结点；数据域(info)存储和边或弧相关的信息，如权值等。对于无权图，如果没有与边相关的其他信息，可省略此域。每个链表设一个表头结点(称为顶点结点)，由两个域组成，如图所示。链域(firstarc)指向链表中的第一个结点；数据域(data)存储顶点名或其他信息。adjvexinfonextarc表结点：datafirstarc顶点结点：

邻接链表结点结构

在图的邻接链表表示中，所有顶点结点用一个向量以顺序结构形式存储，可以随机访问任意顶点的链表，该向量称为表头向量，向量的下标指示顶点的序号。无向图及其邻接链表v1v2v3v4v501234MAX_VEX-1v1

v2v3

v4┇┇v5

213⋀02⋀0314⋀204⋀23⋀(a)有向图v1v2v3v4v513⋀014⋀2⋀3⋀01234MAX_VEX-1v12v20⋀v33v41┇┇┇v51(b)正邻接链表，出度直观2⋀02⋀2⋀01234MAX_VEX-1v11v22v31v42┇┇┇v513⋀04⋀(c)逆邻接链表，入度直观有向图及其邻接链表对有向图，其邻接链表有两种形式，如图所示。2邻接表法的特点◆表头向量中每个分量就是一个单链表的头结点，分量个数就是图中的顶点数目；◆在边或弧稀疏的条件下，用邻接表表示比用邻接矩阵表示节省存储空间；◆在无向图，顶点Vi的度是第i个链表的结点数；◆对有向图可以建立正邻接表或逆邻接表。正邻接表是以顶点Vi为出度(即为弧的起点)而建立的邻接表；逆邻接表是以顶点Vi为入度(即为弧的终点)而建立的邻接表；◆在有向图中，第i个链表中的结点数是顶点Vi的出(或入)度；求入(或出)度，须遍历整个邻接表；◆在邻接表上容易找出任一顶点的第一个邻接点和下一个邻接点。7.2.3十字链表法

十字链表(OrthogonalList)是有向图的另一种链式存储结构，是将有向图的正邻接表和逆邻接表结合起来得到的一种链表。

在这种结构中，每条弧的弧头结点和弧尾结点都存放在链表中，并将弧结点分别组织到以弧尾结点为头(顶点)结点和以弧头结点为头(顶点)结点的链表中。这种结构的结点逻辑结构如下图所示。弧结点tailvexheadvexinfohlinktlink顶点结点Datafirstinfirstout十字链表结点结构◆data域：存储和顶点相关的信息；◆指针域firstin：指向以该顶点为弧头的第一条弧所对应的弧结点；◆指针域firstout：指向以该顶点为弧尾的第一条弧所对应的弧结点；◆尾域tailvex：指示弧尾顶点在图中的位置；◆头域headvex：指示弧头顶点在图中的位置；◆指针域hlink：指向弧头相同的下一条弧；◆指针域tlink：指向弧尾相同的下一条弧；◆Info域：指向该弧的相关信息。弧结点tailvexheadvexinfohlinktlink顶点结点Datafirstinfirstout十字链表结点结构

下图所示是一个有向图及其十字链表(略去了表结点的info域)。从这种存储结构图可以看出，从一个顶点结点的firstout出发，沿表结点的tlink指针构成了正邻接表的链表结构，而从一个顶点结点的firstin出发，沿表结点的hlink指针构成了逆邻接表的链表结构。V0V1V2V30102∧2023∧∧30∧31∧32∧∧0213V0V1∧V2V3有向图的十字链表结构7.2.4邻接多重表

邻接多重表(AdjacencyMultilist)是无向图的另一种链式存储结构。这是一种有效的存储结构，在无向图的邻接表中，一条边(v,w)的两个表结点分别出现在以v和w为头结点的链表中，很容易求得顶点和边的信息，但在涉及到边的操作会带来不便。

邻接多重表的结构和十字链表类似，每条边用一个结点表示；邻接多重表中的顶点结点结构与邻接表中的完全相同，而表结点包括六个域，如图所示。datafirstedge顶点结点邻接多重表的结点结构表结点markivexjvexinfoilinkjlink◆Data域：存储和顶点相关的信息；◆指针域firstedge：指向依附于该顶点的第一条边所对应的表结点；◆标志域mark：用以标识该条边是否被访问过；◆ivex和jvex域：分别保存该边所依附的两个顶点在图中的位置；◆info域：保存该边的相关信息；◆指针域ilink：指向下一条依附于顶点ivex的边；◆指针域jlink：指向下一条依附于顶点jvex的边；datafirstedge顶点结点邻接多重表的结点结构表结点markivexilinkjvexinfojlink邻接多重表与邻接表的区别：

后者的同一条边用两个表结点表示，而前者只用一个表结点表示；除标志域外，邻接多重表与邻接表表达的信息是相同的，因此，操作的实现也基本相似。无向图及其多重邻接链表v1v2v3v4v1v2v3v40123

01

02∧

21∧

23

0∧3∧7.3图的遍历

图的遍历(TraveringGraph)：从图的某一顶点出发，访遍图中的其余顶点，且每个顶点仅被访问一次。图的遍历算法是各种图的其他操作的基础。◆复杂性：图的任意顶点可能和其余的顶点相邻接，可能在访问了某个顶点后，沿某条路径搜索后又回到原顶点。◆解决办法：在遍历过程中记下已被访问过的顶点。设置一个辅助向量Visited[0…n-1](n为顶点数)，其初值为0，一旦访问了顶点vi后，使Visited[i]为1或为访问的次序号。

图的遍历算法有深度优先搜索算法和广度优先搜索算法。7.3.1深度优先搜索算法

深度优先搜索(DepthFirstSearch--DFS)遍历类似树的先序遍历，是树的先序遍历的推广。1算法思想

设初始状态时图中的所有顶点未被访问，深度优先搜索从图中某个初始顶点v出发,首先访问初始顶点v,然后选择一个与顶点v相邻且没被访问过的顶点w为初始顶点,再从w出发进行深度优先搜索,直到图中与当前顶点v邻接的所有顶点都被访问过为止。显然,这个遍历过程是个递归过程。

无向图深度优先搜索遍历(a)无向图Gv1v2v3v4v5(b)G的邻接链表01234MAX_VEX-1v1

v2v3

v4┇┇v5

21⋀20⋀01⋀4⋀3⋀下图是无向图的深度优先搜索遍历示例(红色箭头)。某一种DFS次序是：v1→

v3→

v2→

v4→

v5例：求图G以V0起始点的的深度优先序列。

V0

V7

V6

V5

V4

V3

V2

V1,V6V0V1V3V2V7V5

V4V0,V1,V4,V7,V3,V2,V5,V6

V0,V1,V3,V7,V4,V2,V5图GV6由于没有规定访问邻接点的顺序，DFS序列不是唯一的DFS遍历类似树的先序遍历如果将图的顶点的未被访问邻接点看作树结点的孩子，图的深度优先遍历与树的先根遍历是类似的。图的深度优先遍历

从图中某顶点v出发：（1）访问顶点v；

（2）依次从v的未被访问的邻接点出发，对图进行深度优先遍历。树的先根遍历

若树非空

（1）访问根结点；（2）依次先根遍历各棵子树。比较2算法实现

由算法思想知，这是一个递归过程。在遍历过程中便于区分顶点是否已被访问，设置访问标志数Visited[0…n-1](n为顶点数)，其初值为0，一旦访问了顶点vi后，使Visited[i]为1。voidDFS(GraphG,intv){//算法7.4

//从顶点v出发，深度优先搜索遍历连通图Gvisited[v]=TRUE;VisitFunc(v);for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w);

//对v的尚未访问的邻接顶点w，递归调用DFS}//DFSFFFFFFFFF012345678TTTTTTTTTachdfkebg访问标志:访问次序:例如:abchdekfg812345670achkfedbg3算法分析

遍历时，对图的每个顶点至多调用一次DFS函数，因为一旦某个顶点被标志成为已被访问，就不再从它出发进行搜索。遍历图的过程实质上就是对每个顶点查找邻接顶点的过程，其耗费的时间取决于所采用的存储结构。

当用二维数组表示邻接矩阵作为图的存储结构时，查找每个顶点的邻接点所需时间为O(n2).

当以邻接表作图的存储结构时，找邻接点所需时间为O(e)，e为无向图中边的数或有向图中弧的数，此时的时间复杂度为O(n+e)。7.3.2广度优先搜索算法

广度优先搜索(BreadthFirstSearch--BFS)遍历类似树的按层次遍历的过程。1算法思想

广度优先搜索遍历的过程是：首先访问初始点vi,接着访问vi的所有未被访问过的邻接点vi1,vi2,…,vit,然后再按照vi1,vi2,…,vit的次序,访问每一个顶点的所有未被访问过的邻接点,依次类推,直到图中所有和初始点vi有路径相通的顶点都被访问过为止。下图是有向图的广度优先搜索遍历示例(红色箭头)。上述图的BFS次序是：v1→

v2→

v4→

v3→

v5(b)G’的正邻接链表13⋀014⋀2⋀3⋀01234MAX_VEX-1v12v20⋀v33v41┇┇┇v51有向图广度优先搜索遍历(a)有向图G’v1v2v3v4v5例：求图G以V0起始点的的广度优先序列。

V0

V7

V6

V5

V4

V3

V2

V1,V7V0V1V3V2V7V5

V4V0,V2,V1,V5,V6,V3,V4,V7

V0,V1,V2,V3,V4,V5,V6图GV6由于没有规定访问邻接点的顺序，BFS序列不是唯一的BFS遍历类似树的按层次遍历2算法实现

为了标记图中顶点是否被访问过，同样需要一个访问标记数组；其次，为了依次访问与vi相邻接的各个顶点，需要附加一个队列来保存访问vi的相邻接的顶点。typedefemnu{FALSE,TRUE}BOOLEAN;BOOLEANVisited[MAX_VEX];typedefstructQueue{intelem[MAX_VEX];intfront,rear;}Queue;/*定义一个队列保存将要访问顶点*/voidBFSTraverse(GraphG,Status(*Visit)(intv)){//算法7.6for(v=0;v<G.vexnum;++v)visited[v]=FALSE;//初始化访问标志

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

visited[v]=TRUE;Visit(v);EnQueue(Q,v);//v入队列

while(!QueueEmpty(Q)){DeQueue(Q,u);//队头元素出队并置为ufor(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))if(!visited[w]){visited[w]=TRUE;Visit(w);EnQueue(Q,w);}//if}//while}//if}//BFSTraverse

用广度优先搜索算法遍历图与深度优先搜索算法遍历图的唯一区别是邻接点搜索次序不同，因此，当以邻接表作图的存储结构时广度优先搜索算法遍历图的总时间复杂度也为O(n+e)。图的遍历可以系统地访问图中的每个顶点，因此，图的遍历算法是图的最基本、最重要的算法，许多有关图的操作都是在图的遍历基础之上加以变化来实现的。7.4图的连通性问题7.4.1无向图的连通分量与生成树对于无向图，对其进行遍历时：◆

若是连通图：仅需从图中任一顶点出发，就能访问图中的所有顶点；◆

若是非连通图：需从图中多个顶点出发。每次从一个新顶点出发所访问的顶点集序列恰好是各个连通分量的顶点集。(a)无向图Gv1v2v3v4v5(b)G的邻接链表01234MAX_VEX-1v1

v2v3

v4┇┇v5

21⋀20⋀01⋀4⋀3⋀无向图及深度优先生成森林(c)深度优先生成森林v1v2v3v4v5

如图所示的无向图是非连通图，按图中给定的邻接表进行深度优先搜索遍历，2次调用DFS所得到的顶点访问序列集是：{v1,v3,v2}和{v4,v5}⑴若G=(V,E)是无向连通图，顶点集和边集分别是V(G)，E(G)。若从G中任意点出发遍历时，E(G)被分成两个互不相交的集合：T(G)：遍历过程中所经过的边的集合；B(G)：遍历过程中未经过的边的集合；显然：E(G)=T(G)∪B(G)，T(G)∩B(G)=Ø

显然，图G’=(V,T(G))是G的极小连通子图，且G’是一棵树。G’称为图G的一棵生成树。从任意点出发按DFS算法得到生成树G’称为深度优先生成树；按BFS算法得到的G’称为广度优先生成树。深度优先遍历序列：1,2,4,8,6,3,7,5广度优先遍历序列：1,2,3,4,5,6,7,8⑵若G=(V,E)是无向非连通图，对图进行遍历时得到若干个连通分量的顶点集：V1(G),V2(G),…,Vn(G)和相应所经过的边集：T1(G),T2(G),…,Tn(G)。则对应的顶点集和边集的二元组：Gi=(Vi(G),Ti(G))(1≦i≦n)是对应分量的生成树，所有这些生成树构成了原来非连通图的生成森林。7.4.2有向图的强连通分量

对于有向图，在其每一个强连通分量中，任何两个顶点都是可达的。VG，与V可相互到达的所有顶点就是包含V的强连通分量的所有顶点。设从V可到达(以V为起点的所有有向路径的终点)的顶点集合为T1(G)，而到达V(以V为终点的所有有向路径的起点)的顶点集合为T2(G)，则包含V的强连通分量的顶点集合是：T1(G)∩T2(G)。求有向图G的强连通分量的基本步骤是：⑴对G进行深度优先遍历，生成G的深度优先生成森林T。⑵对森林T的顶点按中序遍历顺序进行编号。⑶改变G中每一条弧的方向，构成一个新的有向图G’。⑷按⑵中标出的顶点编号，从编号最大的顶点开始对G’进行深度优先搜索，得到一棵深度优先生成树。若一次完整的搜索过程没有遍历G’的所有顶点，则从未访问的顶点中选择一个编号最大的顶点，由它开始再进行深度优先搜索，并得到另一棵深度优先生成树。在该步骤中，每一次深度优先搜索所得到的生成树中的顶点就是G的一个强连通分量的所有顶点。⑸重复步骤⑷，直到G’中的所有顶点都被访问。7.4.3最小生成树最小生成树(MinimumSpanningTree)：任何具有n个顶点的连通图，至少有n-1条边，而且所有具有n-1条边的连通图都是树。若在连通图的各条边上赋以权值即网络表示相应的代价，那么，则从连通图中选择一棵总代价最小的树，即为最小代价生成树。最小生成树在实际中具有重要用途，如设计通信网。

例如：要在n个城市间建立通讯网，设图的顶点表示城市，边表示两个城市之间的通信线路，边的权值表示建造通信线路的费用。如何在保证n个城市连通的前题下最节省经费?V3V1V4V6V5V23652165546即要构造连通网的最小生成树。这应在N个顶点的所有带权的边中选取n－1条边（不构成回路），使权值之和为最小。n个城市之间，最多可能设置n(n-1)/2条线路，连通n个城市只需要修建n-1条线路，那么，如何在这些可能的线路中选择n-1条，以使总的耗费最少呢？构造最小生成树的基本原则是：◆尽可能选取权值最小的边，但不能构成回路；◆选择n-1条边构成最小生成树。以上的基本原则是基于最小生成树的MST性质：

设G=(V，E)是一个带权连通图，U是顶点集V的一个非空子集。若u∈U，v∈V-U，且(u,v)是U中顶点到V-U中顶点之间权值最小的边，则必存在一棵包含边(u,v)的最小生成树。（可以用反证法证明）普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法是利用MST性质的两种构造最小生成树的算法。7.5.1普里姆(Prim)算法1算法思想设原连通网G=(V,E)，生成的最小生成树T=(U,TE)，则算法步骤如下：(1)任选一个顶点u0放入U中，即初始U={u0}，TE={}(2)找连接U与V-U集合的一条权值最小的边即找顶点u∈U,顶点v∈V-U的权值最小的一条边(u,v)∈E；并把顶点v加入到U中，边(u,v)加入到TE中，即修改U=U+{v},TE=TE+(u,v)(3)转到（2）重复执行，直到U=V结束ABCDEF101015121287665

（a）无向网G1算法演示:Prim算法求解最小生成树ABCE101512（b）求解过程67ABCDEF1010151212865

（a）无向网G1算法演示:Prim算法求解最小生成树ABCDEF101512765（b）求解过程ABCDEF101015121287665

（a）无向网G1算法演示:Prim算法求解最小生成树ABCDEF1015765（b）求解过程6ABCDEF10101512128765

（a）无向网G1算法演示:Prim算法求解最小生成树ABCDEF1015765（b）求解过程6ABCDEF10101512128765

（a）无向网G1算法演示:Prim算法求解最小生成树ABCDEF10157665（b）求解过程ABCDEF101015121287665

（a）无向网G1算法演示:Prim算法求解最小生成树ABCDEF1015765（b）求解过程ABCDEF101015121287665

（a）无向网G1算法演示:Prim算法求解最小生成树ABCDEF1015765（b）求解过程86ABCDEF101015121287665

（a）无向网G1算法演示:Prim算法求解最小生成树BCDEF10101575（b）求解过程A6ABCDEF101015121287665

（a）无向网G1算法演示:Prim算法求解最小生成树ABCDEF101075（b）求解过程1567ABCDEF101015121287665

（a）无向网G1算法演示:Prim算法求解最小生成树ABCDEF1010125（b）求解过程E67ABCDEF101015121287665

（a）无向网G1算法演示:Prim算法求解最小生成树最小生成树ABCDEF10105E课堂练习：写出如下连通网的最小生成树。165432496102014510106165432495106最小生成树1165432495106最小生成树2最小生成树不唯一！2.算法实现说明

设用邻接矩阵(二维数组)表示图，两个顶点之间不存在边的权值为机内允许的最大值。为便于算法实现，设置一个一维数组closedge[n]，用来保存V-U中各顶点到U中顶点具有权值最小的边。数组元素的类型定义是：struct{intadjvex;/*边所依附于U中的顶点*/intlowcost;/*该边的权值*/}closedge[MAX_EDGE];iabcdegf195141827168213127aaa19141814例如:e12ee8168d3dd7213c5516e21edcbagfabcdefg所得生成树权值和=14+8+3+5+16+21=67abcdefg0123456∞19∞∞14∞1819∞5712∞∞∞5∞3∞∞∞∞73∞8∞∞12∞8∞∞16∞∞∞21∞∞2718∞∞∞1627∞3算法步骤⑴从closedge中选择一条权值(不为0)最小的边(vk,vj)，然后做：①置closedge[k].lowcost为0，表示vk已加入到U中。②根据新加入vk的更新closedge中每个元素：

vi∈V-U，若cost(i,k)≦colsedge[i].lowcost，表明在U中新加入顶点vk后，(vi,vk)成为vi到U中权值最小的边，置：Closedge[i].lowcost=cost(i,k)Closedge[i].adjvex=k

⑵重复⑴n-1次就得到最小生成树。

7.5.2克鲁斯卡尔(Kruskal)算法1算法思想设G=(V,E)是具有n个顶点的连通网，T=(U,TE)是其最小生成树。初值：U=V，TE={}。对G中的边按权值大小从小到大依次选取。⑴选取权值最小的边(vi，vj)，若边(vi，vj)加入到TE后形成回路，则舍弃该边(边(vi，vj)；否则，将该边并入到TE中，即TE=TE∪{(vi，vj)}。⑵重复⑴

，直到TE中包含有n-1条边为止。

v1v3v2v4v54857121136(a)(b)3v5v4v36(e)v14v53v2v45按kruskal算法构造最小生成树的过程(c)v143v5v4(d)v25v143v5v4Kruskal算法练习:abcdegf195141827168213ae12dcbgf714853162171218197.5有向无环图及其应用

有向无环图(DirectedAcyclingGraph，简称DAG图)：是图中没有回路(环)的有向图。

有向无环图是描述含有公共子式的表达式的有效工具。

有向无环图是一类具有代表性的图，主要用于研究工程项目的工序问题、工程时间进度问题等。一个工程(project)都可分为若干个称为活动(active)的子工程(或工序)，各个子工程受到一定的条件约束：某个子工程必须开始于另一个子工程完成之后；整个工程有一个开始点(起点)和一个终点。人们关心：◆

工程能否顺利完成?影响工程的关键活动是什么?◆

估算整个工程完成所必须的最短时间是多少?拓扑排序关键路径有向无环图的应用：7.5.1拓扑排序7.5.2关键路径7.5.1拓扑排序AOV网：在有向图中，用顶点表示活动，用有向边表示活动之间的先后关系，称为AOV网（ActivityonVertexNetwork)。拓扑序列：把AOV网中的所有顶点排成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前边。拓扑排序：构造AOV网拓扑序列的过程称为拓扑排序。例如：软件专业学生必须学习一系列基本课程课程之间的优先关系可以用有向图表示：拓扑排序序列之一：C1,C9,C2,C4,C10,C11,C3,C12,C6,C5,C7,C8

一个有向图可用来表示工程的施工图，产品的生产流程图，学生的课程安排图等。有向图的顶点对应一项子工程或一门课程等；有向边<Vi,Vj>表示子工程或课程Vi必须在Vj之前完成。对有向图的结点进行拓扑排序，对应于这些实际问题就是对各项子工程或各门课程排出一个线性的顺序关系。如果条件限制这些工作必须串行的话，那就应该按拓扑排序安排执行的先后顺序。设有一项工程，有六项子工程第一项：无条件；第二项：在第一、三项完成之后；第三项：在第一项之后；第四项：在第一、六项之后；第五项：在第三、四、六项之后；第六项：无条件；该工程的先后关系可用有向图表示。拓扑序列1，3，2，6，4，56,1,4,3，2,5拓扑排序方法实现步骤如下（对象：无环有向图）：（1）选一个入度为0的顶点（没有前驱）且输出之；（2）从图中删除此顶点及该顶点发出来（以它为始点）的弧；（3）重复（1）、（2）两步，直到图中不存在入度为0的顶点或所有顶点都被输出（此时若图中仍有顶点，则是有环图）。拓扑排序的过程C0C1C2C3C4C5(a)有向无环图C1C2C5C3(c)输出顶点C0C0C2C5C1C3(d)输出顶点C3C0C1C2C3C4C5(b)输出C4C1C2C5(e)输出顶点C2C5C1(f)输出顶点C1C5(g)输出顶点C5最后得到的拓扑有序序列为C4,C0,C3,C2,C1,C5

。它满足图中给出的所有前驱和后继关系，对于本来没有这种关系的顶点，如C4和C2，也排出了先后次序关系。(h)拓扑排序完成拓扑排序序列不唯一！7.5.2关键路径(CriticalPath)

与AOV网相对应的是AOE(ActivityOnEdge)，是边表示活动的有向无环图，如下图所示。图中顶点表示事件(Event)，每个事件表示在其前的所有活动已经完成，其后的活动可以开始；弧表示活动，弧上的权值表示相应活动所需的时间或费用。v0v6v5v4v3v2v1v7v8a1=3a2=10a3=9a4=13a5=12a6=7a7=8a9=6a10=11a12=5a8=4a11=2一个AOE网源点事件V4表示以V4为弧头的所有活动已经完成，同时，也表示以V4为弧尾的所有活动可以开始汇点AOE网具有性质：v0v6v5v4v3v2v1v7v8a1=3a2=10a3=9a4=13a5=12a6=7a7=8a9=6a10=11a12=5a8=4a11=2一个AOE网(1)只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始；(2)只有在进入某一顶点的各有向边所代表的活动都已经结束，该顶点所代表的事件才能发生；(3)表示实际工程计划的AOE网应该是无环的，并且存在惟一的入度过为0的开始顶点(源点）和惟一的出度为0的完成顶点（汇点）。只有当所有路径上的活动都完成后，工程才能完成。如果用AOE网来表示一项工程，有待研究的问题是:(1)完成整个工程至少需要多少时间（从源点到汇点至少需要多少时间）；(2)哪些活动是影响工程进度的关键。路径长度：路径上各活动持续时间的总和，即路径上所有弧的权值之和。关键路径：所有从源点到汇点的路径中，长度最长的路径，称为关键路径。关键活动：关键路径上的活动为关键活动。为了寻找关键活动，确定关键路径，我们先定义几个变量：(1)事件vi的最早发生时间ve(i)：从源点到vi的最长路径长度。(2)事件的最迟发生时间vl(i)：完成顶点vn的最早发生时间ve(n)减去vi到vn的最长路径长度。(3)活动ai的最早开始时间e(i)：事件vj的最早发生时间ve(j)也是所有以vj为起点的出边<vj,vk>所表示的活动ai的最早开始的时间，即e(i)=ve(j)。(4)活动ai的最迟开始时间l(i)：是该活动的弧头事件vk的最迟发生时间减去ai的持续时间，即l(i)=vl(k)-<vj,,vk>的权。通常把e(i)=l(i)的活动称为关键活动。由此可见，在AOE网中找关键活动问题可转化为求e(i)=l(i)，而e(i)=ve(j)，l(i)=vl(k)-<vj,,vk>的权。因此，需先求出事件的最早、最迟发生时间。求AOE中关键路径和关键活动算法思想①利用拓扑排序求出AOE网的一个拓扑序列；

②从拓扑排序的序列的第一个顶点(源点)开始，按拓扑顺序依次计算每个事件的最早发生时间ve(i)；

③从拓扑排序的序列的最后一个顶点(汇点)开始，按逆拓扑顺序依次计算每个事件的最晚发生时间vl(i)；

对于右图AOE网，处理过程如下：◆拓扑排序的序列是：(v0,v1,v2,v3,

v4,v5,v6,v7,v8)◆计算各个事件的ve(i)和vl(i)值，如表中所示。v0v6v5v4v3v2v1v7v8a1=3a2=10a3=9a4=13a5=12a6=7a7=8a9=6a10=11a12=5a8=4a11=2顶点v0v1v2v3v4v5v6v7v8ve(i)0310122217202833vl(i)0910232217312833◆根据关键路径的定义，知该AOE网的关键路径是：(v0,v2,v4,v7,v8)和(v0,v2,v5,v7,v8)。◆关键路径活动是：<v0,v2>，<v2,v4>，<v2,v5>，<v4,v7>，<v5,v7>，<v5,v8>。7.6最短路径

若用带权图表示交通网，图中顶点表示地点，边代表两地之间有直接道路，边上的权值表示路程(或所花费用或时间)。从一个地方到另一个地方的路径长度表示该路径上各边的权值之和。问题：◆

两地之间是否有通路?◆

在有多条通路的情况下，哪条最短?

考虑到交通网的有向性，直接讨论的是带权有向图的最短路径问题，但解决问题的算法也适用于无向图。

将一个路径的起始顶点称为源点，最后一个顶点称为终点。7.6.1单源点最短路径带权有向图中从V0到其余各顶点之间的最短路径：如何求从源点到其余各点的最短路径？算法的基本思想:依最短路径的长度递增的次序求得各条最短路径其中，从源点到顶点v的最短路径是所有最短路径中长度最短者。路径长度最短的最短路径的特点：在这条路径上，必定只含一条弧，并且这条弧的权值最小，不妨