超级盘数据结构七章图

7.1图的定义和术语7.2图的存储表示7.3图的遍历7.4.1最小生成树7.4图的应用7.4.2最短路径7.4.3拓扑排序7.4.4关键路径第七章图柯尼斯堡七桥问题欧拉定理:对于一个连通图，如果它的奇点(通过此点边的条数是奇数)个数为0或2，则能不重复的遍历每一条边，否则则不能。图的应用领域：电路分析、最短路径、工程规划、化合物分类、统计力学、自动化、语言学、社会科学，等等。图结构是最广泛使用的数学结构。图是由一个顶点集V和一个弧集R构成的数据结构。Graph=(V,R)V={x|x∈GElemSet}集合V中的所有元素具有相同的特性R={VR}其中，VR＝{<v,w>|v,w∈V}

<v,w>表示从v到w的一条弧(Arc)，并称v为弧尾(Tail)，w为弧头(Head)。图的结构定义:vw7.1图的定义和术语

由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图。

ABECD例如:G1=(V1,VR1)其中V1={A,B,C,D,E}VR1={<A,B>,<A,E>,<B,C>,<C,D>,<D,B>,<D,A>,<E,C>}若<v,w>VR必有<w,v>VR,则称

(v,w)为顶点v和顶点w之间存在一条边。

BCADFE由顶点集和边集构成的图称作无向图。例如:G2=(V2,VR2)V2={A,B,C,D,E,F}VR2={(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F)}名词和术语网、子图

完全图、稀疏图、稠密图邻接点、度、入度、出度路径、路径长度、简单路径、简单回路连通图、连通分量、强连通图、强连通分量生成树、生成森林ABECFAEFBBC设图G=(V,{VR})和图G=(V,{VR}),且VV,VRVR,则称G为G的子图。1597211132

弧或边带权的图分别称作有向网或无向网。图G图G

假设图中有

n

个顶点，e

条边，则

含有e=n(n-1)/2条边的无向图称作完全图；

含有e=n(n-1)条弧的有向图称作

有向完全图；若边或弧的个数e<nlogn，则称作稀疏图，否则称作稠密图。

假若顶点v和顶点w之间存在一条边，则称顶点v和w互为邻接点，ACDFE例如:ID(B)=3ID(A)=2边(v,w)

和顶点v和w相关联。

和顶点v关联的边的数目定义为边的度。B顶点的出度:以顶点v为弧尾的弧的数目；ABECF对有向图来说，顶点的入度:以顶点v为弧头的弧的数目。顶点的度(TD)=出度(OD)+入度(ID)例如:ID(B)=2OD(B)=1TD(B)=3设图G=(V,{VR})中的一个顶点序列{u=vi,0,vi,1,…,vi,m=w}中，(vi,j-1,vi,j)VR1≤j≤m,则称从顶点u到顶点w之间存在一条路径。路径上边的数目称作路径长度。ABECF如:长度为3的路径{A,B,C,F}简单路径:序列中顶点不重复出现的路径。简单回路:序列中第一个顶点和最后一个顶点相同的路径。若图G中任意两个顶点之间都有路径相通，则称此无向图为连通图（如图1）；若无向图为非连通图（如图2），则图中各个极大连通子图称作此图的连通分量。BACDFEBACDFE图G1图G2若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图（如图1）。ABECFABECF对有向图，否则，其各个强连通子图称作它的强连通分量（如图2）。图G1图G2

例:有n个顶点的有向强连通图最多需要多少条边？最少需要多少条边？

答：有n个顶点的有向强连通图最多有n(n-1)条边(构成一个有向完全图的情况)；最少有n条边(n个顶点依次首尾相接构成一个环的情况)。

假设一个连通图有n个顶点和e条边，其中n-1条边和n个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林。BACDFE结构的建立和销毁插入或删除顶点对邻接点的操作对顶点的访问操作遍历插入和删除弧基本操作CreatGraph(&G,V,VR)://按定义(V,VR)构造图DestroyGraph(&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图的存储表示一、图的数组(邻接矩阵)存储表示二、图的邻接表存储表示Aij={0(i,j)VR1(i,j)VR一、图的数组(邻接矩阵)存储表示BACDFE定义:矩阵的元素为易于判定两顶点间是否有边（弧）、易求顶点的度无向图的邻接矩阵为对称矩阵对无权图，用1或0表示相邻否有向图的邻接矩阵为非对称矩阵ABECFV1V3V2V4V1V3V2V4

V1V2V3V4

V1

0010V20001V30001V41000

V1V2V3V4

V1

0111V21001V31000V41100应用：1.结点间是否有关联2.求结点的度在有向图中：顶点出度=行中非零元素的个数。顶点入度=列中非零元素的个数。在无向图中：顶点的度数=矩阵中对应该顶点的行或列中非零元素的个数。特点：无向图的关联矩阵是对称矩阵V1V3V2V4V1V3V2V4

V1V2V3V4

V1

0010V20001V30001V41000

V1V2V3V4

V1

0111V21001V31000V41100入度出度11112101度数3212优点：增减边的操作简单缺点：增减顶点的操作需要搬移大量的元素；稀疏图时浪费存储空间对带权图：求值矩阵应用：需对关联结点间的值进行运算的问题城市交通图typedefintVRType;//

VRType是顶点关系类型typedefstructArcCell{//弧的定义VRTypeadj;//VRType是顶点关系类型。//对无权图，用1或0表示相邻否；//对带权图，则为权值类型。InfoType*info;//该弧相关信息的指针（可无）}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefcharVertexType;//顶点信息（如顶点名称、顶点坐标等，因图而异）typedefstruct{//图的定义VertexTypevexs[MAX_VERTEX_NUM];//顶点向量-AdjMatrixarcs;//邻接矩阵-弧的信息intvexnum,arcnum;//顶点数，弧数GraphKindkind;//图的种类标志}MGraph;0A141B0452C353D254E015F123BACDFE二、图的邻接表存储表示优点:节省存储空间边的插入和删除操作比较简便缺点:结构复杂

具有两种不同的基本组成单元应用：适于结点多，边少advexnextarcinfodatafirstarc表头结点弧结点typedefstructArcNode//弧的结点结构{intadjvex;//该弧的终点位置structArcNode*nextarc;//指向下一条弧的指针

InfoTypeinfo;//该弧的相关信息}ArcNode;typedefstructVnode//邻接表头结点{Vertexdata;//顶点信息

ArcNode*firstarc;//指向第一条弧}VNode;typedefstruct{AdjListadjlist; //邻接表intvexnum,arcnum;//顶点数和边数}ALGraph;

//图的类型VNodeArcNodetypedefVNode

AdjList[MAXV]; //AdjList是邻接表类型AdjList邻接表142301201234ABCDE有向图的邻接表

ABECF可见，在有向图的邻接表中不易找到指向该顶点的弧。ABECD有向图的逆邻接表ABCDE303420

01234在有向图的邻接表中，对每个顶点，链接的是指向该顶点的弧。易于判定任一顶点的邻接点7.3图的遍历

从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。深度优先搜索广度优先搜索

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

均为V的邻接点，SG1、SG2和SG3分别为含顶点W1、W2和W3

的子图。访问顶点V：for(W1、W2、W3)

若该邻接点W未被访问，

则从它出发进行深度优先搜索遍历。w2w3w2深度优先搜索遍历遍历类似于树的先根遍历如何判别V的邻接点是否被访问？为每个顶点设立一个“访问标志visited[w]”。首先将图中每个顶点的访问标志设为FALSE,之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。非连通图的深度优先搜索遍历voidDFSTraverse(GraphG,void(*Visit)(VertexType)){

//初始条件：图G存在，Visit是顶点的应用函数。算法7.4//操作结果：从第1个顶点起，深度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次intv;VisitFunc=Visit;//使用全局变量VisitFunc，使DFS不必设函数指针参数

for(v=0;v<G.vexnum;v++)//对图G的所有顶点visite[v]=FALSE;//访问标志数组初始化(未被访问)

for(v=0;v<G.vexnum;v++)//对图G的所有顶点if(!visite[v])//顶点v尚未被访问

DFS(G,v);

//对尚未访问的序号为v的顶点调用DFSprintf("\n");}voidDFS(GraphG,intv){//从第v个顶点出发递归地深度优先遍历图G。算法7.5（在同一连通（子）图中遍历。）intw;visite[v]=TRUE;//设置访问标志为TRUE(已访问)VisitFunc(GetVex(G,v));//访问第v个顶点for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))//从顶点v的第1个邻接顶点w开始if(!visite[w])DFS(G,w);

//对v的尚未访问的序号为w的邻接顶点递归调用DFS(访问w)}连通图的深度优先搜索遍历abchdk

e

fgFFFFFFFFFTTTTTTTTTachdefk

bgachefk

dbg访问标志:访问次序:例如:012345678F=0T=1visite[v]=TRUE;VisitFunc(GetVex(G,v));for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))if(!visite[w])DFS(G,w);二、广度优先搜索遍历图Vw1w8w3w7w6w2w5w4对连通图，从起始点V到其余各顶点必定存在路径。其中，V->w1,V->w2,V->w8

的路径长度为1；V->w7,V->w3,V->w5

的路径长度为2；V->w6,V->w4

的路径长度为3。w1Vw2w7w6w3w8w5w4从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。00000visited[]初始态

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

);//访问vEnQueue(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}

//

}//BFSTraverse7.4.1最小生成树7.4图的应用7.4.2最短路径7.4.3拓扑排序7.4.4关键路径7.4.1(连通网的)最小生成树

假设要在n个城市之间建立通讯联络网，则连通n个城市只需要修建n-1条线路，如何在最节省经费的前提下建立这个通讯网？问题：构造网的一棵最小生成树(MST)

，即：在e条带权的边中选取n-1条边（不构成回路），使“权值之和”为最小。算法二：（克鲁斯卡尔算法）该问题等价于：算法一：（普里姆算法）构造网的一棵最小生成树(MST)

在生成树的构造过程中，图中n个顶点分属两个集合：已落在生成树上的顶点集U

和尚未落在生成树上的顶点集V-U，则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。UV-U最小生成树有如下重要性质：设N=(V,{E})是一连通网，U是顶点集V的一个非空子集。若（u,v）是一条具有最小权值的边，其中u∈U，v∈V-U，则存在一棵包含边（u,v）的最小生成树。uvabcdegf例如:195141827168213ae12dcbgf7148531621所得生成树权值和=14+8+3+5+16+21=67

取图中任意一个顶点v作为生成树的根，之后往生成树上添加新的顶点w。在添加的顶点w和已经在生成树上的顶点v之间必定存在一条边，并且该边的权值在所有连通顶点v和w之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有n-1个顶点为止。普里姆算法思想abcdegf195141827168213ae12dcb7aaa19141814例如:e12ee8168d3dd7213c55for(j=0;j<G.vexnum;++j)//辅助数组初始化

if(j!=k)

{

closedge[j]={u,G.arcs[k][j].adj};k=minimum(closedge);//求出加入生成树的下一个顶点(k)

printf(closedge[k].adjvex,G.vexs[k]);//输出生成树上一条边closedge[k].lowcost=0;//第k顶点并入U集lowcost[k].lowcost=0;/ /标记k已经加入U

for(j=0;j<G.vexnum;++j)//修改其它顶点的最小边

if(G.arcs[k][j].adj<closedge[j].lowcost)closedge[j]={G.vexs[k],G.arcs[k][j].adj};0设置一个辅助数组closedge[]，对当前V－U集中的每个顶点，记录和顶点集U中顶点相连接的代价最小的边：voidMiniSpanTree_P(MGraphG,VertexType

u){//用普里姆算法从顶点u出发构造网G的最小生成树k=LocateVex(G,u);//顶点u的序号

for(j=0;j<G.vexnum;++j)//辅助数组初始化

if(j!=k)

{closedge[j].adjvex=k;//顶点u的序号赋给closedge[j].adjvex

closedge[j].lowcost=G.arcs[k][j].adj;//顶点u到顶点j的权值

}//书中closedge[j]={u,G.arcs[k][j].adj};

closedge[k].lowcost=0;//初始，U＝{u}

for(i=0;i<G.vexnum;++i){//

选择其余G.vexnum-1个顶点k=minimum(closedge);//求出加入生成树的下一个顶点(k)

printf(closedge[k].adjvex,G.vexs[k]);//输出生成树上一条边closedge[k].lowcost=0;//第k顶点并入U集for(j=0;j<G.vexnum;++j)//修改其它顶点的最小边

if(G.arcs[k][j].adj<closedge[j].lowcost)closedge[j]={G.vexs[k],G.arcs[k][j].adj};}}具体做法:先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为止。考虑问题的出发点:为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。克鲁斯卡尔算法的基本思想：abcdegf195141827168213ae12dcbgf7148531621例如:7121819普里姆算法克鲁斯卡尔算法时间复杂度O(n2)O(eloge)稠密图稀疏图算法名适应范围比较两种算法7.4.2最短路径求从某个源点到其余各点的最短路径

每一对顶点之间的最短路径

求从源点到其余各点的最短路径的算法的基本思想:依最短路径的长度递增的次序求得各条路径源点v1…其中，从源点到顶点v的最短路径是所有最短路径中长度最短者。v2采用狄克斯特拉(Dijkstra)算法求解基本思想是：设G=(V,E)是一个带权有向图,把图中顶点集合V分成两组：第一组为已求出最短路径的顶点集合(用S表示,初始时S中只有一个源点,以后每求得一条最短路径v,…vk,就将vk加入到集合S中,直到全部顶点都加入到S中,算法就结束了)第二组为其余未确定最短路径的顶点集合(用U表示)。它或者是直接从源点到该点(只含一条弧)；或者是从源点经过已求得最短路径的顶点，再到达该顶点。路径长度最短的最短路径的特点：求最短路径的迪杰斯特拉算法：。设置辅助数组:一维数组Dist[i]：纪录从源点v0到顶点vi的当前最短路径。一维数组path[i]：纪录从源点v0到终点vi的当前最短路径上vi的直接前驱顶点序号。一维数组S[i]：纪录从源点v0到终点vi是否已被确定最短路径长度.S U dist[]path[]01234560123456{0} {1,2,3,4,5,6}{0,4,6,6,∞,∞,∞}{0,0,0,0,-1,-1,-1}{0,1}{2,3,4,5,6}{0,4,5,6,11,∞,∞}{0,0,1,0,1,-1,-1}{0,1,2}{3,4,5,6} {0,4,5,6,11,9,∞}{0,0,1,0,1,2,-1}{0,1,2,3}{4,5,6} {0,4,5,6,11,9,∞}{0,0,1,0,1,2,-1}{0,1,2,3,5}{4,6} {0,4,5,6,10,9,17}{0,0,1,0,5,2,5}{0,1,2,3,5,4} {6} {0,4,5,6,10,9,16}{0,0,1,0,5,2,4}{0,1,2,3,5,4,6}{} {0,4,5,6,10,9,16}{0,0,1,0,5,2,4}寻找序号为v的顶点到所有其它顶点的最短路径(1)初始时,S只包含源点,即S={v},v的距离为0。U包含除v外的其他顶点,U中顶点u距离为边上的权(若v与u有边<v,u>)或∞(若u不是v的出边邻接点)。(2)从U中选取一个距离v最小的顶点k,把k加入S中(该选定的距离就是v到k的最短路径长度)。(3)以k为新考虑的中间点,修改U中各顶点的距离：若从源点v到顶点u(u∈U)的距离(经过顶点k)比原来距离(不经过顶点k)短,则修改顶点u的距离值,修改后的距离值的顶点k的距离加上边<k,u>上的权。

for(i=0;i<g.n;i++){dist[i]=g.arcs[v][i];/*距离初始化*/s[i]=0;/*s[]置空*/if(g.arcs[v][i]<INF) /*路径初始化*/path[i]=v;elsepath[i]=-1;}s[v]=1;path[v]=0; /*源点编号v放入s中*/mindis=INF;k=-1;for(j=0;j<g.n;j++)//选取不在s中且具有最小距离的顶点kif(s[j]==0&&dist[j]<mindis){k=j;mindis=dist[j]; }s[k]=1; //顶点k加入s中for(u=0;u<g.n;u++)//修改不在s中的顶点的距离if(s[u]==0)if(g.arcs[k][u]<INF&&

dist[k]+g.arcs[k][u]<dist[u]){dist[u]=dist[k]+g.arcs[k][u];path[u]=k;}

voidDijkstra(MGraphg,intv)(4)重复步骤(2)和(3)直到所有顶点都包含在S中。7.4.3拓扑排序

问题:

假设以有向图表示一个工程的施工图或程序的数据流图，则图中不允许出现回路。

检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序。例子：计算机专业的学生必须完成一系列规定的基础课和专业课才能毕业，这时工程就是完成给定的学习计划，而活动就是学习课程，这些课程的名称与代号如表所示在AOV网中，用顶点表示课程，有向边表示课程之间的优先关系，如果课程Ci是课程Cj的先修课，则在AOV网中必定存在一条有向边<Ci,Cj>。表中各课程的AOV网如下图所示AOV网：如果用图中的顶点表示活动，边表示活动间的先后关系，则这样的有向图称为顶点活动网(ActivityOnVertexnetwork，简称AOV网)AOV网何谓“拓扑排序”？对有向图进行如下操作：

按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。例如：对于下列有向图BDAC可求得拓扑有序序列：

ABCD

或

ACBD由此所得顶点的线性序列称之为拓扑有序序列拓扑有序序列不是唯一的。BDAC反之，对于下列有向图不能求得它的拓扑有序序列。因为图中存在一个回路{B,C,D}任何无回路的AOV网，其顶点都可以排成一个拓扑序列，方法如下：从AOV网中选择一个入度为0的顶点将其输出。在AOV网中删除此顶点及其所有的出边。反复执行以上两步，直到所有顶点都已经输出为止，此时整个拓扑排序完成；或者直到剩下的顶点的入度都不为0为止，此时说明AOV网中存在回路，拓扑排序无法再进行。拓扑排序思想：abcghdfeabhcdgfe在算法中需要用定量的描述替代定性的概念

没有前驱的顶点

入度为零的顶点删除顶点及以它为尾的弧

弧头顶点的入度减1拓扑排序算法：

设置：设AOV网采用邻接表表示，边表为出边表。算法中定义一个indegree（1：n)数组，存放各顶点的入度。设置一个链栈S（1：n)存储入度为0的顶点。

算法：

1.拓扑排序前，先得到所有结点的入度，然后将所有入度为0的顶点压栈。 2.从栈顶取出一个顶点将其输出，由它的出边表可以得到以该顶点为起点的出边，将这些边终点的入度减1，即删除这些边。如果某条边终点的入度为0，则将该顶点入栈。 3.反复进行上述2操作，直到栈为空，如果这时输出的顶点个数小于n，则说明该AOV网中存在回路，否则，拓扑排序正常结束。 4.算法结束后。

C0C1C22257∧36∧C3C4C5C6∧∧C78∧4∧3∧5∧00221221C86∧1拓扑序列为∶C1,C4,C0,C7,C8,C2,C3,C6,C51.拓扑排序前，先得到所有结点的入度，然后将所有入度为0的顶点压栈。2.从栈顶取出一个顶点将其输出，同时将该顶点的所有后继顶点的入度减1。若后继顶点的入度为0，则将该顶点入栈。3.反复进行上述2操作，直到栈为空。如果这时输出的顶点个数小于n，则说明该AOV网中存在回路，否则，拓扑排序正常结束。

voidFindInDegree(ALGraphG,intindegree[])

{//求顶点的入度inti;ArcNode*p;for(i=0;i<G.vexnum;i++)//对于所有顶点indegree[i]=0;//给顶点的入度赋初值0for(i=0;i<G.vexnum;i++)//对于所有顶点

{p=G.vertices[i].firstarc;//p指向顶点的邻接表的头指针while(p)

//p不空

{indegree[p->data.adjvex]++;//将p所指邻接顶点的入度+1p=p->nextarc;//p指向下一个邻接顶点}}}indegree[MAX_VERTEX_NUM-1];入度数组，存放各顶点当前入度数count=0;//对输出顶点计数while(!EmptyStack(S)){

Pop(S,v);++count;printf(v);

for(w=FirstAdj(v);w;w=NextAdj(G,v,w)){

--indegree(w);//弧头顶点的入度减一

if(!indegree[w])Push(S,w);

//新产生的入度为零的顶点入栈

}}if(count<G.vexnum){printf("此有向图有回路\n");returnERROR;}else{printf("为一个拓扑序列。\n");returnOK;}}FindInDegree(G,indegree);//对各顶点求入度InitStack(S);for(i=0;i<G.vexnum;++i)

if(!indegree[i])Push(S,i);

//入度为零的顶点入栈StatusTopologicalSort(ALGraphG){

//有向图G采用邻接表存储结构。若G无回路，则输出G的顶点的一个拓扑序列并返回OK；否则返回ERROR。7.4.4关键路径问题:

假设以有向网表示一个施工流图，弧上的权值表示完成该项子工程所需时间。问：哪些子工程项是“关键工程”？即：哪些子工程项将影响整个工程的完成期限的。AOE-网：在带权的有向图中，用顶点表示事件，用弧表示活动，权表示活动持续的时间，这样组成的网称为以边表示活动的网。abcdefghk64521187244例如:“关键活动”指的是：该弧上的权值增加

将使有向图上的最长路径的长度增加。(关键路径上的活动)整个工程完成的时间为：从有向图的源点到汇点的最长路径(关键路径)。源点汇点6174注意:在一个AOE网中,可以有不止一条的关键路径。

如何求关键活动？