假设图G采用邻接表存储课件

第七章图第7章图一、教学内容：1、图的基本概念2、图的存储结构（邻接矩阵、邻接表）；3、图的遍历（深度优先搜索、广度优先搜索）；4、最小生成树（kruskul算法、prim算法）；5、最短路径（dijkstra算法、floyd算法）;6、AOV网络与拓扑排序；7、AOE网络与关键路径。第7章图二、教学要求：1、理解图的基本概念，熟悉图的各种存储结构及其构造算法；2、熟练掌握图的两种搜索路径的遍历；3、掌握构造最小生成树的方法，并理解算法；4、掌握用Dijkstra方法求解单源最短路径问题，理解Floyd（弗洛伊德）算法思想；5、掌握求活动网络的拓扑排序的方法，并理解算法；6、掌握求解关键路径的方法。第7章图教学重点：

图的定义、术语及其含义，各种图的邻接矩阵表示法及其类型说明，图的按深度优先搜索遍历方法和按广度优先搜索遍历方法，生成树和最小生成树的概念，Prim算法，拓扑序列和拓扑排序的概念和算法思想，关键路径的算法思想，最短路径的算法思想。教学难点：

图的存储表示、关键路径，最短路径算法。引言图（Graph）是一种较线性表和树更为复杂的数据结构。图形结构中，结点之间的关系可以是任意的，任意两个数据元素之间都可能相关。

应用广泛:

如电路网络分析、交通运输、管理与线路的铺设、印刷电路板与集成电路的布线等众多直接与图有关的问题，它们必须用图的有关方法进行处理；另外像工作的分配、工程进度的安排、课程表的制订、关系数据库的设计等许多实际问题，如果间接地用图来表示，处理起来比较方便。问题的提出假设有”平顶山”、”郑州”、”洛阳”、”许昌”、”漯河”五城市的交通图如下,完成如下要求：

1：对任意输入的两个城市，输出它们之间的直接距离，有则输出实际距离，无则输出道路不直接相通。

2：对任意一个城市，输出都能够直接通达哪些城市，距离多少？51324平顶山郑州洛阳许昌漯河100150120150200180第7章图7.1图的定义和术语

7.2图的存储结构7.3图的遍历操作7.4图的连通性问题7.5有向无环图及其应用7.6最短路径7.1图的定义和术语1、图的结构定义、图形结构特点2、顶点、弧、边、弧头、弧尾3、无向图和有向图4、完全图和有向完全图5、网、子图6、顶点的度、入度和出度、边、弧与各顶点度的关系7.1图的定义和术语7、路径、路径长度、回路（环）、简单路径8、连通、连通图、连通分量9、强连通图、强连通分量10、生成树、有向树、生成森林7.2图的存储表示图的数组(邻接矩阵)存储表示（重点）图的邻接表存储表示（重点）有向图的十字链表存储表示无向图的邻接多重表存储表示回答问题1、什么是图形结构？它和线性结构、树形结构有何区别？2、以下图为例，理解图的相关术语，并回答有关问题。G1ABCDABCDEG2回答问题（1）G1中，A到D的路径是什么？路径长度多少？（2）G2中，A到E的路径是什么？路径长度多少？（3）G1是强连通图吗？若不是找出其强连通分量？（4）写出G2的生成树；（5）写出G1的生成森林；回答问题（6）写出G1的邻接矩阵、邻接表和十字链表；（7）写出G2的邻接矩阵、邻接表和邻接多重表。3、如下所示为一带权有向图，写出其邻接矩阵、邻接表。V1V2V3V440105020邻接矩阵的结构定义：#defineMAX_VERTEX_NUM20Typedef

enum{DG,DN,UDG,UDN}Graphkind;typedef

struct

ArcCell{//弧的定义

VRType

adj;//VRType是顶点关系类型。

//对无权图，用1或0表示相邻否；

//对带权图，则为权值类型。

InfoType*info;//该弧相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef

struct{//图的定义

VertexType//顶点信息

vexs[MAX_VERTEX_NUM];

AdjMatrixarcs;//弧的信息

int

vexnum,arcnum;//顶点数，弧数

GraphKindkind;//图的种类标志

}

MGraph;（1）矩阵不一定是对称的;（2）第i行中1的个数为顶点i的出度;（3）第i列中1的个数为顶点i的入度;（4）矩阵中1的个数为图中弧的数目;（5）很容易判断顶点i和顶点j是否有弧相连.从有向图的邻接矩阵可以得出如下结论从无向图的邻接矩阵可以得出如下结论（1）矩阵是对称的，可压缩存储（上（下）三角;（2）第i行或第i列中1的个数为顶点i的度;（3）矩阵中1的个数的一半为图中边的数目;（4）很容易判断顶点i和顶点j之间是否有边相连(看矩阵中i行j列值是否为1)。

容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。仅耗费O(1)时间。n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。对稀疏图而言尤其浪费空间。邻接矩阵法优点：邻接矩阵法缺点：邻接矩阵存储表示特点邻接表表示图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法，它包括两部分：一部分是单链表，用来存放边的信息；另一部分是数组，主要用来存放顶点本身的数据信息。表结点头结点adjvex

nextarcinfo

datafirstarc指示与顶点Vi邻接的点在图中的位置指示下一条边或弧的结点信息可无存储顶点Vi的名或其他信息指示链表中第一个结点从无向图的邻接表可以得到如下结论：

（1）第i个链表中结点数目为顶点i的度；（2）所有链表中结点数目的一半为图中边数；（3）占用的存储单元数目为n+2e。从有向图的邻接表可以得到如下结论：（1）第i个链表中结点数目为顶点i的出度；（2）所有链表中结点数目为图中弧数；（3）占用的存储单元数目为n+e。邻接表表示邻接表表示邻接表的缺点：邻接表的优点：空间效率高；容易寻找顶点的邻接点；判断任意两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。图的邻接表数据类型描述#defineMAXN50/*MAXN表示图中最大顶点数*/typedef

struct

arcnode//定义边结点的结构{int

adjvex;//该弧所指向的顶点的位置struct

arcnode

*nextarc;//指向下一条弧的指针InfoType*info;}arcnode;typedef

struct

vnode//定义邻接表的表头类型{VertexTypedata;//顶点信息

arcnode

*firstarc;//指向第一条依附该顶点的弧}vnode;Adjlist[MAXN];讨论：邻接表与邻接矩阵有什么异同之处？1.联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。2.区别：①对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。②邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。3.用途：邻接矩阵多用于稠密图的存储（e接近n(n-1)/2)；而邻接表多用于稀疏图的存储（e<<n2)弧的结点结构弧尾顶点位置弧头顶点位置弧的相关信息指向下一个有相同弧尾的结点指向下一个有相同弧头的结点typedef

struct

ArcBox

{//弧的结构表示

int

tailvex,headvex;

InfoType*info;

struct

ArcBox

*hlink,

*tlink;

}

VexNode;三、有向图的十字链表存储表示tailvex

headvex

hlink

tlinkinfo顶点的结点结构顶点信息数据指向该顶点的第一条入弧指向该顶点的第一条出弧typedef

struct

VexNode

{//顶点的结构表示

VertexTypedata;

ArcBox

*firstin,

*firstout;}

VexNode;datafirstin

firstouttypedef

struct{

VexNode

xlist[MAX_VERTEX_NUM];//顶点结点(表头向量)

int

vexnum,arcnum;//有向图的当前顶点数和弧数}

OLGraph;有向图的结构表示(十字链表)边的结点结构标志顶点Vi位置顶点Vj位置边的相关信息指向下一条依附于Vj的边指向下一条依附于Vi的边四、无向图的邻接多重表存储表示markivex

ilink

jvex

jlinkinfo顶点的结点结构顶点信息数据

指向第一条依附于该顶点的边datafirstedge

7.3图的遍历

从图中某个顶点出发遍历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。图的遍历有两种方法：深度优先搜索遍历（DFS）广度优先搜索遍历（BFS）。它们对无向图和有向图都适用。

从图中某个顶点V0出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到。

深度优先搜索遍历类似于树的先序遍历。1．图的深度优先搜索

(1)首先访问顶点i，并将其访问标记置为访问过，即visited[i]=1；

(2)然后搜索与顶点i有边相连的下一个顶点j，若j未被访问过，则访问它，并将j的访问标记置为访问过，visited[j]=1，然后从j开始重复此过程，若j已访问，再看与i有边相连的其它顶点；

(3)若与i有边相连的顶点都被访问过，则退回到前一个访问顶点并重复刚才过程，直到图中所有顶点都被访问完为止。假定给定图G的初态是所有顶点均未被访问过，在G中任选一个顶点i作为遍历的初始点，则深度优先搜索遍历可定义如下：例如，对下面所示无向图G7，从顶点1出发的深度优先搜索遍历序列可有多种，下面仅给出三种，其它可作类似分析。在无向图G7中，从顶点1出发的深度优先搜索遍历序列举三种为：

1,2,4,8,5,6,3,71,2,5,8,4,7,3,61,3,6,8,7,4,2,5深度优先搜索特点

若图是连通的或强连通的，则从图中某一个顶点出发可以访问到图中所有顶点，否则只能访问到一部分顶点。另外，从刚才写出的遍历结果可以看出，从某一个顶点出发的遍历结果是不唯一的。但是,若我们给定图的存贮结构,则从某一顶点出发的遍历结果应是唯一的。Booleanvisited[MAX];Status(*visitfunc)(intv);//visitfunc为指向函数的指针变量voidDFSTraverse(GraphG,Status(*Visit)(intv)){//对图G作深度优先遍历。

VisitFunc=Visit;for(v=0;v<G.vexnum;++v)visited[v]=FALSE;//访问标志数组初始化

for(v=0;v<G.vexnum;++v)

if(!visited[v])DFS(G,v);//对尚未访问的顶点调用DFS}voidDFS(GraphG,intv){//从顶点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}//DFS分析上述过程，在遍历图时，对图中每个顶点至多调用一次dfs过程，因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。因此，遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。深度优先搜索算法分析深度优先搜索算法分析(1)

用邻接矩阵实现图的深度优先搜索深度优先搜索算法分析当用二维数组表示邻接矩阵作图的存储结构时，查找每个顶点的邻接点所需时间为O（n2），其中n为图中顶点数。采用邻接矩阵存储结构求图G中顶点v的第一个邻接点

int

FirstAdjVex(MGraph

G,intv){for(inti=0;i<G.n;i++)if(G.edges[v][i]==1)returni;return-1;}采用邻接矩阵存储结构求图G中顶点v相对于w的下一个邻接点

int

NextAdjVex(MGraph

G,intv，intw){for(int

i=w;i<G.n;i++)if(G.edges[v][i]==1)returni;return-1;}深度优先搜索算法分析2.用邻接表实现图的深度优先搜索深度优先搜索算法分析当以邻接表作图的存储结构时，找邻接点所需时间为O（e），其中e为无向图中边的数或有向图中弧的数。由此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为O（n＋e）。采用邻接表存储结构求图G中顶点v的第一个邻接点

int

FirstAdjVex(ALGraph

G,intv){ArcNode

*p=G.adjlist[v].firstarc;if(p!=NULL)returnp->adjvex;elsereturn-1;}采用邻接表存储结构求图G中顶点v相对于w的下一个邻接点

int

NextAdjVex(ALGraph

G,intv，intw){ArcNode

*p=G.adjlist[v].firstarc;while(p!=NULL&&p->adjvex!=w)

p=p->nextarc;if(p)returnp->adjvex;elsereturn-1;}非连通图的深度优先搜索若图是非连通的或非强连通图，则从图中某一个顶点出发。不能用深度优先搜索访问到图中所有顶点，而只能访问到一个连通子图（既连通分量）或只能访问到一个强连通子图（既强连通分量）。这时，可以在每个连通分量或每个强连通分量中都选一个顶点，进行深度优先搜索遍历，最后将每个连通分量或每个强连通分量的遍历结果合起来，则得到整个非连通图的遍历结果。遍历算法实现与连通图的只有一点不同，即对所有顶点进行循环，反复调用连通图的深度优先搜索遍历算法即可。2．图的广度优先搜索从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

广度优先搜索遍历类似于树的按层次遍历。设图G的初态是所有顶点均未访问，在G中任选一顶点i作为初始点，则广度优先搜索的基本思想是：

(1)首先访问顶点i，并将其访问标志置为已被访问，即visited[i]=1；

(2)接着依次访问与顶点i有边相连的所有顶点W1，W2，…，Wt；

(3)然后再按顺序访问与W1，W2，…，Wt有边相连又未曾访问过的顶点；依此类推，直到图中所有顶点都被访问完为止。

voidBFSTraverse(GraphG,

Status(*Visit)(intv)){

for(v=0;v<G.vexnum;++v)visited[v]=FALSE;//初始化访问标志

InitQueue(Q);//置空的辅助队列Q

for(v=0;v<G.vexnum;++v)

if(

!visited[v]){//v尚未访问

visited[v]=TRUE;Visit(v);//访问u

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);

//访问的顶点w入队列

}//if}//while}//if}//BFSTraverse

例如，对图8-13所示无向图G7，从顶点1出发的广度优先搜索遍历序列可有多种，下面仅给出三种，其它可作类似分析。

在无向图G7中，从顶点1出发的广度优先搜索遍历序列举三种为：1,2,3,4,5,6,7,81,3,2,7,6,5,4,81,2,3,5,4,7,6,8用邻接矩阵实现图的广度优先搜索遍历若从顶点1出发，广度优先搜索序列为：1，2，3，4，5，6，7，8。若从顶点3出发，广度优先搜索序列为：3，1，6，7，2，8，4，5,从其它点出发的广度优先搜索序列可根据同样类似方法分析。用邻接表实现图的广序优先搜索遍历若从顶点1出发，广度优先搜索序列为：1，2，3，4，5，6，7，8，若从顶点7出发，广度优先搜索序列为：7，3，8，1，6，4，5，2，从其它顶点出发的广度优先搜索序列可根据同样类似方法分析。广度优先搜索算法分析分析前述过程，每个顶点至多进一次队列。遍历图的过程实质上是通过边或弧找邻接点的过程、因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，两者不同之处仅仅在于对顶点访问的顺序不同。图遍历的应用1、假设图G采用邻接表存储，设计一个算法，判断无向图G是否连通。若连通则返回1；否则返回0。intConnect(ALGraph

*G) /*判断无向图G的连通性*/{

inti,flag=1; for(i=0;i<G->n;i++) /*visited数组置初值*/ visited[i]=0; DFS(G,0);/*调用DSF算法,从顶点0开始深度优先遍历*/ for(i=0;i<G->n;i++) if(visited[i]==0) { flag=0; break; }returnflag;}2、假设图G采用邻接表存储，设计一个算法，输出图G中从顶点u到v的长度为l的所有简单路径。分析：所谓简单路径是指路径上的顶点不重复。利用回溯的深度优先搜索方法。从顶点u开始，进行深度优先搜索，在搜索过程中，需要把当前的搜索线路记录下来。为此设立一个数组path保存走过的路径，用d记录走过的路径长度。若当前扫描到的结点u等于v且路径长度为l时，表示找到了一条路径，则输出路径path。对应的算法如下：voidPathAll(ALGraph

*G,int

u,int

v,int

l,intpath[],intd)/*d是到当前为止已走过的路径长度，调用时初值为-1*/{

int

m,i;ArcNode*p;visited[u]=1;d++;/*路径长度增1*/

path[d]=u; /*将当前顶点添加到路径中*/if(u==v&&d==l) /*输出一条路径*/{printf("");for(i=0;i<=d;i++)printf("%d",path[i]);

printf("\n");}p=G->adjlist[u].firstarc;/*p指向u的第一条弧的弧头结点*/while(p!=NULL){m=p->adjvex; /*m为u的邻接顶点*/ if(visited[m]==0) /*若顶点未标记访问,则递归访问之*/

PathAll(G,m,v,l,path,d); p=p->nextarc /*找u的下一个邻接顶点*/}visited[u]=0;

/*恢复环境*/}7.4图的连通性问题一、无向图的连通分量和生成树

若图是连通的或强连通的，则从图中某一个顶点出发可以访问到图中所有顶点；若图是非连通的或非强连通图，则需从图中多个顶点出发搜索访问而每一次从一个新的起始点出发进行搜索，搜索过程中得到的顶点访问序列恰为每个连通分量中的顶点集。DEABCFJLMGHIKDEGHIKABCFJLM

对于连通图，

深度优先搜索遍历算法及广度优先搜索遍历算法中遍历图过程中历经边的集合和顶点集合一起构成连通图的极小连通子图。它是连通图的一棵生成树。生成树：是一个极小连通子图，它含有图中全部顶点，但只有n-1条边。

由深度优先搜索遍历得到的生成树，称为深度优先生成树，由广度优先搜索遍历得到的生成树，称为广度优先生成树。1、连通图的生成树例1：画出下图的生成树DFS生成树v0v1v2v4v4v3邻接表01234^1334^142^0v4v3v2v1v023^142^0v0v2v1v4v3BFS生成树v0v1v3v2v4无向连通图2．生成森林

若一个图是非连通图或非强连通图，但有若干个连通分量或若干个强连通分量，则通过深度优先搜索遍历或广度优先搜索遍历，不可以得到生成树，但可以得到生成森林，且若非连通图有

n

个顶点，m个连通分量或强连通分量，则可以遍历得到m棵生成树，合起来为生成森林，森林中包含n-m条树边。

生成森林可以利用非连通图的深度优先搜索遍历或非连通图的广度优先搜索遍历算法得到。3．最小生成树

在一般情况下，图中的每条边若给定了权，这时，我们所关心的不是生成树，而是生成树中边上权值之和。若生成树中每条边上权值之和达到最小，称为最小生成树。构造最小生成树的准则必须只使用该网络中的边来构造最小生成树；必须使用且仅使用n-1条边来联结网络中的n个顶点；不能使用产生回路的边。欲在n个城市间建立通信网，则n个城市应铺n-1条线路；但因为每条线路都会有对应的经济成本，而n个城市可能有n(n-1)/2条线路，那么，如何选择n–1条线路，使总费用最少？典型用途：数学模型：顶点———表示城市，有n个；边————表示线路，有n–1条；边的权值—表示线路的经济代价；连通网——表示n个城市间通信网。问题抽象：

n个顶点的生成树很多，需要从中选一棵代价最小的生成树，即该树各边的代价之和最小。此树便称为最小生成树MST(MinimumcostSpanningTree)显然此连通网是一个生成树！4、求最小生成树的两种方法普里姆算法和克鲁斯卡尔算法普里姆(prim)算法思想

在图中任取一个顶点k作为开始点，令U={k}，W=V-U，其中V为图中所有顶点集，然后找一个顶点在U中，另一个顶点在W中的边中最短的一条，找到后，将该边作为最小生成树的树边保存起来，并将该边顶点全部加入U集合中，并从W中删去这些顶点，然后重新调整U中顶点到W中顶点的距离,使之保持最小，再重复此过程，直到W为空集止。例1654326513566425131163141643142116432142516543214253Prim算法构造最小生成树过程abcdegf例如:利用普里姆算法构造最小生成树195141827168213ae12dcbgf7148531621所得生成树权值和=14+8+3+5+16+21=67

假设开始顶点就选为顶点1，故首先有U={1}，W={2，3，4，5，6}i123456closest[i]111111lowcost[i]0615∞∞closest用于存放顶点序号lowest存放权值i123456closest[i]131133lowcost[i]050554i123456closest[i]131633lowcost[i]050250i123456closest[i]131633lowcost[i]050050i123456closest[i]131623lowcost[i]000030i123456closest[i]131623lowcost[i]000000求最小生成树的两种方法克鲁斯卡尔（kruskal）算法考虑问题的出发点:为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。算法思想：将图中所有边按权值递增顺序排列，依次选定取权值较小的边，但要求后面选取的边不能与前面选取的边构成回路，若构成回路，则放弃该条边，再去选后面权值较大的边，n个顶点的图中，选够n-1条边即可。克鲁斯卡尔算法构造最小生成树过程例如:利用克鲁斯卡尔算法构造最小生成树abcdegf195141827168213ae12dcbgf71485316217121819

为了简便,在实现克鲁斯卡尔算法Kruskal()时,参数E存放图G中的所有边,假设它们是按权值从小到大的顺序排列的。n为图G的顶点个数,e为图G的边数。

typedef

struct

{ intu;/*边的起始顶点*/

intv;/*边的终止顶点*/

intw;/*边的权值*/}Edge;voidKruskal(EdgeE[],int

n,inte){inti,j,m1,m2,sn1,sn2,k;int

vset[MAXV];for(i=0;i<n;i++)vset[i]=i; /*初始化辅助数组*/k=1;/*k表示当前构造最小生成树的第几条边,初值为1*/j=0;/*E中边的下标,初值为0*/while(k<n)/*生成的边数小于n时循环*/{m1=E[j].u;m2=E[j].v; /*取一条边的头尾顶点*/ sn1=vset[m1];sn2=vset[m2];/*分别得到两个顶点所属的集合编号*/

if(sn1!=sn2) /*属不同的集合->最小生成树的一条边*/ {printf("(%d,%d):%d\n",m1,m2,E[j].w); k++; /*生成边数增1*/ for(i=0;i<n;i++)/*两个集合统一编号*/ if(vset[i]==sn2)/*集合编号为sn2的改为sn1*/

vset[i]=sn1; } j++; /*扫描下一条边*/}}

完整的克鲁斯卡尔算法应包括对边按权值递增排序，上述算法假设边已排序的情况下，时间复杂度为O(n2)。如果给定的带权连通无向图G有e条边,n个顶点，采用堆排序(在第11章中介绍)对边按权值递增排序，那么用克鲁斯卡尔算法构造最小生成树的时间复杂度降为O(elog2e)。由于它与n无关，只与e有关，所以说克鲁斯卡尔算法适合于稀疏图。普里姆算法和克鲁斯卡尔算法分析普里姆算法的时间复杂度为O（n2），与网中的边数无关，适用于求边稠密的网的最小生成树。克鲁斯卡尔算法的时间复杂度为

O（eloge），适合于求边稀疏的网的最小生成树。作业11、假设图G采用邻接表存储，分别设计实现以下要求的算法：（1）求图G中每各顶点的出度；（2）求图G中出度最大的一个顶点，输出该顶点编号；（3）计算图G中出度为0的顶点数；（4）判断图G中是否存在边<i，j>。2、假设图G采用邻接表存储，编写一个实现连通图G的深度优先遍历（从顶点v出发）的非递归算法。第7章图7.1图的定义和术语7.2图的存储结构7.3图的遍历操作7.4图的连通性问题7.5有向无环图及其应用7.6最短路径

7.5有向无环图及其应用一个无环的有向图称做有向无环图(DAG）。它在我们的生活中有广泛的应用。有向无环图是描述含有公共子式的表达式的有效工具。有向无环图也是描述一项工程或系统的进行过程的有效工具。对整个工程和系统，人们关心的是两个方面的问题：一是工程能否顺利进行；二是估算整个工程完成所必须的最短时间。7.5.1拓扑排序问题1：假设以有向图表示一个工程的施工图或程序的流程图，则程序中能否出现回路？问题2：如何检查有向图中是否存在回路？问题3：何谓拓扑排序？

拓扑排序拓扑排序：由某个集合上的一个偏序得到该集合上的一个全序，这个操作称为拓扑排序。

(a)偏序(b)全序V1V4V3V2V1V4V3V2

拓扑排序何谓拓扑排序?

换句话说：对有向图进行如下操作，按照有向图给出的次序关系，将图中的顶点排成一个线性序列，对于没有限定次序关系的顶点，则可以人为加上任意的次序关系。问题4：如何进行拓扑排序？拓扑排序方法：

(1)从入度为0的顶点（如v0）开始；

(2)输出v0，将与之相关联的尾端弧删除；

(3)重复上述两步，直至图中全部顶点已输出，或不存在无前驱顶点为止。

前一种情况说明有向图中不存在环，后一种情况则说明有向图中存在环。

检测一个有向图是否存在回路的方法：对有向图构造其顶点的拓扑有序序列，若图中所有顶点都在它的拓扑有序序列中，则该图中必定不存在环。拓扑排序拓扑序列1：C1-C2-C3-C5-C8-C4-C9-C6-C7拓扑序列2：C2-C5-C1-C3-C8-C4-C9-C6-C7问题5：有向图的拓扑有序序列是否唯一？C8C3C5C4C9C6C7C1C2拓扑排序分析：（1）拓扑排序最关键的操作是什么？（2）图的存储结构？（3）如何处理多个入度为0的顶点？问题6：如何在计算机内实现有向图的拓扑排序？拓扑排序实现拓扑排序的算法基础

存贮结构:假设有向图以邻接表的形式存储操作过程:将所有入度为0的顶点入栈；

当栈非空时重复执行下列操作：从栈中退出顶点k；（1）将k顶点的信息输出；（2）将与k邻接的所有顶点的入度减1。拓扑排序栈示例:C0C1C2C3C4C5

C0C1C2C30C4C50degreedataadj

130103

1

vexlink

30

5

1

50

0

1

50拓扑排序算法的时间复杂度分析如果给定的有向图有n个顶点和e条边，那么求各顶点入度的时间为O（e），在拓扑排序的过程中，查找入度为零的顶点的时间为O（n），顶点进栈及退栈输出共执行n次，入度减1的操作执行e次，所以，总的执行时间为O（n+e）。拓扑排序问题7:什么是AOV网?C8C3C5C4C9C6C7C1C27.5.2关键路径问题1:什么是AOE网?有什么用?假设以有向网表示一个施工流程图，弧上的权值表示完成该项子工程所需时间。

问：哪些子工程项是“关键工程”？

即：哪些子工程项将影响整个工程的完成期限

整个工程完成的时间为：从有向图的源点到汇点的最长路径关键路径

关键路径示例:p183图7.29v0v1v2v3v4v5v6v7v864521187244源点汇点6174关键路径相关术语:

源点:p183

汇点:p183AOE网:p183

关键路径:p183

关键活动:p183

缩短工期结论:p186关键路径

求关键路径的目的:求关键活动

确定哪些是关键活动,关键活动就是要找最早开始时间e(i)与最迟开始时间l(i)相等的活动,要首先确定事件的最早开始时间ve(i)和最迟开始时间vl(i).

关键路径

求关键活动:假设第i条弧为<j,k>,如果弧为<j,k>的持续时间为dut(<j,k>),则对第j个顶点而言“事件(顶点)”的最早发生时间ve(j),ve(k)“事件(顶点)”的最迟发生时间vl(j),vl(k)对第i项活动而言“活动(弧)”的最早开始时间e(i)“活动(弧)”的最迟开始时间l(i)e(i)=ve(j)

l(i)=vl(k)-dut(<j,k>)所以：要先求事件的最早和最晚发生时间关键路径第一步:事件i的最早发生时间,前边活动都完成，最长路径长度从