第七章图无答案课件

第七章图图的定义和术语图的存储结构图的基本操作--遍历应用—最小生成树拓扑排序关键路径最短路第七章图图的定义和术语7.1图的定义和术语线性表、树和图：从关系、结构两个角度区分

ABE

CD

BCADFE图Graph;顶点Vertex;序偶<A,B>;弧Arc;弧头B/弧尾ADigraph;Undigraph;无序对(A,B):<A,B>∧<B,A>;Edge网NetWork:弧或边含权的图,分有向网DN、无向网UDN(无向)完全图:边数最大的无向简单图,满足e=n*(n-1)/2有向完全图:弧数最大的有向简单图,e=n*(n-1)稀疏图(如e<nlogn)稠密图ABEC1图的定义和术语线性表、树和图：从关系、结构两个角度区分BECBBC子图Subgraph

邻接点:无向图如A与B互为邻接点,有向图如A邻接到B无向图顶点的度,如TD(A)=2；有向图分入/出度,度为两者之和

ID(A)=1,OD(A)=2,TD(A)=3路径、简单路径、回路(环)、路径长度术语

BCADFEABECFBECBBC子图Subgraph邻接点:无向图如A与若无向图G中任意两个顶点之间都有路径相通，则称此图为连通图。如能找到一条含全部顶点的路径则说明是连通图无向图中的极大连通子图称作此图的连通分量。极大指顶点尽量多,顶点连同其关联的边构成连通分量.图本身连通则连通分量唯一,是自身BACDFEBACDFE连通图,连通分量

(无向图)若无向图G中任意两个顶点之间都有路径相通，则称此图为连通图。若任意两顶点间都存在一条有向路径，则称此有向图为强连通图。ABECFABECF有向图的极大强连通子图称作它的强连通分量。强连通图、强连通分量(有向图)若任意两顶点间都存在一条有向路径，则称此有向图为强连通图。A连通图的一个含有全部顶点的子图,如果连通且极小，则它必是一颗树(边数为n-1)，称该树为原连通图的生成树。破圈法可得生成树对非连通图，由各个连通分量的生成树组成的集合称为此非连通图的生成森林。BACDFE生成树与生成森林（无向图）注:树是含边数最小的连通图(n-1);图中若边少于n-1则必不连通；若图连通则至少含n-1条边；若图中多于n-1条边则必然含有回路。含n-1条边的连通图必然是树连通图的一个含有全部顶点的子图,如果连通且极小，则它必是一颗ADTGraph{

数据对象V：若干顶点组成的集合

数据关系R：R={VR}

VR＝{<v,w>|v,w∈V且<v,w>表示从v到w有一条弧，可代表v认识w或v到w有路等)}

基本操作>>}图的抽象数据类型定义—逻辑结构ADTGraph{图的抽象数据类型定义—逻辑结构CreatGraph(&G,V,VR);//按定义(V,VR)构造图GDestroyGraph(&G);//销毁图G结构的建立和销毁CreatGraph(&G,V,VR);DestroyG插入或删除顶点、弧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>插入或删除顶点、弧InsertVex(&G,v);//在遍历DFSTraverse(G,v,Visit());

//从顶点v起深度优先遍历图G,对每个顶点执行一次VisitBFSTraverse(G,v,Visit());

//从v起广度优先遍历图G，每个顶点调用一次函数Visit规则:访问起始顶点v,然后选取与v邻接的未访问的第一个顶点w,访问之，再选取与w邻接的未访问的第一个顶点，访问之。重复进行至当前节点的所有邻接点都被访问过，此时后退到最近访问过的定点，找其下一个未访问的邻接点访问，依次类推。如ABEFCDH说明:一次可遍历所有与v连通的顶点。若尚有顶点未访问(非连通图),则从其开始重复上述过程.对应树的先根遍历。可得深度优先生成树或森林以及连通分量递归描述：访问v,逐个从v未访问的邻接点出发递归遍历.规则:访问v,访问v的全部未访问的邻接点,再逐个从这些邻接点出发重复.一次可遍历所有与v连通的顶点,若尚有顶点未访问则从其开始重复开始上述过程.如ABEHFCD对应树层序遍历,可得广度优先生成树/森林,可得连通分量,实现?

BCADFEH遍历DFSTraverse(G,v,Visit());对顶点的访问操作LocateVex(G,u);

//若G中存在顶点与u”相等”，则返回该顶点在图中“位置”(下标或指针)GetVex(G,v);

//返回G中顶点v的值。PutVex(&G,v,value);//为G中顶点v赋值value。对顶点的访问操作LocateVex(G,u);GetV对邻接点的操作FirstAdjVex(G,v);

//返回G中顶点v的“第一个邻接点”。若该顶点//在G中没有邻接点，则返回“空”。NextAdjVex(G,v,w);

//w是v的一个邻接点,返回v的“下一个邻接点”。//若w是v的最后一个邻接点，则返回“-1”。对邻接点的操作FirstAdjVex(G,v);Next图的数组表示(p161)(邻接矩阵)图的邻接表表示(p163)有向图的十字链表表示(p164)

无向图的邻接多重表表示(p166)7.2图的存储结构图的数组表示(p161)(邻接矩阵)图的邻接表表示(p163BACDFE邻接矩阵:行、列各对应一个顶点,若第i行对应的顶点到第j列对应的顶点有弧相连则A[i][j]=1,否则为0。n*n阶

ABCDEF

ABCDEF1、图的数组表示--邻接矩阵adjacencymatrixBACDFE邻接矩阵:行、列各对应一个顶点,若第i行对应的顶邻接矩阵举例ABECD无向图的邻接矩阵必为对称阵网的邻接矩阵A[i][j]=wij或∞邻接矩阵举例ABECD无向图的邻接矩阵必为对称阵

ABCDEFABCDEF//----图的数组(邻接矩阵)存储表示----typedefcharVertexType;#defineINFINITY10000//最大值∞

#defineMAX_VERTEX_NUM20//最大顶点个数typedefenum{DG,DN,UDG,UDN}GraphKind;//图类型typedefstructArcCell{//弧的定义

VRTypeadj;//邻接数,0/1或w/∞。VRType为int/double…

InfoType*info;//弧的附加信息数组}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{//图的定义

VertexTypevexs[MAX_VERTEX_NUM];//顶点信息

AdjMatrixarcs;//邻接矩阵,存储弧信息,静态数组

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

GraphKindkind;//图的类型标记}MGraph;//矩阵图ABCDEStatusCreateGraph(Mgraph&G){//输入图的种类及顶点和边信息构造图G(邻接矩阵表示)scanf(“%d”,&G.kind);//枚举值DG,DN…实输入01…switch(G.kind){caseDG:returnCreateDG(G);caseDN:returnCreateDN(G);caseUDG:returnCreateUDG(G);caseUDN:returnCreateUDN(G);default:returnERROR;}图的创建StatusCreateGraph(Mgraph&G)StatusCreateUDN(Mgraph&G){//建立无向网G

输入G.vexnum,G.arcnum,IncInfo;//IncInfo为0表各弧无附加信息

for(i=0;i<G.vexnum;++i)scanf(“%c”,G.vexs[i]);for(i=0;i<G.vexnum;++i)for(j=0;j<G->vexnum;++j)G.arcs[i][j]={INFNITY,NULL};//各弧初始化

for(k=0;k<G.arcnum;++k){scanf(“%c%c%lf”,&v1,&v2,&w);//输入一条“边”及其权值

i=LocateVex(G,v1);j=LocateVex(G,v2);//确定顶点下标

G.arcs[i][j].adj=w;if(IncInfo)输入G.arcs[i][j].info;

G.arcs[j][i]=G.arcs[i][j];//无向网需将对称弧加入

}}//ENDABECF1597211132StatusCreateUDN(Mgraph&G){/BACDFE

ABCDEF邻接矩阵优缺点：易于求顶点度(区分有/无向图)、求邻接点，易判断两点间是否有弧或边相连,但不利于稀疏图的存储，因弧不存在时也要存储相应信息，且要预先分配足够大空间BACDFEA邻接矩阵优缺点：易于求顶点度(区分有/无小结：掌握图的概念和基本术语掌握图的邻接矩阵存储，理解优缺点掌握图的深度优先遍历和广度优先遍历的规则会通过遍历求图的连通分量和深度优先、广度优先生成树、生成森林作业：15

BCADFEH小结：掌握图的概念和基本术语B

ABCDEFABCDEF//----图的数组(邻接矩阵)存储表示----typedefcharVertexType;#defineINFINITY10000//最大值∞

#defineMAX_VERTEX_NUM20//最大顶点个数typedefenum{DG,DN,UDG,UDN}GraphKind;//图类型typedefstructArcCell{//弧的定义

VRTypeadj;//邻接数,0/1或w/∞。VRType为int/double…

InfoType*info;//弧的附加信息数组}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{//图的定义

VertexTypevexs[MAX_VERTEX_NUM];//顶点信息

AdjMatrixarcs;//邻接矩阵,存储弧信息,静态数组

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

GraphKindkind;//图的类型标记}MGraph;//矩阵图ABCDE0A141B0452C353D254E01F123……BACDFE顶点数组(头结点)

邻接点链表无向图中每条边出现两次,n个顶点e条边需n个头结点和2e个表结点2、邻接表存储表示0A14BACDFE邻接点142301201234

ABCDE邻接表举例

ABECDtypedefstructArcNode{intadjvex;

structArcNode*nextarc;

InfoType*info;}ArcNode;datafirstarcadjvexnextarcinfotypedefstructVNode{VertexTypedata;

ArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{

AdjListvertices;

intvexnum,arcnum;GraphKindkind;}

ALGraph;//邻接表图142301201StatusCreateGraph(ALGraph&G){//建立图的邻接表的结构

scanf(“%d”,&G.kind);switch(G.kind){caseDG:returnCreateDG(G);caseDN:returnCreateDN(G);caseUDG:returnCreateUDG(G);caseUDN:returnCreateUDN(G);default:returnERROR;}邻接表图的创建【补充】StatusCreateGraph(ALGraph&G)StatusCreateDN(ALGraph&G){//建立有向网

scanf(“%d%d%d”,&G.vexnum,&G.arcnum,&IncInfo);for(i=0;i<G.vexnum;++i){scanf(G.vertices[i].data);G.vertices[i].firstarc=NULL;}for(k=0;k<G.arcnum;k++){arc=(ArcNode*)malloc(sizeof(ArcNode));scanf(“%c%c%f”,&v1,&v2,&w);i=LocateVex(G,v1);j=LocateVex(G,v2);

arc->adjvex=j;if(IncInf)输入(arcn->info);

arc->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=arcn;//邻接点与输入逆序排列P164,正序?}//邻接点顺序依赖输入顺序和创建程序，“不给”默认正序

ReturnOK；

}//思考无向网的创建有何不同？StatusCreateDN(ALGraph&G){/142301201234

ABCDE邻接表说明：

ABECD稀疏图用邻接表存储相对节省空间对有向图易求顶点出度与邻接点,但求入度难.若只求入度可引入逆邻接表,也可结合邻接表与逆邻接表引入十字链表对无向图易求度,但边出现两次,为方便边操作可借助多重链表ABCDE303420

012341423012013、“有向图”的十字链表存储表示【选】

ABDCE010A1B2C3D4E…….tailvheadvhlinktlinkinfodatafirstinfirstout03^^VexNode:ArcBox:12^24^^32^^40^41^^具体邻接点顺序依赖输入顺序和图的创建程序，如逆序3、“有向图”的十字链表存储表示【选】ABDCE010A13、“有向图”的十字链表存储表示【选】

typedefstructArcBox{inttailvex,headvex;InfoType*info;structArcBox*hlink,*tlink;//指向同弧头/尾的下一弧

}ArcBox;typedefstructVexNode{//顶点的结构表示

VertexTypedata;ArcBox*firstin,*firstout;}VexNode;typedefstruct{VexNodexlist[MAX_VERTEX_NUM];

intvexnum,arcnum;}OLGraph;3、“有向图”的十字链表存储表示【选】typedefstStatusCreateDG(OLGraphG){scanf(&G.vexnum,&G.arcnum,&IncInf);for(i=0;i<G.vexnum;++i){

scanf(&G.xlist[i].data);G.xlist[i].firstin=NULL;G.xlist[i].firstout=NULL;}for(k=0;k<G.arcnum;++k){scanf(&v1,&v2);i=LocateVex(G,v1);j=LocateVex(G,v2);//直接输下标可略

p=(ArcBox*)malloc(sizeof(ArcBox));*p={i,j,G.xlist[j].firstin,G.xlist[i].firstout,NULL};//逆序

G.xlist[j].firstin=G.xlist[i].firstout=p;//邻接点顺序与例图反

if(IncInf)input(p->info);}}//ENDStatusCreateDG(OLGraphG){4、“无向图”的邻接多重表存储表示【选】无向图的邻接表存储中，一条边出现两次，分别在两个顶点对应的链表中，对边的操作复杂。为此，将每条边(Vi,Vj)只用一个如下结点表示:顶点表示为：markivexilinkjvexjlinkinfodatafirstedge0123

ABCDABDC01^0^31^2^2^3^e1e2e3

e4将边看作有向的，如A->B4、“无向图”的邻接多重表存储表示【选】无向图的邻接表存储中typedefstructEbox{VisitIfmark;//访问标记

intivex,jvex;//该边依附的两个顶点的位置

structEBox*ilink,*jlink;//指向对应顶点为i,j的下一边

InfoType*info;}EBox;4、“无向图”的邻接多重表存储表示【选】typedefstruct{VexBoxadjmulist[MAX_VERTEX_NUM];

intvexnum,edgenum;

}AMLGraph;//邻接多重表typedefstructVexBox{VertexTypedata;EBox*firstedge;//指向第一条依附该顶点的边}VexBox;typedefstructEbox{4、“无向图”的邻7.3图的遍历—深度优先遍历规则:访问v,逐个从v未访问的邻接点出发递归遍历，如此可遍历所有与v连通的顶点.若尚有顶点未访问(不连通),则从其开始重复上述过程.如ABEFCDH.voidDFS(G，v){VisitFunc(v);visited[v]=TRUE;

for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))

if（!visited[w]）DFS(G，w)；}voidDFSTraverse(GraphG,Status(*Visit)(intv)){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);}//visited数组和VisitFunc函数为全局每个顶点调用一次DFS,DFS主要操作是查找邻接点,当用邻接矩阵存储时查找某顶点的邻接点复杂度为O(n),总复杂度O(n2);当邻接表存储时查找邻接点总复杂度为O(e),总复杂度为O(n+e)DFSTraverse每调用一次DFS所访问的顶点连通这些顶点关联的边构成一个连通分量.只保留走过的边得生成树或生成森林

BCADFEH7.3图的遍历—深度优先遍历规则:访问v,逐个从v未访问的邻abchdekfgachkfedbgabcdefghk2345607070807812385547注意邻接点的顺序作题时若未给出则默认为正序,实际上应依赖创建程序和输入顺序。若给出存储结构则以所给为准。如上例既非正序也非逆序,如h、k顶点对应的链表，画生成树时注意求图的连通分量、深度优先生成树或生成森林P171DFSTraverse每调用一次DFS所访问的顶点连同这些顶点关联的边构成一个连通分量.只保留走过的边得生成树或生成森林abchdekfgachkfedbgabcdefghk2347.3图的遍历—广度优先遍历BFSTraverse(G,v,Visit());

规则:访问v,访问v的各未访问的邻接点,之后逐个从这些邻接点出发重复上述操作。待与v连通的顶点访问毕再从另一顶点出发.如ABEHFCD实现：对各个顶点v：{若其尚未访问则访问v,之后v入队。【队顶元素出队，逐个访问其尚未访问的邻接点，没访问完一个便入队】。重复【】中内容到队空｝

BCADFEH7.3图的遍历—广度优先遍历BFSTraverse(G,voidBFSTraverse(GraphG,Status(*Visit)(intv)){for(v=0;v<G.vexnum;++v)visited[v]=FALSE;InitQueue(Q);for(v=0;v<G.vexnum;++v)if(!visited[v]){

}}Visit(v);visited[v]=TRUE;EnQueue(Q,v);while(!QueueEmpty(Q)){DeQueue(Q,v);for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))if(!visited[w]){//注意NextAdjVex返回值约定

Visit(w);visited[w]=TRUE;EnQueue(Q,w);}}对各个顶点v：{若其尚未访问则访问v,之后v入队。【队顶元素出队，逐个访问其尚未访问的邻接点，每访问完一个便入队】。重复【】中内容到队空｝每个顶点进一次队,出队时主要操作是查找邻接点,当用邻接矩阵存储时查找某顶点的各邻接点复杂度的为O(n),总复杂度O(n2);当用邻接表存储时查找邻接点复杂度为O(e),总复杂度为O(n+e)voidBFSTraverse(GraphG,Stat7.4.3最小生成树P173假设要在n个城市之间建立通讯联络网，不同城市间建立通讯设施的代价不同，如何在最节省经费的前提下建立这个通讯网？即找权值之和最小的极小连通子网，问题转换为在连通网中找一颗生成树，最小生成树abcdegf195141827168213ae12dcbgf71485316217.4.3最小生成树P173假设要在n个城市之间建立通Kuaskal算法直接找权值最小的边,若并入后构成回路则舍弃Kruskal算法求最小生成树：设N=(V,{E})是连通网,求最小生成树令T=(V,{}),各顶点自成一连通分量在E中找代价最小的边,若该边的顶点落在不同连通分量上，则将其并入,依次类推至所有顶点到一个连通分量上总O(eloge)，与n无关，适合稀疏图abcdegf195141827168213ae12dcbgf71485316217121819Prim算法是逐个顶点并入，再据顶点找最小边；Kuaskal算法直接找权值最小的边,若并入后构成回路则舍弃普里姆Prim算法求最小生成树：abcdegf195141827168213ae12dcb7aaa1914180e12ee8160d3dd7210c50e0gd0f0设U代表已并入最小生成树中的顶点的集合，最初任选一点放入U。之后找U到U最小边，将对应新顶点并入，共N-1轮即可从顶点u0开始,令U={u0},初始化u0到其余各顶点距离{找最小的边输出,并入新顶点,赋0+更新表使U到非U距离更小}。如上重复n-1次普里姆Prim算法求最小生成树：abcdegf1951418构造下表对应的数组,每个元素对应一个顶点,元素取值是当前轮从U到该点最小边的信息(出发点下标和代价),顶点被并入U后代价置0struct{VertexTypeadjvex;//出发点名称

VRTypelowcost;//代价}closedge[MAX_VERTEX_NUM];aaa1914180e12ee8160d3dd7210c50e0d0构造下表对应的数组,每个元素对应一个顶点,元素取值是当前轮从voidMiniSpanTree_Prim(MGraphG,VertexTypeu){//用普里姆算法从u出发求网G(邻接矩阵表示)最小生成树,输出各边

k=LocateVex(G,u);closedge[k].lowcost=0;//将u并入U,赋0for(j=0;j<G.vexnum;++j)//据u更新数组元素代价

if(j!=k)closedge[j]={u,G.arcs[k][j].adj};for(i=1;i<G.vexnum;++i){//共n-1轮,每轮找最小边输出,赋0更新

k=minimum(closedge);//代价非零的元素中找最小元素,返下标

printf(“%c%c”,closedge[k].adjvex,G.vexs[k]);//输出边u->kclosedge[k].lowcost=0;//将k号结点并入U，赋0for(j=0;j<G.vexnum;++j)//据k号结点更新数组元素代价

if(G.arcs[k][j]).adj<closedge[j].lowcostclosedge[j]={G.vexs[k],G.arcs[k][j].adj};}}将初始点u并入U,初始化表;{之后找小边并入,赋0+更新}重复复杂度为O(n2),与边数无关，适合稠密图voidMiniSpanTree_Prim(MGraph7.5.1拓扑排序AOV-网:顶点表示活动,弧表示活动间先后(依赖)关系的有向图.AOV-网用以表示工程或系统的施工计划，可据此判断工程是否可以顺利进行AOV-网中应存在一个覆盖全部顶点的序列(全序),在该序列中顶点出现的顺序满足网中的先后关系(偏序)。一个全序就对应一个合法的完整工序BDACBDAC7.5.1拓扑排序AOV-网:顶点表示活动,弧表示活动间先由某个集合上的一个偏序得到该集合上的一个全序,该操作称为拓扑排序。若得到一个含全部顶点的拓扑有序序列(全序)则说明工程可顺利开展,不存在则说明图中存在有向回路,不合理何谓拓扑排序BDACABCD或ACBD均是含全部顶点的拓扑有序序列(DAG图)BDAC不存在含全部顶点的拓扑有序序列,存在有向回路BCDB由某个集合上的一个偏序得到该集合上的一个全序,该操作称为拓扑从有向图中选取一没有前驱的顶点并输出之；重复上述两步，至图空(得一全序)或图不空但不存在无前驱的顶点(得一有向环)。从图中“删除”此顶点及所有从其出发的弧如何进行拓扑排序abcghdfeabchdgfeBDACA入度0顶点入栈,{出栈并据此更新入度,零入度者入栈}重复至栈空从有向图中选取一没有前驱的顶点并输出之；重复上述两步，至图空3、拓扑排序算法的实现将入度为0的顶点入栈,出栈并据此更新入度,如此重复StatusTopologicalSort(ALGraphG){//G用邻接表存储,若G无回路则输出拓扑有序序列,返OK,否则返ERROR.

FindInDegree(G,indegree);//求各顶点入度存入数组indegreeInitStack(S);for(i=0;i<G.vexnum;++i)if(!indegree[i])Push(s,i);count=0;//用以对输出的顶点进行计数

while(!StackEmpty(S)){

Pop(S,i);printf(G.vertices[i].data);++count;}if(count<G.vexnum)returnERROR;elsereturnOK;}

for(p=G.vertices[i].firstarc;p!=NULL;p=p->nextarc){k=p->adjvex;

--indegree[k];//更新入度

if(!indegree[k])Push(S,w);//新的入度为零的顶点入栈

}最初求入度O(e);第一波顶点入栈O(n)；若为DAG图则每个顶点入栈、出栈各一次,O(n);入度减1的操作执行e次,故总复杂的度O(n+e)3、拓扑排序算法的实现将入度为0的顶点入栈,出栈并据此更新入作业：7.7prim算法注意画表，多张Kruscal算法，手工执行，直接给答案abcdegf195141827168213ae12dcbgf71485316217121819作业：7.7abcdegf195141827168213ae作业：9对下图执行教材中的拓扑排序算法，写出得到的拓扑有序序列abcghdfeabcdegf195141827168213ae12dcbgf7148531621作业：9对下图执行教材中的拓扑排序算法，写出得到的拓扑有序7.5.2关键路径AOE网：顶点表示状态，弧表示活动，弧权表示完成活动所需时间。用以估算工程的完成时间问:最短工期多长？哪些活动是影响工期的“关键活动”abcdefghk64521187244源点汇点174关键路径(长度最长的路径)决定工期关键活动:工程正常开展最早开始时间等于最迟开始时间的活动ee(act)=ve(头)与el(act)=vl(尾)-dur(act)7.5.2关键路径AOE网：顶点表示状态，弧表示活动，弧权ve(源点)=0.对普通顶点v,设W为其前驱顶点集则 ve(v)=max{ve(w)+dut(w,v)|w∈W}如何保证求ve(v)时ve(w)已经求出？关键活动求取—求各点最早到达时间ve(x)abcdefghk64521187244实现:{各顶点ve初始化为0,找无前驱顶点,据其ve值更新后继ve值,“删除”}如此重复,至图空或发现回路.实际是按拓扑序ve(源点)=0.关键活动求取—求各点最早到达时间ve(x)StatusTopologicalOrder(ALGraphG，Stack&T){//求个顶点最早到达时间计入全局数组ve,T按访问顺序存储各顶点,求vl用

ve[0..G.vexnum-1]=0;

FindInDegree(G,indegree);InitStack(S);InitStackT;for(i=0;i<G.vexnum;++i)if(!indegree[i])Push(s,i);count=0;//对输出的顶点进行计数

while(!StackEmpty(S)){//出栈S、入栈T、”删除”、更新

Pop(S,j);Push(T,j);++count;

for(p=G.vertices[j].firstarc;p;p=p->nextarc){k=p->adjvex;--indegree(k);if(indegree[k]==0)Push(S,w);

if(ve[j]+*(p->info)>ve[k])ve[k]=ve[j]+*(p->info)

}}if(count<G.vexnum)returnERROR;elsereturnOK;}{各点ve初始化为零,无前驱顶点入栈,出栈并据其更新后继ve,“删除”}重复StatusTopologicalOrder(ALGrap00000000064571157151418abcdefghk64521187244{找无前驱顶点,据其ve值更新后继ve,“删除”}重复用栈实现的拓扑排序序列为:a-d-f-c-b-e-h-g-k00000000064571157151418abcdefg关键活动求取—求最晚到达时间vl(x)vl(汇点)=ve(汇点)普通顶点v,设W为其后继顶点集合，则 vl(v)=min{vl(w)-dut(v,w)|w∈W}如何保证求vl(v)时vl(w)已求出？abcdefghk64521187244174各顶点vl初始化成工期，按拓扑逆序(T的出栈顺序)逐个更新该元素的vl关键活动求取—求最晚到达时间vl(x)vl(汇点)=ve(汇关键活动:调用函数求Ve,按拓扑逆序求Vl,求ee/el并输出StatusCriticalPath(ALGraphG){//求个顶点最晚到达时间计入全局数组vl,同时输出各活动的最早、迟时间等信息InitStack(T);if(!TopologicalOrder(G,T))returnERROR;

vl[0..G.vexnum-1]=ve[G.vexnum-1];while(!StackEmpty(T)){

Pop(T,j);for(p=G.vertices[j].firstarc;p!=NULL;p=p->nextarc){k=p->adjvex;dut=*(p->info);//对应活动<j,k>的持续时间if(vl[k]-dut<vl[j])vl[j]=vl[k]-dut;}}for(j=0;j<G.vexnum;++j)

for(p=G.vertices[j].firstarc;p;p=p->nextarc){k=p->adjvex;dut=*(p->info);ee=ve[j];el=vl[k]-dut//活动<j,k>的最早/迟开始时间if(ee==el)printf(j,k,dut,ee,el,√);

elseprintf(j,k,dut,ee,el,×);}}关键活动:调用函数求Ve,按拓扑逆序求Vl,求ee/el并输栈T:a-d-f-c-b-e-h-g-kabcdefghk6452118724417400000000064571157151418181818181818181818161486610807各顶点vl初始化成工期，按拓扑逆序(T的出栈顺序)逐个更新该元素的vl栈T:a-d-f-c-b-e-h064577151418181416107866000064577715141416023668871002302630266302866302886630278866302107886630216107886630214161078866302ee作业题1：7.10求关键活动064577151418181416107866000064单源最短路径每一对顶点之间的最短路径7.6最短路径（P187）单源最短路径每一对顶点之间的最短路径7.6最短路径（P18集合S存放已找到最短路的顶点将源并入S,初始化源到V-S中各顶点的最短路径在V-S中找长度最小的顶点并入S,据此更新再找再更新,共重复n-1轮v0v1v2v4v5100301050510v36020终点路径长度v0v0->v00v1∞V2v0->v210V3∞V4v0->v430V5v0->v5100终点路径长度v0v0->v00v1∞V2v0->v210V3v0v2v360V4v0->v430V5v0->v5100终点路径距离v0v0->v00v1∞V2v0->v210V304350V4v0->v430V5045907.6.1单源最短路径--Dijkstra算法集合S存放已找到最短路的顶点v0v1v2v4v5100301迪杰斯特拉算法实现：设辅助数组D,D[k]存储当前所得从源到顶点k的最短路长度final[k]标记k号顶点已并入SP[v][w]标记源到v的最短路上w是否出现for(v=0;v<G.vexnum;++v){final[v]=FALSE;//最初未得源点v0到v的最短路

for(w=0;w<G.vexnum;++w)p[v][w]=FALSE;//最短路最初为空,不含任何顶点

D[v]=G.arcs[v0][v];//根据v0更新

if(D[v]<InFINITY){p[v][v0]=TRUE;p[v][v]=TRUE;}//更新路径}D[v0]=0;final[v0]=ＴＲＵＥ;初始化:初始化各数组,源点并入并更新终点路径P长度Dv0v0->v00v1∞V2v0->v210V3∞V4v0->v430V5v0->v5100迪杰斯特拉算法实现：设辅助数组D,D[k]存储当前所得从源到每次循环都找距离最小新顶点并入S，更新，重复n-1轮终点路径距离v0v0->v00v1∞V2v0->v210V3∞V4v0->v430V5v0->v5100终点路径长度v0v0->v00v1∞V2v0->v210V3v0v2v360V4v0->v430V5v0->v5100v0v1v2v4v5100301050510v36020for(i=1;i<G.vexnum;++i){min=INFINITY;for(w=0;w<G.vexnum;++w)if(!final[w]&&D[w]<min){v=w;min=D[w]}final[v]=TRUE;for(w=0;w<G.vexnum;++w)if(!final[w]&&(min+G.arcs[v][w])<D[w]){D[w]=min+G.arcs[v][w];P[w][0..G.vexnum]=P[v][0..G.vexnum];//书中简写

P[w][w]=TRUE;}}每次循环都找距离最小新顶点并入S，更新，重复n-1轮终点路径迪杰斯特拉算法的实现

for(i=1;i<G.vexnum;++i){//重n-1轮,每轮找最小的,并入更新

min=INFINITY;for(w=0;w<G.vexnum;++w)if(!final[w]&&D[w]<min){v=w;min=D[w]}final[v]=TRUE;for(w=0;w<G.vexnum;++w)if(!final[w]&&(min+G.arcs[v][w]<D[w])){D[w]=min+G.arcs[v][w];P[w][0..G.vexnum]=P[v][0..G.vexnum];P[w][w]=TRUE;}}}//复杂度O(n2),单源单终点问题也是O(n2)voidShortestPath_DIJ(MGraphG,intv0,PathMatrix&P,ShortPathTable&D){for(v=0;v<G.vexnum;++v){//初始化数组，并入v0并更新

final[v]=FALSE;for(w=0;w<G.vexnum;++w)p[v][w]=FALSE;D[v]=G.arcs[v0][v];if(D[v]<InFINITY){p[v][v0]=TRUE;p[v][v]=TRUE;}}D[v0]=0;final[v0]=0;迪杰斯特拉算法的实现for(i=1;i<G.vexnum;作业说明：邻接表中表节点中存储的是下标非dataPrim算法执行过程看课件拓扑有序序列可能有多个，注意要求关键路径与单源最短路径求法看课件作业说明：邻接表中表节点中存储的是下标非data7.6.2任意一对顶点间的最短路径每次以一个顶点为源点调用Dijkstra算法，复杂度O(n3)Floyd算法(复杂度同，但形式简单):D(k)[i][j]表示从i顶点到j顶点的路径中”最短”路径的长度，要求该”最短路径”内部各顶点的标号不超过kD(-1)[i][j]表示i直接到j(内部无顶点)的情况,值G.arcs[i][j]D(0)[i][j]表i到j中间可含0号顶点;D(2)[i][j]表示i到j中间可含0、1、2号顶点;D(n-1)[i][j]意味着什么？D(k)[i][j]=min{D(k-1)[i][j],D(k-1)[i][k]+D(k-1)[k][j]}ACB4611327.6.2任意一对顶点间的最短路径每次以一个顶点为源点调用Floyd算法求任意顶点间的最短路ACB461132D(k)[i][j]k=-1,0,1,2P(k)[i][j][]k=-1,0,1,2D(-1)[i][j]=G.arcs[i][j]D(k)[i][j]=min{D(k-1)[i][j],D(k-1)[i][k]+D(k-1)[k][j]}.k=0,1,…,n-1P[i][j][k]表示i到j最短路中k号顶点是否出现765Floyd算法求任意顶点间的最短路ACB461132D(k)Floyd算法voidShortestPath_FLOYD(MGraphG,PathMatrix&P[n][n][n],DistancMatrix&D){//初始化D(-1)[][]与P(-1)[][][]for(i=0;i<G.vexnum;++i){for(j=0;j<G.vexnum;++j){D[i][j]=G.arcs[i][j];if(D[i][j]<INFINITY){P[i][j][i]=TRUE;P[i][j][j]=TRUE;}}}//递推求Dk[][]与Pk[][][],k=0->G.vexnum-1for(k=0;k<G.vexnum;++k)for(i=0;i<