算法分析与复杂性理论第7章(图)

2023/2/41第七章图2023/2/42引言图是一类重要的非线性结构；由数据和结构组成，G=(V,E)；是一种多对多的结构关系，每个元素可以有零个或多个直接前趋；零个或多个直接后继。图论的创始人是瑞士科学家欧拉，他提出并解答了著名的哥尼斯堡七桥问题，从而开创了图论的研究，请参见【L.Euler,SolutioProblematisadGeomertriamSitusPertinentis.1736】2023/2/43contents7.1图的定义和术语7.2图的存储结构7.2.1数组表示法7.2.2邻接表7.3图的遍历7.3.1深度优先搜索7.3.2广度优先搜索7.4图的连通性问题7.4.1无向图的连通分量和生成树7.4.2最小生成树7.5有向无环图及其应用7.5.1拓扑排序7.5.2关键路径7.6最短路径7.6.1从某个点源到其余各顶点的最短路径7.6.2从一对顶点之间的最短路径2023/2/447.1图的定义和术语图(Graph)——图G是由两个集合V(G)和E(G)组成的，记为G=(V,E)其中：V(G)是顶点的非空有限集

E(G)是边的有限集合，边是顶点的无序对或有序对有向图——有向图G是由两个集合V(G)和E(G)组成的

其中：V(G)是顶点的非空有限集

E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为<v,w>，v,w是顶点，v为弧尾，w为弧头无向图——无向图G是由两个集合V(G)和E(G)组成的

其中：V(G)是顶点的非空有限集

E(G)是边的有限集合，边是顶点的无序对，记为(v,w）或(w,v)，并且(v,w)=(w,v) 2023/2/45例245136G1图G1中：V(G1)={1,2,3,4,5,6}E(G1)={<1,2>,<2,1>,<2,3>,<2,4>,<3,5>,<5,6>,<6,3>}例157324G26图G2中：V(G2)={1,2,3,4,5,6,7}E(G1)={(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)}2023/2/46(1)邻接点及关联边邻接点：边的两个顶点关联边：若边e=(v,u),则称顶点v、u关连边e(2)顶点的度无向图中，顶点的度为与每个顶点相连的边数有向图中，顶点的度分成入度与出度入度：以该顶点为头的弧的数目出度：以该顶点为尾的弧的数目定理：设图G的边数为e，图的所有顶点的度数和=2*e。例245136G1顶点2入度：1出度：3顶点4入度：1出度：0例157324G26顶点5的度：3顶点2的度：42023/2/47(3)路径——路径是顶点的序列V={Vi0,Vi1,……Vin}，满足(Vij-1,Vij)E或<Vij-1,Vij>E,(1<jn)路径长度——沿路径边的数目或沿路径各边权值之和回路——第一个顶点和最后一个顶点相同的路径叫~(4)简单路径——序列中顶点不重复出现的路径叫~(5)简单回路——除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫~例245136G1路径：1，2，3，5，6，3路径长度：5简单路径：1，2，3，5回路：1，2，3，5，6，3，1简单回路：3，5，6，32023/2/48例157324G26路径：1，2，5，7，6，5，2，3路径长度：7简单路径：1，2，5，7，6回路：1，2，5，7，6，5，2，1简单回路：1，2，3，1(6)连通图连通——从顶点V到顶点W有一条路径，则说V和W是连通的连通图——图中任意两个顶点都是连通的叫~连通分量——非连通图的每一个连通部分叫~强连通图——有向图中，如果对每一对Vi,VjV,ViVj,从Vi到Vj和从Vj到Vi都存在路径，则称G是~2023/2/49连通图例245136强连通图356例非连通图连通分量例2451362023/2/410(7)子图——如果图G(V,E)和图G‘(V’,E‘),满足：V’VE’E

则称G‘为G的子图356例245136图与子图(8)完备图有向完备图——n个顶点的有向图最大边数是n(n-1)无向完备图——n个顶点的无向图最大边数是n(n-1)/22023/2/411(9)网权——与图的边或弧相关的数叫~网——带权的图叫~例213213有向完备图无向完备图例14523753186422023/2/412多重链表(了解)例G12413例15324G2V1V2^^V4^V3^

^V1

V2

V4^

V5^

V37.2图的存储结构2023/2/413邻接矩阵——表示顶点间相联关系的矩阵定义：设G=(V,E)是有n1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵例G12413例15324G22023/2/414特点：无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n²无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和有向图中，顶点Vi的出度是A中第i行元素之和顶点Vi的入度是A中第i列元素之和网络的邻接矩阵可定义为：2023/2/415例14523753186422023/2/416关联矩阵——表示顶点与边的关联关系的矩阵(了解)定义：设G=(V,E)是有n1个顶点，e0条边的图，G的关联矩阵A是具有以下性质的ne阶矩阵2023/2/4174321例G124131234例15324G21234564321562023/2/418例BDAC123456ABCD4321562023/2/419特点关联矩阵每列只有两个非零元素，是稀疏矩阵；n越大，零元素比率越大无向图中顶点Vi的度TD(Vi)是关联矩阵A中第i行元素之和有向图中，顶点Vi的出度是A中第i行中“1”的个数顶点Vi的入度是A中第i行中“-1”的个数2023/2/420邻接表实现：为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧）例aecbdG21234acdbvexdatafirstarc

4

2

1

2^^^adjvexnext5e

4

3

5^

1

5

3

2

3^邻接表首次出现于J.E.Hopcroft和R.E.Tarjan发表的论文【Algorithm447:EfficientAlgorithmsforGraphManipulation,CommunicationsoftheACM,16(1973),225~231】。2023/2/421typedefstructarcnode//定义边结构{intadjvex;//下一条边的始点编号structarcnode*nextarc;//下一条边的指针}arcnode;typedefstructvexnode//定义顶点数组{intvertex;//存放顶点信息

arcnode*firstarc;//指向第1条边的指针}adjlist;typedefstructgraphs//图类型{

adjlistadjlist[Vnum];//顶点数组

intvexnum,arcnum;//顶点个数和边条数}graph;结构定义2023/2/422创建图的基本算法//实质是：将图中的数据和关系存储起来(1)初始化图的顶点数和边数(2)初始化图的顶点数组(3)初始化图的边voidcreate(graph*g){//根据用户输入创建一个图 intn,e,i,j,k; arcnode*p,*t; cout<<"创建一个图:\t"; cout<<"顶点数:"; cin>>n; cout<<"\t\t边数:"; cin>>e; g->vexnum=n;//(1)

g->arcnum=e;//(1)

for(i=0;i<n;i++){//(2) g->adjlist[i].vertex=i; g->adjlist[i].firstarc=NULL; }//for2023/2/423 for(k=0;k<e;k++){//(3) cout<<"第"<<k+1<<"条边(结点号从0到"<<n-1<<"):"; cin>>i>>j; p=newarcnode;//创建边结点

p->adjvex=j; p->nextarc=NULL;// p->nextarc=g->adjlist[i].firstarc;// g->adjlist[i].firstarc=p;

if(g->adjlist[i].firstarc!=NULL){ t=g->adjlist[i].firstarc; while(t->nextarc!=NULL) {t=t->nextarc;} t->nextarc=p; }//if else g->adjlist[i].firstarc=p; }//for}2023/2/424voiddisp(graph*g)//输出一个图{ inti,have; arcnode*p; cout<<"输出图:"<<endl;; for(i=0;i<g->vexnum;i++) { p=g->adjlist[i].firstarc; have=0; while(p!=NULL) { cout<<"("<<i<<","<<p->adjvex<<")"; p=p->nextarc; have=1; } if(have==1)cout<<endl; }}voidmain(){ graphg; create(&g); disp(&g);}2023/2/425有向图的十字链表表示法(已介绍)弧结点：typedefstructarcnode{inttailvex,headvex;//弧尾、弧头在表头数组中位置

structarcnode*hlink；//指向弧头相同的下一条弧

structarcnode*tlink;//指向弧尾相同的下一条弧}AD;tailvexheadvexhlinktlink顶点结点：typedefstructdnode{intdata;//存与顶点有关信息

structarcnode*firstin；//指向以该顶点为弧头的第一个弧结点

structarcnode*firstout;//指向以该顶点为弧尾的第一个弧结点}DD;DDg[M];//g[0]不用datafirstinfirstout2023/2/426例bdacabcd1234

13

12

34

31

43

42

41^^^^^^^^2023/2/427无向图的邻接多重表表示法(了解)顶点结点：typedefstructdnode{intdata;//存与顶点有关的信息

structnode*firstedge;//指向第一条依附于该顶点的边}DD;DDga[M];//ga[0]不用datafirstedge边结点：typedefstructnode{intmark;//标志域

intivex,jvex;//该边依附的两个顶点在表头数组中位置

structnode*ilink,*jlink;//分别指向依附于ivex和jvex的下一条边}JD;markivexilinkjvexjlink2023/2/428例aecbd1234acdb5e

12

14

34

32

35

52^^^^^2023/2/429深度优先遍历(DFS)方法：从图的某一顶点V0出发，访问此顶点；然后依次从V0的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V0相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止V1V2V4V5V3V7V6V8例深度遍历：V1V2V4V8V5V3V6V77.3图的遍历2023/2/430V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍历：V1V2V4V8V5V6V3V7深度遍历：V1V2V4V8V5V6V3V72023/2/431V1V2V4V5V3V7V6V8例（书）:深度遍历：V1V2V4V8V3V6V7V52023/2/432深度优先遍历算法递归算法开始访问V0,置标志求V0邻接点有邻接点w求下一邻接点wV0W访问过结束NYNYDFS开始标志数组初始化Vi=1Vi访问过DFSVi=Vi+1Vi==Vexnums结束NNYY2023/2/433V1V2V4V5V3V7V6V8例深度遍历：V112341342vexdatafirstarc

2

7

8

3^^^adjvexnext55

6

4

1^

5

1

2

8

2^678678

7

3

6

3

5

4^^^V3V7V6V2V5V8V42023/2/434V1V2V4V5V3V7V6V8例12341342vexdatafirstarc

2

7

8

3^^^adjvexnext55

6^

4

8

2^678678

7^^^深度遍历：V1V3V7V6V2V4V8V52023/2/43512341342vexdatafirstarc

2

7

8

3^^^adjvexnext55

6^

4

8

2^678678

7^^^递归算法：以图中某一结点作为当前结点进行以下过程：(1)访问当前结点，并作已访问标志；(2)若当前结点有后续结点，则取第一个后续结点，若该后续结点未被访问过，则以该后继结点作为当前结点用深度优先搜索法进行访问。这是一个递归过程。2023/2/436voiddfs(graphg,intv, intvisited[]){arcnode*p;inti;cout<<v<<“”;//开始访问点visited[v]=1;p=g.adjlist[v].firstarc;while(p!=NULL){i=p->adjvex;if(visited[i]==0)

dfs(g,i,visited);p=p->nextarc;}}12341342vexdatafirstarc

2

7

8

3^^^adjvexnext55

6^

4

8

2^678678

7^^^结果2/437voidmain(){graphg;intvisited[Vnum],i,v;for(i=0;i<Vnum;i++)visited[i]=0;g=creatng();disp(&g);cout<<"输入顶点:";cin>>v;cout<<"深度优先序列:";dfs(g,v,visited);}…主函数2023/2/438广度优先遍历(BFS)方法：从图的某一顶点V0出发，访问此顶点后，依次访问V0的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止V1V2V4V5V3V7V6V8例广度遍历：V1V2V3V4V5V6V7V82023/2/439V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8广度遍历：V1V2V3V4V5V6V7V8广度遍历：V1V2V3V4V5V6V7V82023/2/440V1V2V4V5V3V7V6V8例广度遍历：V1V2V3V4V6V7V8V52023/2/441广度优先遍历算法开始标志数组初始化Vi=1Vi访问过BFSVi=Vi+1Vi==Vexnums结束NNYY2023/2/442开始访问V0,置标志求V邻接点ww存在吗V下一邻接点ww访问过结束NYNYBFS初始化队列V0入队队列空吗队头V出队访问w,置标志w入队NaaY2023/2/443(1)把队列置空(f=r)；(2)打印出发结点，置该顶点已被访问标志；(3)让出发顶点进队；(4)若队列不空(f!=r)，则(a)取出队首中的顶点v；(b)在邻接表中，以此取得与顶点v

邻接的各个顶点(i)若当前取得邻接顶点未被访问，则打印该顶点，置该顶点已被访问标志，该顶点进队；(ii)取得下个邻接顶点；(c)转(4)；(5)若队列空，则处理过程结束。例1423512341342vexdatafirstarc

5

5

4

3^^^adjvexnext55

1^

5

1

1

4

3^

2

2为何要使用队列?2023/2/444例1423512341342vexdatafirstarc

5

5

4

3^^^adjvexnext55

1^

5

1

1

4

3^

2

20123451fr遍历序列：10123454fr遍历序列：1401234543fr遍历序列：1432023/2/445例1423512341342vexdatafirstarc

5

5

4

3^^^adjvexnext55

1^

5

1

1

4

3^

2

2012345432fr遍历序列：1432012345

32fr遍历序列：1432012345

325fr遍历序列：143252023/2/446012345

25fr遍历序列/p>

5fr遍历序列/p>

fr遍历序列：14325例1423512341342vexdatafirstarc

5

5

4

3^^^adjvexnext55

1^

5

1

1

4

3^

2

22023/2/447//广度优先遍历算法实现voidbfs(graphg,intv){intqueue[Vnum],rear=-1,first=-1;intvisited[Vnum],i;arcnode*p;//for(i=0;i<Vnum;i++)visited[i]=0;cout<<v<<"";visited[v]=1;rear++;queue[rear]=v;2023/2/448while(rear!=first){

first++;

v=queue[first]; p=g.adjlist[v].firstarc; while(p!=NULL) { if(!visited[p->adjvex]) { cout<<p->adjvex<<""; visited[p->adjvex]=1; rear++;

queue[rear]=p->adjvex; } p=p->nextarc; }//while}//while}结果2/449voidbfs(graphg,intv){intqueue[Vnum],rear=-1,first=-1;intvisited[Vnum],i;arcnode*p;//for(i=0;i<Vnum;i++)visited[i]=0;

cout<<v<<"";visited[v]=1;rear++;queue[rear]=v;while(rear!=first){

first++;

v=queue[first]; p=g.adjlist[v].firstarc; while(p!=NULL){ if(!visited[p->adjvex]){ cout<<p->adjvex<<""; visited[p->adjvex]=1; rear++;

queue[rear]=p->adjvex; } p=p->nextarc; }}}结果：1327648(1)把队列置空(f=r)；(2)打印出发结点，置该顶点已被访问标志；(3)让出发顶点进队；(4)若队列不空(f!=r)，则(a)取出队首中的顶点v；(b)在邻接表中，以此取得与顶点v

邻接的各个顶点(i)若当前取得邻接顶点未被访问，则打印该顶点，置该顶点已被访问标志，该顶点进队；(ii)取得下个邻接顶点；(c)转(4)；(5)若队列空，则处理过程结束。2023/2/450作业：Dfs的非递归算法；Bfs的递归算法(尝试)。2023/2/451DFS非递归算法Dfs(Graphg,intv){//利用栈实现非递归算法 //第一个顶点入栈并访问Visit(v);visit[v]=1;push(s,v); //当栈不空时做

Whlie(!EmptyStack(s)){p=ghead[v]->firstArc; //找到栈顶的一个未被访问的邻接点，入栈并访问 while(p){w=p->adjvex; if(!visited[w]){push(s,w);visit(w); p=ghead[w]->firstArc;} elsep=p->next; }//while //如果所有邻接点都被访问，出栈

pop(s,v);}//while｝2023/2/452BFS递归算法—针对邻接矩阵的程序voidBFSTraverse(Graphg){inti;for(i=0;i<g.vexnum;i++)visited[i]=0;for(i=0;i<g.vexnum;i++)if(!visited[i])BFSM(g,i);}2023/2/453voidBFSM(Graphg,intk){ inti,j; CirQueueQ; InitQueue(&Q); cout<<g.vertex[k]<<endl; visited[k]=1; EnQueue(&Q,k); while(!QueueEmpty(&Q)) { i=DeQueue(&Q); for(j=0;j<g.vexnum;j++) if(g.edges[i][j]==1&&!visited[j]){ cout<<g.vertex[j]<<endl; visited[j]=1; EnQueue(&Q,j); } }}2023/2/454生成树定义：所有顶点均由边连接在一起，但不存在回路的图叫~分为：深度优先生成树与广度优先生成树生成森林：非连通图每个连通分量的生成树一起组成非连通图的~GHKI7.4生成树2023/2/455说明：一个图可以有许多棵不同的生成树所有生成树具有以下共同特点：生成树的顶点个数与图的顶点个数相同生成树是图的极小连通子图一个有n个顶点的连通图的生成树有n-1条边生成树中任意两个顶点间的路径是唯一的在生成树中再加一条边必然形成回路含n个顶点n-1条边的图不一定是生成树2023/2/456V1V2V4V5V3V7V6V8例深度遍历：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V8深度优先生成树V1V2V4V5V3V7V6V8广度优先生成树V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8广度遍历：V1V2V3V4V5V6V7V82023/2/457例ABLMCFDEGHKIJABLMCFJDEGHKI深度优先生成森林2023/2/458最小生成树问题提出要在n个城市间建立通信联络网，顶点——表示城市权——城市间建立通信线路所需花费代价给定一个无向网络，在图的所有生成树中，使得各边权数和最小的那棵生成树称为图的最小生成树，也叫最小代价生成树。问题分析1654327131791812752410n个城市间，最多可设置n(n-1)/2条线路n个城市间建立通信网，只需n-1条线路问题转化为：如何在可能的线路中选择n-1条，能把

所有城市（顶点）均连起来，且总耗费

（各边权值之和）最小2023/2/4591.1926年Baruvka提出了第一个最小生成树算法【O.Baruvka,“Ojistemproblemuminimalnim,”Praca

MoravskePrirodovedeckeSpolecnosti,vol.3,pp.37~58】2.1957年Prim提出了著名的Prim算法【R.C.Prim,“ShortestConnectionNetworksandSomeGeneralizations,”BellSystemTechnicalJournal,vol.36,pp.1389~1401】3.1956年Kruskal提出了著名的Kruskal算法【J.B.Kruskal,“OntheShortestSpanningSubtreeofaGraphandtheTravelingSalesmanProblem,”ProceedingsoftheAmericanMathematicalSociety,vol.7,48~50】3.当前渐进最快的最小生成树算法是1995年由Karger、Klein和Tarjan提出的随机方法【D.R.Karger,P.Klein,andR.E.Tarjan,“ARandomizedLinear-timeAlgorithmtoFindMinimumSpanningTrees,”JournaloftheACM,vol.42,321~328】4.文章【R.L.GrahamandP.Hell,“OntheHistoryoftheMinimumSpanningTreeProblem,”AnnalsoftheHistoryofComputing,vol.7,43~57】系统地介绍了最小生成树的历史。2023/2/460构造最小生成树方法一：普里姆(Prim)算法算法思想：按权值局部最小逐次将顶点和边加入到T中，直至V(T)满n个顶点为止。设N=(V,{E})是连通网，TE是N上最小生成树中边的集合初始令U={u0},(u0V),TE=在所有uU,vV-U的边(u,v)E中，找一条代价最小的边(u0,v0)将(u0,v0)并入集合TE，同时v0并入U重复上述操作直至U=V为止，则T=(V,{TE})为N的最小生成树算法实现：图用邻接矩阵表示例16543265135664252023/2/461例16543265135664251311631416431421164321425165432142532023/2/46210123450123451-21-41-11-51-3054321651356642505432114253算法：从网中任意一个顶点开始，首先把这个顶点包括在生成树里，然后在那些其一个端点已在生成树里另一个端点还未在生成树里的边中，找权值最小的一条边，并把这条边和边依附的那个不在生成树里的端点添加进生成树里。说明：对角线元素全为0。构造最小生成树的过程中，若顶点已包含在生成树里，就把其对应的对角线元素置为“1”；若边(vi,vj)已包含进生成树里，就把A[i,j]或A[j,i]位于下三角的一个置为负值。2023/2/463voidminispantree_PRIM(intad[][M],intn){inti,j,k,p,q,wm;q=p=n-1;ad[q][q]=1;

for(k=0;k<(n-1);k++){ wm=MAX;

for(i=0;i<n;i++) if(ad[i][i]==1)

for(j=0;j<n;j++) if((ad[j][j]==0)&&(ad[i][j]<wm)) { wm=ad[i][j]; p=i; q=j; }2023/2/464 ad[q][q]=1; cout<<p<<“”q<<“”<<ad[p][q]; if(p>q) ad[p][q]=-ad[p][q]; else ad[q][p]=-ad[q][p];}//for}…续上页2023/2/4652023/2/466方法二：克鲁斯卡尔(Kruskal)算法算法思想：按权值的递增次序选择合适边来构造最小生成树。设连通网N=(V,{E})，令最小生成树：初始状态为只有n个顶点而无边的非连通图T=(V,{})，每个顶点自成一个连通分量在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边依此类推，直至T中所有顶点都在同一连通分量上为止例1654326513566425165432123452023/2/467（0）用顶点数组和边数组存放顶点和边信息（1）初始时，令每个顶点的jihe互不相同；每个边的flag为0（2）选出权值最小且flag为0的边（3）若该边依附的两个顶点的jihe值不同，即非连通，则令该边的flag=1，选中该边；再令该边依附的两顶点的jihe

以及两集合中所有顶点的jihe相同若该边依附的两个顶点的jihe值相同，即连通，则令该边的flag=2，即舍去该边（4）重复上述步骤，直到选出n-1条边为止//顶点结点：typedefstruct{intdata;//顶点信息

intjihe;}VEX;边结点：typedefstruct{intvexh,vext;//边依附的两顶点

intweight;//边的权值

intflag;//标志域}EDGE;算法实现：2023/2/468例1654326513566425算法描述：datajihe124536124536124536vexhweight112213233544vextflag61535500000001342567893345566664260000111114211122222165432123452023/2/469voidminitree_KRUSKAL(void){intn,i,m,min,k,j;VEXt[M];EDGEe[M];cout<<"Inputnumberofvertexandedge:";cin>>n>>m;cout<<"Inputdataofvertex"<<endl;for(i=1;i<=n;i++){//初始化顶点 cout<<"t["<<i<<"].data=:"; cin>>t[i].data; t[i].jihe=i;}for(i=0;i<m;i++){//初始化边和权 cout<<"e["<<i<<"].vexhe["<<i<<"].vexte["<<i<<"].weight:"; cin>>e[i].vexh>>e[i].vext>>e[i].weight; e[i].flag=0;}2023/2/470i=1;while(i<n){ min=MAX; for(j=0;j<m;j++){//寻找weight最小的边，k if(e[j].weight<min&&e[j].flag==0){ min=e[j].weight;k=j;} }//for if(t[e[k].vexh].jihe!=t[e[k].vext].jihe){ e[k].flag=1; for(j=1;j<=n;j++) if(t[j].jihe==t[e[k].vext].jihe) t[j].jihe=t[e[k].vexh].jihe; t[e[k].vext].jihe=t[e[k].vexh].jihe; i++; }//使连通 elsee[k].flag=2;//已连通}//while

2023/2/471//输出代码for(i=0;i<m;i++) if(e[i].flag==1) cout<<e[i].vexh<<e[i].vext<<e[i].weight;}…续上页2023/2/4722023/2/473普里姆算法克鲁斯卡尔算法时间复杂度O(n2)O(eloge)稠密图稀疏图算法名适应范围比较两种算法2023/2/474作业实现普里姆(Prim)算法实现克鲁斯卡尔(Kruskal)算法2023/2/475问题提出：学生选修课程问题顶点——表示课程有向弧——表示先决条件，若课程i是课程j的先决条件，则图中有弧<i,j>学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业——拓扑排序定义AOV网——用顶点表示活动，用弧表示活动间优先关系的有向图，称为顶点表示活动的网(ActivityOnVertexnetwork)，简称AOV网若<vi,vj>是图中有向边，则vi是vj的直接前驱；vj是vi的直接后继AOV网中不允许有回路，这意味着某项活动以自己为先决条件7.5拓扑排序2023/2/476拓扑排序——把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫~检测AOV网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环拓扑排序的方法在有向图中选一个没有前驱的顶点且输出之从图中删除该顶点和所有以它为尾的弧重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止2023/2/477例课程代号课程名称先修棵C1C2C3C4C5C6C7C8C9C10C11C12无C1C1,C2C1C3,C4C11C3.C5C3,C6无C9C9C1,C9,C10程序设计基础离散数学数据结构汇编语言语言的设计和分析计算机原理编译原理操作系统高等数学线性代数普通物理数值分析C1C2C3C4C5C6C7C8C9C10C11C122023/2/478C1C2C3C4C5C6C7C8C9C10C11C12拓扑序列：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网的拓扑序列不是唯一的2023/2/479C1C2C3C4C5C6C7C8C9C10C11C122023/2/480C2C3C4C5C6C7C8C9C10C11C12拓扑序列：C1（1）C3C4C5C6C7C8C9C10C11C12拓扑序列：C1--C2（2）2023/2/481C4C5C6C7C8C9C10C11C12拓扑序列：C1--C2--C3（3）C5C6C7C8C9C10C11C12拓扑序列：C1--C2--C3--C4（4）2023/2/482C6C8C10C11C12拓扑序列：C1--C2--C3--C4--C5--C7--C9C6C8C11C12拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10（8）C6C7C8C9C10C11C12拓扑序列：C1--C2--C3--C4--C5（5）C6C8C9C10C11C12拓扑序列：C1--C2--C3--C4--C5--C7（6）2023/2/483C6C8C12拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11（9）C8C12拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6（10）C8拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12（11）拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8（12）2023/2/484算法实现以邻接表作存储结构把邻接表中所有入度为0的顶点进栈栈非空时，输出栈顶元素Vj并退栈；在邻接表中查找Vj的直接后继Vk，把Vk的入度减1；若Vk的入度为0则进栈重复上述操作直至栈空为止。若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕(1)选无前驱结点输出(2)删除该点及其出边2023/2/485邻接表结点：typedefstructarcnode{intadjvex;//顶点域

structarcnode*next;//链域}arcnode;表头结点：typedefstructvexnode{

intvexdata;

//顶点信息intin;//入度域

arcnode

*firstarc;//链域}adjlist[Vnum];例123456typedefstructgraphs{adjlistadjlist;intvexnum,arcnum;}graph;2023/2/48632104算法描述例1234560122inlink

5

5

4

3^^^vexnext3^

2

5^

2

40123456^top16toptop2023/2/4870122inlink

5

5

4

3^^^vexnext3^

2

5^

2

40123456^输出序列：63210416toptop2023/2/4880122inlink

5

5

4

3^^^vexnext3^

2

5^

2

40123456^输出序列：6321041topp2023/2/4890122inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^输出序列：6321041topp2023/2/4900122inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^输出序列：6321041topp2023/2/4910112inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^输出序列：6321041topp2023/2/4920112inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^输出序列：6321041topp=NULL2023/2/4930112inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^输出序列：61321041toptop2023/2/4940112inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^输出序列：6132104topp2023/2/4950102inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^输出序列：6132104topp42023/2/4960102inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^输出序列：6132104p4top2023/2/4970102inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^输出序列：6132104p4top2023/2/4980002inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^输出序列：6132104p4top32023/2/4990002inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^输出序列：6132104p4top32023/2/41000002inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^输出序列：6132104p4top32023/2/41010001inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^输出序列：6132104p4top32023/2/41020001inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^输出序列：6132104p=NULL4top32023/2/41030001inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^输出序列：613321044top32023/2/41040001inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^输出序列：613321044topp2023/2/41050001inlink

5

5

4

3^^^vexnext1^

2

5^

2

40123456^输出序列：613321044topp2023/2/41060001inlink

5

5

4

3^^^vexnext1^

2

5^

2

40123456^输出序列：613321044topp2023/2/41070000inlink

5

5

4

3^^^vexnext1^

2

5^

2

40123456^输出序列：613321044topp22023/2/41080000inlink

5

5

4

3^^^vexnext1^

2

5^

2

40123456^输出序列：613321044topp22023/2/41090000inlink

5

5

4

3^^^vexnext1^

2

5^

2

40123456^输出序列：613321044top2p=NULL2023/2/41100000inlink

5

5

4

3^^^vexnext1^

2

5^

2

40123456^输出序列：6132321044top2p=NULL2023/2/41110000inlink

5

5

4

3^^^vexnext1^

2

5^

2

40123456^输出序列：6132321044topp=NULL2023/2/41120000inlink

5

5

4

3^^^vexnext1^

2

5^

2

40123456^输出序列：61324321044top2023/2/41130000inlink

5

5

4

3^^^vexnext1^

2

5^

2

40123456^输出序列：6132432104topp2023/2/41140000inlink

5

5

4

3^^^vexnext0^

2

5^

2

40123456^输出序列：6132432104topp52023/2/41150000inlink

5

5

4

3^^^vexnext0^

2

5^

2

40123456^输出序列：6132432104topp=NULL52023/2/41160000inlink

5

5

4

3^^^vexnext0^

2

5^

2

40123456^输出序列：61324532104top52023/2/41170000inlink

5

5

4

3^^^vexnext0^

2

5^

2

40123456^输出序列：61324532104topp=NULL2023/2/4118voidtoposort(graph*g){ inttop,m,k,j,s[20]; arcnode*p; top=0;m=0; for(j=0;j<g->vexnum;j++) if(g->adjlist[j].in==0) s[top++]=j;//进栈

while(top>0){ j=s[--top]; cout<<g->adjlist[j].vexdata<<""; m++; p=g->adjlist[j].firstarc;2023/2/4119 while(p!=NULL) { k=p->adjvex; g->adjlist[k].in--; if(g->adjlist[k].in==0) s[top++]=k; p=p->nextarc; } } cout<<endl; cout<<"输出的顶点个数:"<<m<<endl; if(m<g->vexnum) cout<<"Thenetworkhasacycle\n";}503241…续上页2023/2/4120问题提出把工程计划表示为有向图，用顶点表示事件，弧表示活动；每个事件表示在它之前的活动已完成，在它之后的活动可以开始例设一个工程有11项活动，9个事件事件V1——表示整个工程开始事件V9——表示整个工程结束问题：（1）完成整项工程至少需要多少时间？（2）哪些活动是影响工程进度的关键？987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=47.6关键路径2023/2/4121定义AOE网(ActivityOnEdge)——也叫边表示活动的网。AOE网是一个带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间路径长度——路径上各活动持续时间之和关键路径——路径长度最长的路径叫~Ve(j)——表示事件Vj的最早发生时间Vl(j)——表示事件Vj的最迟发生时间e(i)——表示活动ai的最早开始时间l(i)——表示活动ai的最迟开始时间l(i)-e(i)——表示完成活动ai的时间余量关键活动——关键路径上的活动叫~，即l(i)=e(i)的活动2023/2/4122问题分析如何找e(i)=l(i)的关键活动？设活动ai用弧<j,k>表示，其持续时间记为：dut(<j,k>)则有：（1）e(i)=Ve(j)

（2）l(i)=Vl(k)-dut(<j,k>)jkai如何求Ve(j)和Vl(j)？(1)从Ve(1)=0开始向前递推(2)从Vl(n)=Ve(n)开始向后递推2023/2/4123求关键路径步骤求Ve(i)求Vl(j)求e(i)求l(i)计算l(i)-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9顶点VeVl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活动ell-e000022660462583770770710316160141400332023/2/4124算法实现以邻接表作存储结构从源点V1出发，令Ve[1]=0,按拓扑序列求各顶点的Ve[i]从汇点Vn出发，令Vl[n]=Ve[n],按逆拓扑序列求其余各顶点的Vl[i]根据各顶点的Ve和Vl值，计算每条弧的e[i]和l[i],找出e[i]=l[i]的关键活动邻接表结点：typedefstructnode{intvex;//顶点域

intlength;structnode*next;//链域}JD;表头结点：typedefstructtnode{intvexdata;intin;//入度域

structnode*link;//链域}TD;TDg[M];//g[0]不用2023/2/4125算法描述输入顶点和弧信息，建立其邻接表计算每个顶点的入度对其进行拓扑排序排序过程中求顶点的Ve[i]将得到的拓扑序列进栈按逆拓扑序列求顶点的Vl[i]计算每条弧的e[i]和