算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案PAGE1-算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案一、課設(shè)目的與要求本次課設(shè)主要是圖的基本操作與應(yīng)用，共包括四個部分：有向圖的基本操作與應(yīng)用、無向圖的基本操作與應(yīng)用、有向網(wǎng)的基本操作與應(yīng)用、無向網(wǎng)的基本操作與應(yīng)用。測試文件(test.cpp)已給出。*********************************text.cpp**********************************#include<iostream>usingnamespacestd;typedefcharVertexType;typedefintElemtpye;#include"Graph.h"#include"DGraph.h"#include"UNGraph.h"#include"UDGraph.h"#include"DNGraph.h"voidShowMainMenu(){ cout<<"\n"; cout<<"***************圖的基本操作及應(yīng)用******************\n"; cout<<"*1無向圖的基本操作及應(yīng)用*\n"; cout<<"*2無向網(wǎng)的基本操作及應(yīng)用*\n";cout<<"*3有向圖的基本操作及應(yīng)用*\n"; cout<<"*4有向網(wǎng)的基本操作及應(yīng)用*\n"; cout<<"*5退出*\n"; cout<<"***************************************************\n";}voidUDG(){ MGraphMG; ALGraphALG; intn; do {算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第1頁。 cout<<"\n";算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第1頁。 cout<<"***************無向圖的基本操作及應(yīng)用***************\n"; cout<<"*1創(chuàng)建無向圖的鄰接矩陣*\n"; cout<<"*2創(chuàng)建無向圖的鄰接表*\n"; cout<<"*3無向圖的深度優(yōu)先遍歷*\n"; cout<<"*4無向圖的廣度優(yōu)先遍歷*\n"; cout<<"*5退出*\n"; cout<<"*************************************************\n"; cin>>n; switch(n){ case1: CreatUDG_M(MG); break; case2: { CreatUDG_ALG(ALG); dispgraph(ALG); } break; case3: { CreatUDG_ALG(ALG); cout<<"您打算從第幾個頂點(diǎn)開始訪問?"<<endl; cin>>n; DFS(ALG,n); } break; case4: { CreatUDG_ALG(ALG); cout<<"您打算從第幾個頂點(diǎn)開始訪問?"<<endl; cin>>n; BFS(ALG,n); } break; default: if(n!=5) cout<<"錯誤，重新輸入\n"; } }while(n!=5);}voidUDN(){ MGraphMG;算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第2頁。 ALGraphALG;算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第2頁。 intn; do{ cout<<"\n"; cout<<"***************無向網(wǎng)的基本操作及應(yīng)用***************\n"; cout<<"*1創(chuàng)建無向網(wǎng)的鄰接矩陣*\n"; cout<<"*2創(chuàng)建無向網(wǎng)的鄰接表*\n"; cout<<"*3prim算法求最小生成樹*\n"; cout<<"*4kraskal算法求最小生成樹*\n"; cout<<"*5退出*\n"; cout<<"****************************************************\n"; cin>>n; switch(n){ case1: CreatUNG_M(MG); break; case2: { CreatUNG_ALG(ALG); dispgraph(ALG); } break; case3: { CreatUNG_M(MG); cout<<"起始出發(fā)頂點(diǎn)為："; cin>>n; Prim(MG,n); } break; case4: { CreatUNG_M(MG); Kruskal(MG); } break; default: if(n!=5) cout<<"錯誤，重新輸入\n"; } }while(n!=5); }voidDG()算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第3頁。算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第3頁。 MGraphMG; ALGraphALG; intn; do { cout<<"\n"; cout<<"***************有向圖的基本操作及應(yīng)用***************\n"; cout<<"*1創(chuàng)建有向圖的鄰接矩陣*\n"; cout<<"*2創(chuàng)建有向圖的鄰接表*\n"; cout<<"*3拓?fù)渑判?\n"; cout<<"*4退出*\n"; cout<<"****************************************************\n"; cin>>n; switch(n){ case1: CreatDG_M(MG); break; case2: { CreatDG_ALG(ALG); dispgraph(ALG); } break; case3: { CreatDG_ALG(ALG);TopoSort(ALG); } break; default: if(n!=4) cout<<"錯誤，重新輸入\n"; } }while(n!=4);}voidDN(){ MGraphMG; ALGraphALG; intn; do{ cout<<"\n"; cout<<"***************有向網(wǎng)的基本操作及應(yīng)用***************\n";算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第4頁。 cout<<"*1創(chuàng)建有向網(wǎng)的鄰接矩陣*\n"算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第4頁。 cout<<"*2創(chuàng)建有向網(wǎng)的鄰接表*\n"; cout<<"*3關(guān)鍵路徑*\n"; cout<<"*4單源頂點(diǎn)最短路徑問題*\n"; cout<<"*5每對頂點(diǎn)最短路徑問題*\n"; cout<<"*6退出*\n"; cout<<"****************************************************\n"; cin>>n; switch(n) { case1: CreatDNG_M(MG); break; case2: { CreatDNG_ALG(ALG); dispgraph(ALG); } break; case3: { CreatDNG_ALG(ALG);KeyPath(ALG); } break; case4: { CreatDNG_M(MG); cout<<"起始出發(fā)頂點(diǎn)為："; cin>>n; SinMiniPathD(MG,n); } break; case5: { CreatDNG_M(MG); DouMiniPathF(MG); } break; default: if(n!=6) cout<<"錯誤，重新輸入\n"; } }while(n!=6);算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第5頁。算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第5頁。}voidmain(){ intn; do{ ShowMainMenu(); cin>>n; switch(n){ case1: UDG(); break; case2:UDN(); break; case3: DG(); break; case4: DN(); break; default: if(n!=5) cout<<"錯誤，重新輸入\n"; } }while(n!=5);}圖是由若干個頂點(diǎn)和若干條邊構(gòu)成的結(jié)構(gòu)，每個頂點(diǎn)具有任意多個前驅(qū)和后繼。頂點(diǎn)是一些具體對象的抽象，而邊是對象間關(guān)系的抽象。在具體應(yīng)用中，頂點(diǎn)和邊被賦予具體的含義。如一個交通圖中，用頂點(diǎn)代表城市，邊表示城市之間的交通聯(lián)系。其形式化定義為：G=（V，E）V=｛vi|vi∈dataobject｝E={(vi,vj)|vi,vj∈V∧P(vi,vj)}圖是一種結(jié)構(gòu)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，其信息包括兩部分：圖中數(shù)據(jù)元素即頂點(diǎn)的信息，元素間的關(guān)系（頂點(diǎn)之間的關(guān)系）——邊或者弧的信息。無論采用爰方法建立圖的存儲結(jié)構(gòu)，都要完整、準(zhǔn)確地反映這兩方面的信息。一般情況下圖有四種存儲結(jié)構(gòu)：鄰接矩陣存儲、鄰接表存儲、十字鏈表存儲、鄰接多重表存儲。此次僅討論前兩種存儲結(jié)構(gòu)。二、無向圖的基本操作與應(yīng)用無向圖的基本操作與應(yīng)用包括用鄰接矩陣和鄰接表構(gòu)造無向圖以及以鄰接表為存儲結(jié)構(gòu)的無向圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷。2.1、設(shè)計方案無向圖可以用鄰接矩陣、鄰接表兩種存儲結(jié)構(gòu)來表示，用一維數(shù)組存儲圖的頂點(diǎn)的信息，用二維數(shù)組存儲圖中邊或弧的信息，該二維數(shù)組稱為鄰接矩陣。設(shè)G=（V，E）為具有n個頂點(diǎn)的圖，若用二維數(shù)組A表示圖的鄰接矩陣，則A是一個n階的方陣，其中：A［i］［j］=鄰接矩陣的存儲結(jié)構(gòu)定義如下：算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第6頁。#defineMAXVEX30算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第6頁。typedefcharVertexType;/*頂點(diǎn)類型設(shè)為字符型*/typedefstruct{ VertexTypevexs[MAXVEX];/*頂點(diǎn)表*/intarcs[MAXVEX][MAXVEX];/*鄰接矩陣*/intvexnum,arcnum;/*圖中頂點(diǎn)數(shù)和邊數(shù)*/}MGraph;/*鄰接矩陣存儲的圖類型*/無向圖的鄰接矩陣是一個對稱矩陣，其第i行（或第i列）非零元素的個數(shù)為第i個頂點(diǎn)的度TD（vi）。有向圖的鄰接矩陣的第i行非零元素的個數(shù)正好為第i個頂點(diǎn)的出度OD（vi）,第i列非零元素的個數(shù)為第i個頂點(diǎn)的入度ID（vi）。鄰接表表示法類似于樹的孩子鏈表表示法。它對圖中的每個頂點(diǎn)vi建立一個帶頭結(jié)點(diǎn)的線性鏈表，用于存儲圖中與vi相鄰接的邊或信息。頭結(jié)點(diǎn)中存放該頂點(diǎn)的信息。所有頭結(jié)點(diǎn)用一個順序表存放。其中，頭結(jié)點(diǎn)由兩個域組成：存儲頂點(diǎn)信息的data域和指向鏈表中第一個結(jié)點(diǎn)的指針域firstarc。表結(jié)點(diǎn)由三個域組成：鄰接點(diǎn)域dajvex、指向下一條邊或弧的指針域nextarc和存儲邊或弧上相關(guān)信息（如權(quán)值等）的域info。鄰接表表示遠(yuǎn)射圖，每條邊（vi,vj）在兩個頂點(diǎn)vi,vj的鏈表中各占一個表節(jié)點(diǎn)。因此，每條邊在鏈表中存儲兩次。若無向圖中有n個頂點(diǎn)、e條邊，則它的鄰接表需n個頭結(jié)點(diǎn)和2e個表結(jié)點(diǎn)。頂點(diǎn)vi的度恰為第i個鏈表中的結(jié)點(diǎn)數(shù)。鄰接表存儲結(jié)構(gòu)的定義如下：typedefstructArcNode{ intadjvex;//鄰接點(diǎn)序號 intw;//邊或狐上的權(quán) structArcNode*next;}ArcNode;typedefstructvnode{ VertexTypedata;//頂點(diǎn)信息 intindegree; ArcNode*firstarc;//指向下一個邊結(jié)點(diǎn)}Vnode,AdjList[MAXVEX];typedefstruct{ AdjListvertices;intvexnum,arcnum;}ALGraph;鄰接表存儲圖很容易找到任一頂點(diǎn)的鄰接點(diǎn)，但要判定任意兩個頂點(diǎn)(vi和vj)之間是否有邊或弧相連，則需搜索第i個或第j個鏈表，不及鄰接矩陣方便。設(shè)圖G有n個頂點(diǎn)，e條邊，圖的鄰接矩陣表示的空間代價是O(n2),只與圖的頂點(diǎn)數(shù)有關(guān)。若圖G是無向圖，圖的鄰接表表示的空間代價是O(n+2e)；若圖G是有向圖，圖的鄰接表表示的空間代價是O(n+e)。2.2、實(shí)現(xiàn)過程鍵盤輸入圖的頂點(diǎn)數(shù)和邊數(shù)，用循環(huán)來實(shí)現(xiàn)頂點(diǎn)的數(shù)組G.vexs[i]，用同樣的方法構(gòu)造出鄰接矩陣。兩點(diǎn)這有邊的賦值為1，否則為0。用鄰接矩陣創(chuàng)建無向圖的函數(shù)為CreatUDG_M(MGraph&G)，用鄰接表創(chuàng)建無向圖的函數(shù)為CreatUDG_ALG(ALGraph&G)。其代碼參見頭文件UDGraph.h。給定一個圖G，我們希望從圖中的某個頂點(diǎn)出發(fā)，經(jīng)過一定的路線訪問圖中所有可訪問的頂點(diǎn)，使每個可訪問到的頂點(diǎn)都被訪問且只被訪問一次。這一過程稱為圖的遍歷。算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第7頁。算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第7頁。圖的遍歷通常有深度優(yōu)先遍歷和廣度優(yōu)先遍歷兩種方式。2.2.1嘗試優(yōu)先遍歷深度優(yōu)先遍歷類似于樹的先根遍歷，是樹的先根遍歷的推廣。其具體思想是：從圖中某個頂點(diǎn)v出發(fā)，訪問此頂點(diǎn)，然后依次從v的未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直到圖中所有和v有路徑相通的頂點(diǎn)都被訪問到。若此時圖中還有頂點(diǎn)未被訪問，另選圖中一個未曾被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直到圖中所有頂點(diǎn)都被訪問到為止。這是一個遞歸的過程。以鄰接表為圖的存儲結(jié)構(gòu)的深度優(yōu)先遍歷算法如下：intvisited[MAXVEX]={0};voidDFS(ALGraphG,intv){ ArcNode*p; visited[v]=1; printf("[%d,%c]",v,G.vertices[v].data); p=G.vertices[v].firstarc; while(p) { if(!visited[p->adjvex]) DFS(G,p->adjvex); p=p->next; }}算法運(yùn)行結(jié)果如下圖所示：算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第8頁。在遍歷時，對圖中每個頂點(diǎn)至多訪問一次DFS函數(shù)，因?yàn)橐坏┠硞€頂點(diǎn)被標(biāo)志成已被訪問，就不再從它出發(fā)進(jìn)行搜索。因此，遍歷圖的過程實(shí)質(zhì)上是對每個頂點(diǎn)查找其鄰接點(diǎn)的過程。其耗費(fèi)的時間則取決于所采用的存儲結(jié)構(gòu)。對于n個頂點(diǎn)，e條邊或弧的圖，當(dāng)用鄰接矩陣作其存儲結(jié)構(gòu)時，深度遍歷圖的時間復(fù)雜度為O(n2算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第8頁。2.2.2廣度倚靠遍歷廣度優(yōu)先遍歷類似于樹的層次遍歷。其基本思想是：從圖中某頂點(diǎn)v出發(fā)，在訪問了v之后依次訪問v的各個未曾訪問未被訪問過的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)依次訪問它們的鄰接點(diǎn)，并使“先被訪問的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問的頂點(diǎn)的鄰接點(diǎn)”被訪問，直到圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到。若此時圖中尚有頂點(diǎn)未被訪問，則另選圖中一個未曾被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直到圖中所有頂點(diǎn)都被訪問到為止。以鄰接表作為圖的存儲結(jié)構(gòu)的廣度優(yōu)先遍歷算法如下：voidBFS(ALGraphG,intv){ LinkQueueQ; intvi; ArcNode*p; InitQueue(Q); visited[v]=1; printf("[%d,%c]",v,G.vertices[v].data); EnQueue(Q,v); while(!QueueEmpty(Q)) { EnQueue(Q,vi); p=G.vertices[vi].firstarc; while(p) { if(visited[p->adjvex]!=1) { visited[p->adjvex]=1; printf("[%d,%c]",p->adjvex,G.vertices[p->adjvex].data); EnQueue(Q,p->adjvex); } p=p->next; } }算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第9頁。}算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第9頁。2.2.3代碼實(shí)現(xiàn)*********************************UDGraph.h**********************************#include"LinkQueue.h"voidCreatUDG_M(MGraph&G){inti,j,c;cout<<"請輸入頂點(diǎn)數(shù),邊數(shù):"; cin>>G.vexnum>>G.arcnum;printf("請輸入頂點(diǎn):"); for(i=1;i<=G.vexnum;i++) cin>>G.vexs[i]; for(i=1;i<=G.vexnum;i++) for(j=1;j<=G.vexnum;j++) G.arcs[i][j]=0; printf("請輸入邊:\n"); for(c=1;c<=G.arcnum;c++) { cin>>i>>j;G.arcs[i][j]=1;G.arcs[j][i]=1; } cout<<"創(chuàng)建的鄰接矩陣為："<<endl; for(i=1;i<=G.vexnum;i++) { for(j=1;j<=G.vexnum;j++)算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第10頁。 cout<<G.arcs[i][j]<<""算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第10頁。cout<<endl; } cout<<"鄰接矩陣創(chuàng)建完畢"<<endl;}算法運(yùn)行結(jié)果如下圖所示：voidCreatUDG_ALG(ALGraph&G){inti,s,d;ArcNode*p,*q; cout<<"請輸入頂點(diǎn)數(shù),邊數(shù)："; cin>>G.vexnum>>G.arcnum;for(i=1;i<=G.vexnum;i++) { printf("第%d個結(jié)點(diǎn)信息:",i); cin>>G.vertices[i].data; G.vertices[i].firstarc=NULL; }for(i=1;i<=G.arcnum;i++){ printf("第%d條邊=>起點(diǎn)序號,終點(diǎn)序號:",i); cin>>s>>d; p=(ArcNode*)malloc(sizeof(ArcNode)); q=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=d; q->adjvex=s; p->next=G.vertices[s].firstarc;/*p插入頂點(diǎn)s的鄰接表中*/算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第11頁。算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第11頁。 q->next=G.vertices[d].firstarc;/*q插入頂點(diǎn)d的鄰接表中*/ G.vertices[d].firstarc=q; }}算法運(yùn)行結(jié)果如下圖所示：voiddispgraph(ALGraphG){ inti;ArcNode*p;printf("圖的鄰接表表示如下:\n");for(i=1;i<=G.vexnum;i++){ printf("[%d,%c]=>",i,G.vertices[i].data); p=G.vertices[i].firstarc; while(p!=NULL) { printf("[%d→]",p->adjvex); p=p->next; } printf("∧\n"); }}intvisited[MAXVEX]={0};voidDFS(ALGraphG,intv){ ArcNode*p; visited[v]=1; printf("[%d,%c]",v,G.vertices[v].data); p=G.vertices[v].firstarc; while(p) { if(!visited[p->adjvex])算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第12頁。算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第12頁。 p=p->next; }}voidBFS(ALGraphG,intv){ LinkQueueQ; intvi; ArcNode*p; InitQueue(Q); visited[v]=1; printf("[%d,%c]",v,G.vertices[v].data); EnQueue(Q,v); while(!QueueEmpty(Q)) { DeQueue(Q,vi); p=G.vertices[vi].firstarc; while(p) { if(visited[p->adjvex]!=1) { visited[p->adjvex]=1; printf("[%d,%c]",p->adjvex,G.vertices[p->adjvex].data); EnQueue(Q,p->adjvex); } p=p->next; } }}三、無向網(wǎng)的基本操作與應(yīng)用無向圖的基本操作與應(yīng)用包括用鄰接矩陣和鄰接表創(chuàng)建無向網(wǎng)以及以鄰接矩陣為存儲結(jié)構(gòu)的兩種算法求最小生成樹(Prim算法和Kruskal算法)。3.1、設(shè)計方案用與構(gòu)造無向圖相似的的方式可以構(gòu)造出鄰接矩陣和鄰接表。無向網(wǎng)的鄰接矩陣可定義為：A［i］［j］=其中，Wij表示邊(vi,vj)或弧<vi,vj>上的權(quán)值；∞表示一個計算機(jī)允許的、大于所有邊上權(quán)值的數(shù)。鄰接矩陣存儲結(jié)構(gòu)定義如下：#defineMAXVEX30/*最大頂點(diǎn)數(shù)設(shè)為20*/typedefcharVertexType;/*頂點(diǎn)類型設(shè)為字符型*/typedefstruct{ VertexTypevexs[MAXVEX];/*頂點(diǎn)表*/算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第13頁。intarcs[MAXVEX][MAXVEX];算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第13頁。intvexnum,arcnum;/*圖中頂點(diǎn)數(shù)和邊數(shù)*/}MGraph;/*鄰接矩陣存儲的圖類型*/無向網(wǎng)的鄰接表構(gòu)造方法與無向圖的構(gòu)造方法相似，只需要在表結(jié)點(diǎn)中加入權(quán)值w即可。其代碼如下：typedefstructArcNode{ intadjvex;//鄰接點(diǎn)序號 intw;//邊或狐上的權(quán) structArcNode*next;}ArcNode;typedefstructvnode{ VertexTypedata;//頂點(diǎn)信息 intindegree; ArcNode*firstarc;//指向下一個邊結(jié)點(diǎn)}Vnode,AdjList[MAXVEX];typedefstruct{ AdjListvertices;intvexnum,arcnum;}ALGraph;3.2、實(shí)現(xiàn)過程其實(shí)現(xiàn)過程同無向圖的實(shí)現(xiàn)過程類似，其邊的輸入由由邊的兩個頂點(diǎn)和邊上的權(quán)組成。用鄰接矩陣創(chuàng)建無向網(wǎng)的函數(shù)為CreatUNG_M(MGraph&G)，用鄰接表創(chuàng)建無向網(wǎng)的函數(shù)為CreatUNG_ALG(ALGraph&G)，其代碼參見頭文件UNGraph.h。構(gòu)造最小生成樹可以有多種算法，以下是普里姆算法，克魯斯卡爾算法的說明。3.2.1普里姆算法假設(shè)N=(V,E)是連通網(wǎng)，T=(U,TE)為N的最小生成樹，U是T的頂點(diǎn)集合，TE是T的邊集合。普里姆算法的基本思想是：首先從集合V中任取一頂點(diǎn)(假設(shè)為u0)加入集合U中，這時U={u0}，TE={}，然后所有u∈U，v∈V-U的邊(u,v)∈E中，選取具有最小權(quán)值的邊(u0,v0)加入集合TE，同時將頂點(diǎn)v0并入集合U中。重復(fù)上述操作，直到U=V為止。此時TE中必有n-1條邊，T=(U,TE)為N的最小生成樹。為實(shí)現(xiàn)prim算法，需設(shè)置一個輔助數(shù)組closedge，記錄從U到V-U集合具有最小代價的邊。對每個頂點(diǎn)vi∈V-U，在輔助數(shù)組中存在一個相應(yīng)分量closedge［i-1］，它包括兩個域：adjvex和lowcost，其中adjvex存儲該邊依附于集合U中的頂點(diǎn)，lowcost存儲該邊的權(quán)值。Closedge的結(jié)構(gòu)定義為：struct { intadjvex;/*該邊依附于集合U中的頂點(diǎn)*/ intlowcost;/*該邊的權(quán)值*/ }closedge[MAXVEX];算法中將第i個頂點(diǎn)(設(shè)為vi+1)并入集合U中通過設(shè)置closedge[i].lowcost=0實(shí)現(xiàn)(即用closedge[i].lowcost=0表示頂點(diǎn)vi+1在U集合中,closedge[i].lowcost不為0表示vi+1在V-U集合中)；選取U集合到V-U集合具有最小權(quán)值的邊，通過在所有closedge[i].lowcost！=0(V-U集合中的頂點(diǎn))的closedge[i].lowcost中選擇最小的值來實(shí)現(xiàn)。算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第14頁。不妨設(shè)無向網(wǎng)采用鄰接矩陣存儲(MgraphG)，若存在分量closedge[i].lowcost=0，closedge[i].adjvex=i，表示頂點(diǎn)G.vexs[j]已并入U集合，(G.vexs[i],G.vexs[j])算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第14頁。初始狀態(tài)時，U=｛u1｝(u1為出發(fā)的頂點(diǎn))，初始closedge[0].lowcost=0，數(shù)組的其他各分量的lowcost域是頂點(diǎn)u1到其余各頂點(diǎn)所構(gòu)成的邊的權(quán)值，adjvex域?yàn)?.然后不斷選取權(quán)值最小的邊(ui,uj)(ui∈U,uj∈V-U)，每選取一條邊，設(shè)置closedge[k-1].lowcost=0表示頂點(diǎn)uk已加入集合U中。由于頂點(diǎn)uk從集合V-U進(jìn)入集合U后，這兩個集合的內(nèi)容發(fā)生了變化，就需依據(jù)具體情況更新數(shù)組closedge中部分分量的內(nèi)容。最后closedge中即為所建立的最小生成樹。當(dāng)無向網(wǎng)采用鄰接矩陣存儲時，Prim算法如下：voidPrim(MGraphG,intv){ struct { intadjvex; intlowcost; }closedge[MAXVEX]; inti,j,k,min; for(i=1;i<=G.vexnum;i++) { closedge[i].lowcost=G.arcs[v][i]; closedge[i].adjvex=v; } closedge[v].lowcost=0; for(i=1;i<G.vexnum;i++) { min=MAXCOST; for(j=1;j<=G.vexnum;j++) if(closedge[j].lowcost!=0&&closedge[j].lowcost<min) { min=closedge[j].lowcost; k=j; } printf("(%c,%c,%d)",G.vexs[closedge[k].adjvex],G.vexs[k],min); closedge[k].lowcost=0; for(j=1;j<=G.vexnum;j++) if(closedge[j].lowcost!=0&&G.arcs[k][j]<closedge[j].lowcost) { closedge[j].lowcost=G.arcs[k][j]; closedge[j].adjvex=k; } }算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第15頁。}算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第15頁。假設(shè)網(wǎng)中有n個頂點(diǎn)，Prim算法的時間復(fù)雜度為O(n2),與網(wǎng)中的邊數(shù)無關(guān)，因此適用于求稠密網(wǎng)的最小生成樹。3.2.2克魯斯卡爾算法克魯斯卡爾算法是一種按照網(wǎng)中邊權(quán)值不減的順序構(gòu)造最小生成樹的方法。其基本思想是：設(shè)無向網(wǎng)為N=(V,E)，令N的最小生成樹的初態(tài)為只含有n個頂點(diǎn)而無邊的非連通圖T=(V,{})，圖中每個頂點(diǎn)自成一個連通分量。在E中選擇權(quán)值最小的邊，若該邊依附的兩個頂點(diǎn)落在T中不同的連通分量上，則將該邊加入到T中，否則舍去此邊，選擇下一條權(quán)值最小的邊。依次類推，直到T中所有頂點(diǎn)都在同一連通分量上為止。此連通分量便為G的一棵最小生成樹。在訪問各頂點(diǎn)的同時，用循環(huán)語句計算出權(quán)值最小的兩個頂點(diǎn)，并用a、b記錄其弧頭和弧尾的頂點(diǎn)。為了判斷某條邊加入到T集合是否構(gòu)成回路，可以定義一個一維數(shù)組set[n]，存放T中每個頂點(diǎn)所在的連通分量的標(biāo)號。其初值為set[i]=i(i=0,1,2,…,n-1)，表示各個頂點(diǎn)在不同的連通分量上。訪問最小權(quán)值依附的兩個頂點(diǎn)，若它們不屬于同一個分量，則將這條邊作為最小生成樹的邊輸出，并合并它們所屬的兩個連通分量；若它們屬于同一分量，則選擇下一個最小權(quán)值依附的邊。其實(shí)現(xiàn)代碼如下：voidKruskal(MGraphG){ intset[MAXVEX],i,j; intk=0,a=1,b=1,min=G.arcs[a][b]; for(i=0;i<G.vexnum;i++) set[i]=i; cout<<"最小生成樹的各條邊為："<<endl; while(k<G.vexnum-1) { for(i=0;i<G.vexnum;i++)算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第16頁。 for算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第16頁。 if(G.arcs[i+1][j+1]<min) { min=G.arcs[i+1][j+1];//最小權(quán)值 a=i+1; b=j+1; } min=G.arcs[a][b]=MAXCOST;//刪除該邊，下次不再查找 if(set[a]!=set[b]) { cout<<G.vexs[a]<<"->"<<G.vexs[b]<<endl; k++; for(i=0;i<G.vexnum;i++) if(set[i]==set[b])//將頂點(diǎn)b所在集合并入頂點(diǎn)a集合中 set[i]=set[a]; } }}算法運(yùn)行結(jié)果如下圖所示：3.2.3代碼實(shí)現(xiàn)*********************************UNGraph.h**********************************算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第17頁。void算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第17頁。{inti,j,c,w;cout<<"請輸入頂點(diǎn)數(shù),邊數(shù):"; cin>>G.vexnum>>G.arcnum;printf("請輸入頂點(diǎn):"); for(i=1;i<=G.vexnum;i++) cin>>G.vexs[i]; for(i=1;i<=G.vexnum;i++) for(j=1;j<=G.vexnum;j++) G.arcs[i][j]=MAXCOST; printf("請輸入邊和權(quán)值:\n"); for(c=1;c<=G.arcnum;c++) { cin>>i>>j>>w;G.arcs[i][j]=w;G.arcs[j][i]=w; } cout<<"創(chuàng)建的鄰接矩陣為："<<endl; for(i=1;i<=G.vexnum;i++) { for(j=1;j<=G.vexnum;j++) cout<<G.arcs[i][j]<<""; cout<<endl; } cout<<"鄰接矩陣創(chuàng)建完畢"<<endl;}算法運(yùn)行結(jié)果如下圖所示：算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第18頁。void算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第18頁。{inti,s,d,w;ArcNode*p; ArcNode*q; cout<<"請輸入頂點(diǎn)數(shù),邊數(shù)："; cin>>G.vexnum>>G.arcnum;for(i=1;i<=G.vexnum;i++) { printf("第%d個結(jié)點(diǎn)信息:",i); cin>>G.vertices[i].data; G.vertices[i].firstarc=NULL; }for(i=1;i<=G.arcnum;i++){ printf("第%d條邊=>起點(diǎn)序號,終點(diǎn)序號，權(quán)值:",i); cin>>s>>d>>w; p=(ArcNode*)malloc(sizeof(ArcNode)); q=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=d; q->adjvex=s; p->w=w; q->w=w; p->next=G.vertices[s].firstarc;/*p插入頂點(diǎn)s的鄰接表中*/ G.vertices[s].firstarc=p; q->next=G.vertices[d].firstarc; G.vertices[d].firstarc=q; }}算法運(yùn)行結(jié)果如下圖所示：算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第19頁。voidPrim(MGraphG,int算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第19頁。{ struct { intadjvex; intlowcost; }closedge[MAXVEX]; inti,j,k,min; for(i=1;i<=G.vexnum;i++) { closedge[i].lowcost=G.arcs[v][i]; closedge[i].adjvex=v; } closedge[v].lowcost=0; for(i=1;i<G.vexnum;i++) { min=MAXCOST; for(j=1;j<=G.vexnum;j++) if(closedge[j].lowcost!=0&&closedge[j].lowcost<min) { min=closedge[j].lowcost; k=j; } printf("(%c,%c,%d)",G.vexs[closedge[k].adjvex],G.vexs[k],min); closedge[k].lowcost=0; for(j=1;j<=G.vexnum;j++) if(closedge[j].lowcost!=0&&G.arcs[k][j]<closedge[j].lowcost) { closedge[j].lowcost=G.arcs[k][j]; closedge[j].adjvex=k; } }}voidKruskal(MGraphG){ intset[MAXVEX],i,j; intk=0,a=1,b=1,min=G.arcs[a][b]; for(i=0;i<G.vexnum;i++) set[i]=i; cout<<"最小生成樹的各條邊為："<<endl; while(k<G.vexnum-1) { for(i=0;i<G.vexnum;i++) for(j=i+1;j<G.vexnum;j++)算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第20頁。 if算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第20頁。 { min=G.arcs[i+1][j+1];//最小權(quán)值 a=i+1; b=j+1; } min=G.arcs[a][b]=MAXCOST;//刪除該邊，下次不再查找 if(set[a]!=set[b]) { cout<<G.vexs[a]<<"->"<<G.vexs[b]<<endl; k++; for(i=0;i<G.vexnum;i++) if(set[i]==set[b])//將頂點(diǎn)b所在集合并入頂點(diǎn)a集合中 set[i]=set[a]; } }}四、有向圖的基本操作與應(yīng)用有向圖的基本操作與應(yīng)用包括用鄰接矩陣和鄰接表創(chuàng)建有向圖以及以鄰接表為存儲結(jié)構(gòu)的拓?fù)渑判虻乃惴ā?.1、設(shè)計方案有向圖可用鄰接矩陣和鄰接表來創(chuàng)建，它與無向圖相比，其鄰接矩陣的定義為：A［i］［j］=用鄰接表創(chuàng)建有向圖時僅創(chuàng)建一個結(jié)點(diǎn)，其前驅(qū)為弧尾頂點(diǎn)，后記為弧頭頂點(diǎn)。用鄰接矩陣創(chuàng)建有向網(wǎng)的函數(shù)為CreatDG_M(MGraph&G)，用鄰接表創(chuàng)建有向網(wǎng)的函數(shù)為CreatDG_ALG(ALGraph&G)，其代碼參見頭文件DGraph.h。4.2、有向圖應(yīng)用的實(shí)現(xiàn)4.2.1拓?fù)渑判蚪o定一個AOE網(wǎng)，將其全部頂點(diǎn)按照活動的先后關(guān)系排成一個線性序列，使得若活動vi是活動vj的前驅(qū)，則序列中vi應(yīng)在vj的前面。具有這樣特性序列稱為拓?fù)溆行蛐蛄小?gòu)造拓?fù)湫蛄械倪^程稱為拓?fù)渑判?。求拓?fù)溆行蛐蛄械牟襟E為：(1)在AOE網(wǎng)中選一個沒有前驅(qū)的頂點(diǎn)，并輸出之。(2)從圖中刪除該頂點(diǎn)和所有以它為尾的弧。重復(fù)上述兩步，直到全部頂點(diǎn)已輸出，或者當(dāng)前圖中不存在無前驅(qū)的頂點(diǎn)為止。第一種情況說明拓?fù)渑判蛞呀?jīng)完成，第二種情況說明AVO網(wǎng)中存在回路。為了實(shí)現(xiàn)拓?fù)渑判颍捎靡环N特殊的鄰接表作AOE網(wǎng)的存儲結(jié)構(gòu)，即在頭節(jié)點(diǎn)中增加一個存儲相應(yīng)頂點(diǎn)的入度值域。網(wǎng)中沒有前驅(qū)的頂點(diǎn)即是鄰接表中入度為0的頂點(diǎn)，而每當(dāng)輸出一個頂點(diǎn)后，刪除以該頂點(diǎn)為尾的所有弧的操作通過將相應(yīng)弧頭頂點(diǎn)的入度值減1實(shí)現(xiàn)。為避免重復(fù)檢測入度為零的頂點(diǎn)，可另設(shè)一個棧暫存所有入度為零的頂點(diǎn)。拓?fù)渑判虻乃惴ㄈ缦拢篿ntTopoSort(ALGraphG){ inti,k,v,count=0;算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第21頁。算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第21頁。 ArcNode*p;for(i=1;i<=G.vexnum;i++) G.vertices[i].indegree=0; for(i=1;i<=G.vexnum;i++) { p=G.vertices[i].firstarc;while(p) { G.vertices[p->adjvex].indegree++; p=p->next; } } InitStack(s);for(inti=1;i<=G.vexnum;i++) if(!G.vertices[i].indegree) Push(s,i); while(!StackEmpty(s)) {Pop(s,v); cout<<G.vertices[v].data<<""; count++; for(p=G.vertices[v].firstarc;p;p=p->next) { k=p->adjvex; G.vertices[k].indegree--; if(!G.vertices[k].indegree) Push(s,k); } } if(count<G.vexnum) { cout<<"此有向圖有回路!"<<endl; return0; } else { cout<<endl<<"為一個拓?fù)湫蛄?"<<endl; return1; }算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第22頁。}算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第22頁。拓?fù)湫蛄杏脕頇z測AOE網(wǎng)中是否存在環(huán)以確定在一個流程圖中是否有有死循環(huán)從而減少工程的出錯率。4.2.2代碼實(shí)現(xiàn)*********************************DGraph.h**********************************#include"Sqstack.h"voidCreatDG_M(MGraph&G){inti,j,c;cout<<"請輸入頂點(diǎn)數(shù),邊數(shù):"; cin>>G.vexnum>>G.arcnum;printf("請輸入頂點(diǎn):"); for(i=1;i<=G.vexnum;i++) cin>>G.vexs[i]; for(i=1;i<=G.vexnum;i++) for(j=1;j<=G.vexnum;j++) G.arcs[i][j]=0; printf("請輸入邊:\n"); for(c=1;c<=G.arcnum;c++) { cin>>i>>j;G.arcs[i][j]=1; } cout<<"創(chuàng)建的鄰接矩陣為："<<endl; for(i=1;i<=G.vexnum;i++) { for(j=1;j<=G.vexnum;j++) cout<<G.arcs[i][j]<<""; cout<<endl;算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第23頁。算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第23頁。 cout<<"鄰接矩陣創(chuàng)建完畢"<<endl;}算法運(yùn)行結(jié)果如下圖所示：voidCreatDG_ALG(ALGraph&G){inti,s,d;ArcNode*p; cout<<"請輸入頂點(diǎn)數(shù),邊數(shù)："; cin>>G.vexnum>>G.arcnum;for(i=1;i<=G.vexnum;i++) { printf("第%d個結(jié)點(diǎn)信息:",i); cin>>G.vertices[i].data; G.vertices[i].firstarc=NULL; }for(i=1;i<=G.arcnum;i++){ printf("第%d條邊=>起點(diǎn)序號,終點(diǎn)序號:",i); cin>>s>>d; p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=d; p->next=G.vertices[s].firstarc;/*p插入頂點(diǎn)s的鄰接表中*/ G.vertices[s].firstarc=p; }算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第24頁。}算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第24頁。intTopoSort(ALGraphG){ inti,k,v,count=0; SqStacks; ArcNode*p;for(i=1;i<=G.vexnum;i++) G.vertices[i].indegree=0; for(i=1;i<=G.vexnum;i++) { p=G.vertices[i].firstarc;while(p) { G.vertices[p->adjvex].indegree++; p=p->next; } } InitStack(s);for(inti=1;i<=G.vexnum;i++) if(!G.vertices[i].indegree) Push(s,i); while(!StackEmpty(s)) {Pop(s,v); cout<<G.vertices[v].data<<""; count++; for(p=G.vertices[v].firstarc;p;p=p->next) { k=p->adjvex; G.vertices[k].indegree--;算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第25頁。 if算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第25頁。 Push(s,k); } } if(count<G.vexnum) { cout<<"此有向圖有回路!"<<endl; return0; } else { cout<<endl<<"為一個拓?fù)湫蛄?"<<endl; return1; }}五、有向網(wǎng)的基本操作與應(yīng)用有向網(wǎng)的基本操作與應(yīng)用包括創(chuàng)建有向網(wǎng)的鄰接矩陣和鄰接表，關(guān)鍵路徑，單源頂點(diǎn)最短路徑問題，每對頂點(diǎn)最短路徑問題。5.1、設(shè)計方案用與構(gòu)造無向圖相似的的方式可以構(gòu)造出鄰接矩陣和鄰接表。無向網(wǎng)的鄰接矩陣可定義為：A［i］［j］=其中，Wij表示邊(vi,vj)或弧<vi,vj>上的權(quán)值；∞表示一個計算機(jī)允許的、大于所有邊上權(quán)值的數(shù)。用鄰接表創(chuàng)建有向圖時僅創(chuàng)建一個結(jié)點(diǎn)，其前驅(qū)為弧尾頂點(diǎn)，后記為弧頭頂點(diǎn)。輸入時還應(yīng)加上弧上的權(quán)w。用鄰接矩陣創(chuàng)建有向網(wǎng)的函數(shù)為CreatDNG_M(MGraph&G)，用鄰接表創(chuàng)建有向網(wǎng)的函數(shù)為CreatDNG_ALG(ALGraph&G)，其代碼參見頭文件DNGraph.h。5.2、有向網(wǎng)應(yīng)用的實(shí)現(xiàn)5.2.1迪杰斯特拉算法從一個頂點(diǎn)到其余各頂點(diǎn)的最短路徑從某個源點(diǎn)到其余各頂點(diǎn)的最短路徑又稱為單源最短路徑。迪杰斯特拉提出了一個按路徑長度遞增的次序產(chǎn)生最短路徑的算法，又稱“貪心”算法。算法的基本思想是：把圖中的頂點(diǎn)分成兩個集合S和T，集合S中存放已確定最短路徑的頂點(diǎn)，集合T中存放尚未確定最短路徑的頂點(diǎn)。按最短路徑長度遞增的次序逐個將T集合中的頂點(diǎn)加入到S中，直到從源點(diǎn)出發(fā)可以到達(dá)的所有頂點(diǎn)都在S中為止。為實(shí)現(xiàn)算法，引入一個輔助結(jié)構(gòu)數(shù)組dist，用來存放源點(diǎn)v0到其他頂點(diǎn)的最短路徑長度及最短路徑。它有兩個域：存儲該頂點(diǎn)當(dāng)前最短路徑長度的length域和該路徑上的前驅(qū)頂點(diǎn)的pre域。Dis的初值為：若從v0到vi有弧，則dist[i].length為弧上的權(quán)值；否則為∞。而dist[i].pre=0(i!=0)。顯然長度為dist[i].length=min{dist[i].length，i=1,2,…,n-1}的路徑就是從v0出發(fā)的長度最短的一條最短路徑。此路徑為(v0,vj)。假設(shè)下一條最短路徑的終點(diǎn)為vk，那么該路徑或者是弧(v0,vk),或者是中間只經(jīng)過集合S中的頂點(diǎn)而到達(dá)頂點(diǎn)vk的路徑。因?yàn)榧偃舸寺窂缴铣齲之外還有頂點(diǎn)不在集合S中，說明存在一條終點(diǎn)不在S中而路徑長度比此路徑還短的路徑，這與我們按路徑長度遞增的順序產(chǎn)生最短路徑的前提相矛盾。因此，一般情況下，下一條長度次短的最短路徑的長度必是dist[j].length=min{dist[i].length|vi∈T}算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第26頁。另引入一個數(shù)組final，用來標(biāo)識頂點(diǎn)是否已經(jīng)確定最短路徑。Final[i]=1,表明vi的最短路徑已經(jīng)確定，即vi∈S。final[i]=0，表明vi∈T。當(dāng)從集合T中選取頂點(diǎn)vj加入到集合S中，需要更新頂點(diǎn)v0到集合T中任一頂點(diǎn)vk的最短路徑長度值。如果dist[j].length+G.arcs[j][k]<dist[k].length，則修改dist[k].length=dist[j].length+G.arcs[j][k],dist[j].pre=j。該算法的時間復(fù)雜度為O(n2)。算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第26頁。voidSinMiniPathD(MGraphG,intv){ struct { intlength; intpre; }dist[MAXVEX]; intfinal[MAXVEX]; inti,j,k,min; SqStacks; for(i=1;i<=G.vexnum;i++) { final[i]=0; dist[i].length=G.arcs[v][i]; if(dist[i].length<MAXCOST) dist[i].pre=v; else dist[i].pre=-1; } dist[v].pre=-1; final[v]=1; for(i=1;i<G.vexnum;i++) { min=MAXCOST; for(j=1;j<=G.vexnum;j++) if((!final[j])&&(dist[j].length<min)) { min=dist[j].length; k=j; } if(min<MAXCOST) { final[k]=1; for(j=1;j<=G.vexnum;j++) if(!final[j]&&(min+G.arcs[k][j]<dist[j].length)) { dist[j].length=min+G.arcs[k][j]; dist[j].pre=k;算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第27頁。算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第27頁。 else break; } } for(i=1;i<=G.vexnum;i++) { printf("%c->%c:%d\n",G.vexs[v],G.vexs[i],dist[i].length); InitStack(s); Push(s,i); j=dist[i].pre; while(j!=-1) { Push(s,j); j=dist[j].pre; } while(!StackEmpty(s)) { Pop(s,k); cout<<G.vexs[k]; } cout<<endl; }}算法運(yùn)行結(jié)果如下圖所示：算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第28頁。算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第28頁。 5.2.2弗洛伊德算法每對頂點(diǎn)之間的最短路徑假設(shè)求從頂點(diǎn)vi到vj的最短路徑，弗洛伊德算法的基本思想是：如果從vi到vj有弧，則從vi到vj存在一條長度為cost[i][j]的路徑，該路徑不一定是最短路徑，因?yàn)榭赡艽嬖趶膙i到vj且包含其他頂點(diǎn)為中間頂點(diǎn)的較短路徑。尚需進(jìn)行n次試探。首先考慮路徑(vi,v0,vj)是否存在(即判別弧(vi,v0)和(v0,vj)是否存在)。如果存在，則比較(vi,vj)和(vi,v0,vj)的路徑長度，取其中較短者為從vi到vj且中間頂點(diǎn)的序號不大于0的最短路徑。然后在路徑上再增加一個頂點(diǎn)，設(shè)(vi,…,v1)和(v1,…,vj)分別是當(dāng)前找到的從vi到v1和v1到vj中間頂點(diǎn)序號不大于0的最短路徑，比較(vi,…,v0，…,vj)和(vi,…,v1)+(v1,…,vj)的路徑長，取較短者作為從vi到vj且中間頂點(diǎn)的序號不大于1的最短路徑。再增加一個頂點(diǎn)v2，繼續(xù)進(jìn)行試探。若(vi,…,vk)和(vk,…,vj)分別是從vi到vk和從vk到vj的中間頂點(diǎn)的序號不大于k-1的最短路徑，則將(vi,…,vk，…,vj)和已經(jīng)得到的從vi到vj且中間頂點(diǎn)序號不大于k-1的最短路徑相比較，取其長度較短者作為從vi到vj的中間頂點(diǎn)的序號不大于k的最短路徑。這樣，在經(jīng)過n次比較后，最后求得的必是從vi到vj的最短路徑。弗洛伊德算法遞推地產(chǎn)生一個矩陣序列：D(-1),D(0),D(1),…，D(k),D(n-1)，其中D(k)[i][j]表示從頂點(diǎn)vi到vj且中間頂點(diǎn)序號不大于k的最短路徑的長度。D(n-1)[i][j]就是從vi到vj的最短路徑的長度。而產(chǎn)生D(-1),D(0),D(1),…，D(k),D(n-1)的過程就是逐步允許越來越多的頂點(diǎn)作為路徑的中間頂點(diǎn)，直到所有可能的頂點(diǎn)均作為中間頂點(diǎn)。設(shè)目前已求出D(k-1)[i][j]，求D(k)[i][j]有兩種情況：(1)如果從頂點(diǎn)vi到vj的最短路徑不經(jīng)過頂點(diǎn)vk，D(k)[i][j]=D(k-1)[i][j]。(2)如果從頂點(diǎn)vi到vj的最短路徑經(jīng)過頂點(diǎn)vk，D(k)[i][j]=D(k-1)[i][k]+D(k-1)[j][k]其中D(k-1)[i][k]和D(k-1)[j][k]分別表示從頂點(diǎn)vi到頂點(diǎn)vk和從頂點(diǎn)vk到頂點(diǎn)vj的中間頂點(diǎn)序號不大于k-1的最短路徑的長度。由此得到D(k)[i][j]的計算公式：D(-1)[i][j]=cost[i][j]算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第29頁。D(k)[i][j]=Min{D(k-1)[i][j]，D(k-1)[i][k]+D(k-1)[k][j]}0≤k≤n-1。采用鄰接矩陣存儲時，求任意兩頂點(diǎn)間的最短路徑的弗洛伊德算法如下：算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第29頁。voidDouMiniPathF(MGraphG){ intpath[MAXVEX][MAXVEX],D[MAXVEX][MAXVEX]; inti,j,k; for(i=1;i<=G.vexnum;i++) for(j=1;j<=G.vexnum;j++) { D[i][j]=G.arcs[i][j]; path[i][j]=-1; } for(k=1;k<=G.vexnum;k++) for(i=1;i<=G.vexnum;i++) for(j=1;j<=G.vexnum;j++) if(D[i][j]>D[i][k]+D[k][j]) { D[i][j]=D[i][k]+D[k][j]; path[i][j]=k; } displaypath(G,D,path);}voidppath(MGraphG,intpath[][MAXVEX],inti,intj){ intk; k=path[i][j]; if(k==-1)return; ppath(G,path,i,k); cout<<G.vexs[k]; ppath(G,path,k,j);}voiddisplaypath(MGraphG,intD[][MAXVEX],intpath[][MAXVEX]){ inti,j; for(i=1;i<=G.vexnum;i++) for(j=1;j<=G.vexnum;j++) if(D[i][j]==MAXCOST) printf("%c到%c沒有路徑可達(dá)",G.vexs[i],G.vexs[j]); else { printf("%c到%c的最短路徑為:%c",G.vexs[i],G.vexs[j],G.vexs[i]); ppath(G,path,i,j); printf("%c\n",G.vexs[j]); printf("最短路徑為長度為：%d\n",D[i][j]); }算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第30頁。}算法運(yùn)行結(jié)果如下圖所示：算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第30頁。 5.2.3關(guān)鍵路徑用頂點(diǎn)表示事件，用有向弧表示活動，弧上的權(quán)值表示活動持續(xù)的時間的有向網(wǎng)稱為AOE網(wǎng)，AOE網(wǎng)可用來估算工程的完成時間。由于AOE網(wǎng)中有些活動可以并行進(jìn)行，故完成工程的最短時間是從源點(diǎn)到匯點(diǎn)的最長路徑長度(這里的路徑長度指路徑上的各活動持續(xù)時間之和)。路徑長度最長的路徑稱為關(guān)鍵路徑。為了確定AOE網(wǎng)的關(guān)鍵路徑，首先定義下列幾個參數(shù)。1.事件的vj的最早發(fā)生時間ve[j]從源點(diǎn)v1到vj的最長路徑長度叫做事件vj的最早發(fā)生時間。這個時間決定了所有以vj為尾的弧表示的活動的最早開始時間?？捎孟旅孢f推公式計算ve[j]:ve[l]=0ve[j]=max{ve[i]+dut(<vi,vj>)}<vi,vj>∈T其中，T是所有以vj為頭的弧的集合，dut(<vi,vj>)為弧<vi,vj>上的權(quán)。2.事件的最遲發(fā)生時間vl[i]vl[i]是指在不推遲整個工期的前提下(即保證事件vn在ve(n)時刻發(fā)生的前提下),事件vi允許的最晚發(fā)生時間。等于ve(n)減去vi到vn的最長路徑長度。算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第31頁。vl[n]=ve[n]算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第31頁。vl[i]=min{vl[j]-dut(<vi,vj>)}<vi,vj>∈S其中S是所有以vi為尾的弧的集合。3.活動ak的最早開始時間ee[k]若活動ak是由弧<vi,vj>表示，只有事件vi發(fā)生了，活動ak才能開始。所以，活動ak的最早開始時間應(yīng)等于事件vi的最早發(fā)生時間。ee[k]=el[i]4.活動ak的最遲開始時間e1[k]在不推遲整個工程完成的前提下，活動ak最遲必須開始進(jìn)行的時間稱為活動ak的最遲開始時間。若由弧<vi,vj>表示活動ak，則ak的最遲開始時間等于事件vj的最遲發(fā)生時間vl[j]減去活動ak的持續(xù)時間。即：el[k]=vl[j]-dut(<vi,vj>)把el[k]=ee[k]的活動ak稱為關(guān)鍵活動。el[i]-ee[i]表示完成活動ak的時間余量，即在不延遲工期的前提下活動ak可以延遲的時間。求關(guān)鍵路徑的算法步驟為：(1)輸入e條弧<j,k>，建立AOE網(wǎng)的存儲結(jié)構(gòu)。(2)從源點(diǎn)v0出發(fā)，令ve[0]=0,按拓?fù)溆行蚯笃溆喔黜旤c(diǎn)的最早發(fā)生時間ve[i](1≤i≤n-1)。如果得到的拓?fù)溆行蛐蛄兄许旤c(diǎn)個數(shù)小于網(wǎng)中頂點(diǎn)數(shù)n，則說明網(wǎng)中存在環(huán)，不能求關(guān)鍵路徑，算法終止：否則執(zhí)行步驟(3).(3)從匯點(diǎn)vn出發(fā)，令vl[n-1]=ve[n-1],按逆拓?fù)溆行蚯笃溆喔黜旤c(diǎn)的最遲發(fā)生時間vl[i](n-2≥i≥2)。(4)根據(jù)各頂點(diǎn)的ve和vl值，求每條弧s的最早開始時間ee(s)和最遲開始時間el(s)。若某條弧滿足條件ee(s)=el(s),則為關(guān)鍵活動。用頭結(jié)點(diǎn)中增加一個存儲相應(yīng)頂點(diǎn)的入度值域的特殊鄰接表作AOE網(wǎng)的存儲結(jié)構(gòu)，求關(guān)鍵路徑的算法如下：intve[MAXVEX],vl[MAXVEX];inttporder(ALGraphG,SqStack*T){ SqStacks; inti,v,k,count=0; ArcNode*p; InitStack(s); for(i=1;i<=G.vexnum;i++) G.vertices[i].indegree=0; for(i=1;i<=G.vexnum;i++) { p=G.vertices[i].firstarc;while(p) { G.vertices[p->adjvex].indegree++; p=p->next; } } for(i=1;i<=G.vexnum;i++) { ve[i]=0;算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第32頁。 if(!G.vertices[i].indegree)算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計方案全文共41頁，當(dāng)前為第32頁。 Push(s,i); } while(!StackEmpty(s)) { Pop(s,v); count++; Push(T,v); for(p=G.vertices[v].firstarc;p;p=p->next) { k=p->adjvex; G.vertices[k].indegree--; if(!G.vertices[k].indegree) Push(s,k); if(ve[v]+p->w>ve[k]) ve[k]=ve[v]+p->w; } } returncount;}v