數(shù)據(jù)結(jié)構(gòu)課程設計最短路徑

1、數(shù)據(jù)結(jié)構(gòu)課程設計題目名稱：最短路徑計算機科學與技術學院一、需求分析(1)題目：最短路徑實現(xiàn)圖的輸入，選擇合適的結(jié)構(gòu)表示圖，在此基礎上實現(xiàn)求解最短路徑的算法，可以從任意一點求最短路徑，學生必須準備多組測試數(shù)據(jù)，并設計清晰易懂的輸入輸出界面，要求：如何用多種數(shù)據(jù)結(jié)構(gòu)來求解問題。同時要求實現(xiàn)對應數(shù)據(jù)結(jié)構(gòu)的所有基本操作。(2)程序的輸入與輸出：要求用多種數(shù)據(jù)結(jié)構(gòu)求解問題，也就是要用鄰接表與鄰接矩陣實現(xiàn)最短路徑的算法，需要有多組輸入輸出，(a)輸入的形式和輸入值的范圍：輸入的形式為整型1,先輸入共需要創(chuàng)建幾次圖2,再分別輸入邊數(shù)和頂點數(shù)(范圍：1-100)3,輸入1和2選擇是否為有向圖圖(1為有向，2為

2、無向)4 .對應每條邊輸入起點和終點下標，以及對這條邊的權值(最大的權值為100)。5 .輸入在鄰接表的基礎上輸入深度與廣度優(yōu)先搜索的起點6 .我們輸入求各種最短路徑起點和終點(b)輸出的形式；1 .輸出所建立的鄰接表(表結(jié)點后面的括號是頭結(jié)點與表結(jié)點的權值)2 .輸出DF陰口BFS的結(jié)果3,輸出該圖不帶權值的最短路徑與路徑4 .接下來輸入起點和終點，求帶權值的最短路徑也就是Dijstra算法，輸出長度并給出路徑5 .前面都是用鄰接表實現(xiàn)的各種算法，接下來的Floyd算法就用矩陣實現(xiàn)，于是直接鄰接表轉(zhuǎn)矩陣輸出6,用Floyd算法求出圖的多源最短路徑，給出起點終點輸出最短路徑長度，接著便到了第二

3、次創(chuàng)建圖，直至循環(huán)結(jié)束。(3)程序的功能：求給出帶權圖的任意兩點，輸出最短路徑長度并給出其最短路徑所經(jīng)過的頂點。在實際應用中可以將交通網(wǎng)絡化成帶權的圖，圖中頂點表示城市，邊代表城市之間的公路，邊上的權值表示公路的長度。這樣可以發(fā)現(xiàn)兩個地方之間有無公路可連，在幾條公路可通的情況下，可以找到那條路徑最短。也就是現(xiàn)在地圖app中的功能。（4）測試數(shù)據(jù)：包括正確的輸入及其輸出結(jié)果和含有錯誤的輸入及其輸出結(jié)果。F:報告*最短路徑（D與F）.exe八溷僉宣向M2.無向;2l,u2,weight：1l,u2,weiglit：2l,u2,ueight：3l,u2,weight：1l,u2,ueight：5l,

4、u2,weight：5立的鄰接表為=31184，入：礎爨，1到4的最短路徑為：11的長二堪為權路徑帶短路善取短2,的最NII4的1至4uH短路徑信息:14：254最軍路徑信息用鄰接表與Di出tra算法）度為二61234100210010011002100310010010010031001100100100100110081001100100810041001001001004100入Ulib：14在有向圖中輸入錯誤的數(shù)據(jù)（頂點與頂點方向相反），會輸出逆向信息:、概要設計1 .主程序流程(a)主程序首先多組輸入一個n,在n不為0的前提下循環(huán)執(zhí)行(b)調(diào)用BuildGraph()函數(shù)，創(chuàng)建一個圖

5、并以鄰接表的形式存儲(c)BuildGraph()函數(shù)輸入頂點、邊數(shù)調(diào)用CreateGraph(Nv)函數(shù)，初始化一個有Nv個頂點但沒有邊的圖，再根據(jù)結(jié)構(gòu)體Edge輸入每個邊的信息，調(diào)用InsertEdge(Graph,E,c);函數(shù)將每條邊插入到僅僅初始化的圖中，完成一個圖的建立，并返回一個鄰接表類型的結(jié)構(gòu)體(d)主函數(shù)接到返回來的鄰接表結(jié)構(gòu)體，調(diào)用outL()函數(shù)，輸出這個鄰接表(e)輸入起點，調(diào)用DFS(Graph,v1,1);函數(shù)進行遞歸求解深度優(yōu)先搜索并直接輸出(f)輸入起點，調(diào)用BFS(Graph,v1);函數(shù)，求解廣度優(yōu)先搜索并直接輸出(g)輸入起點、終點，調(diào)用Unweighte

6、d(Graph,v1);函數(shù)求得起點到每個點的最短路徑，再用distv2輸出。(h)如果distv2大于0證明v1可以到達v2,調(diào)用outpath(v2)輸出路徑(i)輸入起點、終點，調(diào)用Dijkstra(Graph,v1);函數(shù)求得起點到每個點的最短路徑，再用distv2輸出。(j)如果distv2小于定義的INF,證明v1可以到達v2,再次調(diào)用outpath(v2)輸出路徑(k)用MGraphgra;創(chuàng)建一個鄰接矩陣之后，調(diào)用transform(Graph);進行鄰接表與鄰接矩陣的轉(zhuǎn)換(l)outM(gra);函數(shù)，以二維數(shù)組的形式輸出鄰接矩陣(mj)調(diào)用Floyd(gra,D,pa);函

7、數(shù)求得多源最短路徑，存儲在D這個二維數(shù)組中，給出起點，終點直接輸出。2 .所有用到的抽象數(shù)據(jù)類型(1)邊的定義(a)表示邊的起點和終點(b)邊的權重(2)鄰接表的表結(jié)點的定義(a)鄰接點下標(b)邊權重(c)指向下一個鄰接點的指針(3)鄰接表的頂點表頭結(jié)點的定義(a)邊表頭指針(b)存頂點的數(shù)據(jù)(c)鄰接表類型的AdjList存儲鄰接表的頭結(jié)點(4)鄰接表對應圖結(jié)點的定義(a)頂點數(shù)(b)邊數(shù)(c)鄰接表(5)鄰接矩陣的定義(a)頂點數(shù)(b)邊數(shù)(c)二維數(shù)組形式的鄰接矩陣(6) BFS存數(shù)據(jù)的隊列(a)隊頭front標記(b)隊頭rear標記(c)存數(shù)據(jù)的數(shù)組(7)用于輸出最短路徑的棧(a)

8、棧頂top標記(b)存數(shù)據(jù)的數(shù)組3.設計程序的各個模塊(即函數(shù))功能及設計思想(1) CreateGraph(intVertexNum)函數(shù)功能：初始化一個有VertexNum個頂點但沒有邊的圖設計思想：(a)根據(jù)鄰接表結(jié)構(gòu)體分配一塊空間(b)初始化圖的頂點數(shù)和邊數(shù)(c)初始化鄰接表頭指針(d)注意：這里默認頂點編號從1開始，到Graph-Nv(e)初始化dist口與path口數(shù)組(2) InsertEdge(LGraphGraph,EdgeE,intc)函數(shù)功能：在建立的圖中插入邊設計思想：(a)輸入v1,v2,建立一個v2的新的鄰接點(b)將V2插入V1的表頭，用c做標志位，在調(diào)用函數(shù)時輸

9、入(c)若c=2,表示圖為無向圖，還要插入邊(d)接著為V1建立新的鄰接點，將V1插入V2的表頭(3) BuildGraph()函數(shù)功能：輸入頂點和邊數(shù)，定義有向圖和無向圖，建立圖，并返回鄰接表類型的指針設計思想：(a)讀入頂點個數(shù)，調(diào)用CreateGraph(Nv)初始化有Nv個頂點但沒有邊的圖(b)讀入邊數(shù)，定義有向、無向，如果有邊，建立邊結(jié)點，讀入邊，格式為起點終點權重，插入鄰接表(c)注意：如果權重不是整型，Weight的讀入格式要改(4) clrv(LGraphg)函數(shù)功能：初始化圖的訪問數(shù)組Visited為0設計思想：重置被DFS口BFS修改過的visited數(shù)組(5) DFS(L

10、GraphGraph,VertexV,intx)函數(shù)功能：以V為出發(fā)點對鄰接表存儲的圖Graph進行DFS索設計思想：|(a)首先訪問出發(fā)點v,并將其標記為已訪問過；(b)然后依次從v出發(fā)搜索v的每個鄰接點w。若w未曾訪問過，則以w為新的出發(fā)點繼續(xù)進行深度優(yōu)先遍歷，直至圖中所有和源點v有路徑相通的頂點(亦稱為從源點可達的頂點)均已被訪問為止。|(c)若此時圖中仍有未訪問的頂點，則另選一個尚未訪問的頂點作為新的源點重復上述過程，直至圖中所有頂點均已被訪問為止。(d)也就是訪問頂點v,從v的未被訪問的鄰接點中選取一個頂點w,從w出發(fā)進行深度優(yōu)先遍歷，重復上述兩步，直至圖中所有和v有路徑相通的頂點都

11、被訪問到。(6) CreateQueue()函數(shù)功能：初始化一個隊列設計思想：(a)隊列的front與rear分別置-1(b)為數(shù)組分配空間r(7) AddQ(QueueQ,VertexS)函數(shù)功能：向隊列中添加元素設計思想：(a)將rear位置挪一位(b)在rear這位加入一個數(shù)(8) DeleteQ(QueueQ)函數(shù)功能：隊列中刪除一個元素，并返回設計思想：(a)從隊列的頭出隊(b)也就是front位置加一(c)將front這位的數(shù)據(jù)彈出IsEmpty(QueueQ)函數(shù)功能：判斷隊列是否為空設計思想：(a)判斷front的位置與rear是否相等(10) Unweighted(LGrap

12、hGraph,VertexS)函數(shù)功能：輸入兩點，求對應不帶權值的圖的最短路徑設計思想：(a)按照遞增(非遞減)的順序找出各個頂點的最短路，類似于BFS(b)先創(chuàng)建空隊列，MaxSize為外部定義的常數(shù)(c)初始化源點.distS=0(d)對V的每個鄰接點W-AdjV(e)若W-AdjV未被訪問過，W-AdjV到S的距離更新(f)將V記錄在S到W-AdjV的路徑上(11) BFS(LGraphGraph,VertexV)函數(shù)功能：向隊列中添加元素設計思想：(a)頂點v入隊列。(b)當隊列非空時則繼續(xù)執(zhí)行，否則算法結(jié)束。(c)出隊列取得隊頭頂點v;訪問頂點v并標記頂點v已被訪問。(d)查找頂點v

13、的第一個鄰接頂點first。(e)若v的鄰接頂點first未被訪問過的，則first入隊列。(f)繼續(xù)查找頂點v的另一個新的鄰接頂點first,轉(zhuǎn)到步驟(e)。(g)直到頂點v的所有未被訪問過的鄰接點處理完。轉(zhuǎn)到步驟(f)。(12) clr(LGraphGraph)函數(shù)功能：重置dist口數(shù)組與path口數(shù)組設計思想：(a)重置最短路徑的舉例與路徑(13) FindMinDist(LGraphGraph,intcollected)函數(shù)功能：傳入一個dist中沒有被收錄(collected對應為-1)的數(shù)設計思想：(a)V從1到頂點最大的下標-(b)若V未被收錄，且distV更小(c)更新最小距

14、離更新對應頂點(d)若找到最小dist,返回對應的頂點下標(e)若這樣的頂點不存在，返回錯誤標記一(14) Dijkstra(LGraphGraph,VertexS)函數(shù)功能：求出輸入VertexS的單源最短路徑設計思想：(a)Dijkstra算法開始采用的是一種貪心的策略，聲明一個數(shù)組dist來保存源點到各個頂點的最短距離和一個保存已經(jīng)找到了最短路徑的頂點的集合T(b)初始時，原點s的路徑權重被賦為0(diss=0)(c)若對于頂點s存在能直接到達的邊(s,m),則把dism設為w(s,m),同時把所有其他(s不能直接到達的)頂點的路徑長度設為無窮大(d)初始時，集合T只有頂點So(e)從d

15、is數(shù)組選擇最小值(貪心)，則該值就是源點s到該值對應的頂點的最短路徑，并且把該點加入到T中，OK此時完成一個頂點，(f)我們需要看看新加入的頂點是否可以到達其他頂點并且看看通過該頂點到達其他點的路徑長度是否比源點直接到達短，如果是，那么就替換這些頂點在dis中的值。(g)然后，又從dis中找出最小值，重復上述動作，直到T中包含了圖的所有頂點。(15) transform(LGrapha)函數(shù)功能：鄰接矩陣與鄰接表轉(zhuǎn)換設計思想：(a)分析鄰接矩陣與鄰接表的異同(b)鄰接表有一個頭結(jié)點數(shù)組，每一個對應一串鏈表，跟著的是每一個頂點與鄰接點相連(c)鄰接矩陣則是一個二維數(shù)組，兩點有邊值為權重，沒有則

16、初始化為無窮(d)先初始化一個空的二維數(shù)組(e)再對應鄰接表每個頭結(jié)點遍歷其鏈表，將其值對應的加入到鄰接矩陣中(16) outM(MGraphgra)函數(shù)功能：傳入鄰接矩陣結(jié)構(gòu)體，輸出鄰接矩陣設計思想：(a)相當于輸出一個二維數(shù)組(17) outL(LGraphGraph)函數(shù)功能：傳入鄰接表結(jié)構(gòu)體，輸出鄰接表設計思想：(a)第一個循環(huán)遍歷每個頭結(jié)點(b)在第一個循環(huán)中表結(jié)點的地址不為空則輸出(還要輸出權值)(18) Floyd(MGraphGraph,WeightTypeDmaxVnum,VertexpathmaxVnum)函數(shù)功能：Floyd算法求出多源最短路徑設計思想：(a)通過Floy

17、d計算圖G=(V,E)中各個頂點的最短路徑時，需要引入兩個矩陣，矩陣S中的元素aij表示頂點i(第i個頂點)到頂點j(第j個頂點)的距離。矩陣P中的元素bij,表示頂點i到頂點j經(jīng)過了bij記錄的值所表示的頂點。(b)假設圖G中頂點個數(shù)為N,則需要對矩陣D和矩陣P進行N次更新。(c)初始時，矩陣D中頂點aij的距離為頂點i到頂點j的權值(d)如果i和j不相鄰，則aij=巴矩陣P的值為頂點bij的j的值(e),對矩陣D進行N次更新(f)第1次更新時，如果aij的距離”“ai0+a0j(ai0+a0j表示i與j之間經(jīng)過第1個頂點的距離”)，則更新aij為ai0+a0j，更新bij=bi0。(g)同

18、理，第k次更新時，如果aij的距離”“aik-1+ak-1j，則更新aij為aik-1+ak-1j，bij=bik-1。更新N次之后，求出最短路徑(19) StrackcreateStr()函數(shù)功能：創(chuàng)建一個棧設計思想：(a)分配空間，top=-1(20) push(Strackptr,intv)函數(shù)功能：向棧中添加元素設計思想：(a)top加一(b)對應位置存為v(21) pop(Strackptr)函數(shù)功能：出棧設計思想：(a)先將棧頂元素彈出，top減一(22) sIsEmpty(Strackptr)函數(shù)功能：判斷棧是否為空1設計思想：(a)若果top=-1,為空，否則返回0(23) o

19、utpath(intv)函數(shù)功能：輸出最短路徑設計思想：(a)由于存最短路徑的path數(shù)組每位存的只是上一個頂點，所以每次查找都會不斷地找到每個頂點的上級，直至pathv=-1,會形成一個方向的路徑，就要利用堆棧后進先出的特點輸出。(b)在path存的數(shù)據(jù)不為-1時，將他們?nèi)繅喝霔Ｖ校賹⑺麄內(nèi)枯敵鋈?、詳細設計1 .程序流程圖2 .數(shù)據(jù)類型的實現(xiàn)(1)邊的定義typedefstructENode*PtrToENode;structENodeVertexV1,V2;/*有向邊*/WeightTypeWeight;/*權重*/);typedefPtrToENodeEdge;(2)鄰接表的表結(jié)點

20、的定義typedefstructAdjVNode*PtrToAdjVNode;structAdjVNodeVertexAdjV;/*鄰接點下標*/WeightTypeWeight;/*邊權重*/PtrToAdjVNodeNext;/*指向下一個鄰接點的指針*/);typedefPtrToAdjVNodeANode;(3)鄰接表的頂點表頭結(jié)點的定義typedefstructVnodePtrToAdjVNodeFirstEdge;/*邊表頭指針*/DataTypeData;/*存頂點的數(shù)據(jù)*/*注意：很多情況下，頂點無數(shù)據(jù)，此時Data可以不用出現(xiàn)*/AdjListmaxVnum;/*AdjLis

21、t是鄰接表類型*/(4)鄰接表對應圖結(jié)點的定義typedefstructGNode*PtrToGNode;structGNodeintNv;/*頂點數(shù)*/intNe;/*邊數(shù)*/AdjListG;/*鄰接表*/;typedefPtrToGNodeLGraph;/*以鄰接表方式存儲的圖類型*/(5)鄰接矩陣的定義typedefstructMNode*PtrToMNode;structMNodeintNv;/*頂點數(shù)*/intNe;/*邊數(shù)*/WeightTypeGmaxVnummaxVnum;/*鄰接矩陣*/;typedefPtrToMNodeMGraph;/*以鄰接矩陣存儲的圖類型*/(6)B

22、FS存數(shù)據(jù)的隊列typedefstructQue*Queue;structQueintfront;intrear;intdatalistmaxVnum;(7)用于輸出最短路徑的棧typedefstructStr*Strack;structStrinttop;intStrlistmaxVnum;)；3 .重要函數(shù)的偽代碼(1)無權圖的單源最短路徑voidUnweighted(Vertexs)Enqueue(s,q);while(隊列不空)v=Deququ(q);for(v的每個鄰接點w)if(w沒被訪問過)更新w的距離；pathw=v;Enqueue(w,q);)(2) 有權圖的單源最短路徑vo

23、idDijkstra(Vertexs)while(1)v=未收錄頂點中的dist最小者；if(這樣的v不存在)break;collectedv=true;for(v的每個鄰接點w)if(w沒被收錄)if(distv+v到w的權值522=313=424=535=6416=5輸入賽度優(yōu)先搜索的起點DFS結(jié)果為56432輸入廣度優(yōu)先搜索的起點BFS結(jié)果為52643蒯木凡2譽不置收值電暈短路徑信息4盛麒翻瞭吸4能釐耀疆然徑信息用鄰接表與其算法人勺基短路徑為：12鄰接表轉(zhuǎn)換為矩陣輸出:100221001003100100110010010010031001100100100100110081001100

24、100810041001001001004100額入uj2。豳出最短路徑長度用鄰接矩陣與Floyd算法：悠丐1到4的感熊咨徑長度為:6七、測試情況測試成功，程序正常進行結(jié)果正確。1 .對于第一次循環(huán)（無向圖）：DFS:15423BFS:152643不帶權的1到4最短路徑為：154長度為：2帶權的1到4最短路徑為：1234長度為：6Floyd算法中求最短路徑也為62 .對于第二次循環(huán)（有向圖）：由于V6與其他頂點反向，所以DFS:15432正確BFS:15243正確不帶權的1到6最短路徑為：無因為1到6逆向帶權的1到4最短路徑為：無因為1到6逆向而在Floyd算法中求1到4最短路徑長度還是：6正

25、確附錄（源代碼）：#include#include#include#defineINF100#defineERROR200# defineflase0最大頂點數(shù)設為100*/用頂點下標表示頂點，為整型*/*圖的鄰接邊的權值設為整型*/頂點存儲的數(shù)據(jù)類型設為字符型*/# definetrue1# definemaxVnum100/*typedefintVertex;/*表表示法*/typedefintWeightType;/*typedefcharDataType;/*usingnamespacestd;intdistmaxVnum;intpathmaxVnum;intcollectmaxVnu

26、m;/BFS存數(shù)據(jù)的隊列typedefstructQue*Queue;structQueintfront;intrear;intdatalistmaxVnum;/輸出路徑的棧typedefstructStr*Strack;structStrinttop;intStrlistmaxVnum;/*邊的定義*/typedefstructENode*PtrToENode;structENodeVertexV1,V2;/*有向邊*/WeightTypeWeight;/*權重*/;typedefPtrToENodeEdge;/*鄰接點的定義*/typedefstructAdjVNode*PtrToAdjV

27、Node;structAdjVNodeVertexAdjV;/*WeightTypeWeight;/*PtrToAdjVNodeNext;/*;typedefPtrToAdjVNodeANode;鄰接點下標*/邊權重*/指向下一個鄰接點的指針*/*頂點表頭結(jié)點的定義*/typedefstructVnodePtrToAdjVNodeFirstEdge;/*DataTypeData;/*邊表頭指針*/存頂點的數(shù)據(jù)*/*注意：很多情況下，頂點無數(shù)據(jù)，此時Data可以不用出現(xiàn)*/AdjListmaxVnum;/*AdjList是鄰接表類型*/*圖結(jié)點的定義*/typedefstructGNode*Pt

28、rToGNode;structGNodeintNv;/*頂點數(shù)*/intNe;/*邊數(shù)*/AdjListG;/*鄰接表*/;typedefPtrToGNodeLGraph;/*以鄰接表方式存儲的圖類型*/typedefstructMNode*PtrToMNode;structMNodeintNv;/*頂點數(shù)*/intNe;/*邊數(shù)*/WeightTypeGmaxVnummaxVnum;/*鄰接矩陣*/;typedefPtrToMNodeMGraph;/*以鄰接矩陣存儲的圖類型*/LGraphCreateGraph(intVertexNum)/*初始化一個有VertexNum個頂點但沒有邊的圖*

29、/VertexV;LGraphGraph;Graph=(LGraph)malloc(sizeof(structGNode);/*建立圖*/Graph-Nv=VertexNum;Graph-Ne=0;/*初始化鄰接表頭指針*/*注意：這里默認頂點編號從1開始，至UGraph-Nv*/for(V=1;VNv;V+)Graph-GV.FirstEdge=NULL;distV=-1;pathV=-1;returnGraph;voidInsertEdge(LGraphGraph,EdgeE,intc)PtrToAdjVNodeNewNode;/*插入邊*/*為V2建立新的鄰接點*/NewNode=(Pt

30、rToAdjVNode)malloc(sizeof(structAdjVNode);NewNode-AdjV=E-V2;NewNode-Weight=E-Weight;/*將V2插入V1的表頭*/NewNode-Next=Graph-GE-V1.FirstEdge;Graph-GE-V1.FirstEdge=NewNode;if(c=2)/*若是無向圖，還要插入邊*/*為V1建立新的鄰接點*/NewNode=(PtrToAdjVNode)malloc(sizeof(structAdjVNode);NewNode-AdjV=E-V1;NewNode-Weight=E-Weight;/*將V1插入

31、V2的表頭*/NewNode-Next=Graph-GE-V2.FirstEdge;Graph-GE-V2.FirstEdge=NewNode;LGraphBuildGraph()LGraphGraph;EdgeE;VertexV;intNv,i;cout輸入圖的頂點個數(shù)：；scanf(%d,&Nv);/*讀入頂點個數(shù)*/Graph=CreateGraph(Nv);/*初始化有Nv個頂點但沒有邊的圖*/coutNe);/*讀入邊數(shù)*/intc;coutc;if(Graph-Ne!=0)/*如果有邊*/E=(Edge)malloc(sizeof(structENode);/*建立邊結(jié)點*/*讀入

32、邊，格式為起點終點權重*/for(i=0;iNe;i+)printf(v1,v2,weight:);scanf(%d%d%d,&E-V1,&E-V2,&E-Weight);/*注意：如果權重不是整型，Weight的讀入格式要改*/InsertEdge(Graph,E,c);returnGraph;intVisitedmaxVnum;voidclrv(LGraphg)inti;for(i=1;iNv;i+)Visitedi=0;voidDFS(LGraphGraph,VertexV,intx)/*以V為出發(fā)點對鄰接表存儲的圖Graph進彳tDFS搜索*/PtrToAdjVNodeW;if(x=1

33、)clrv(Graph);x+;coutVGV.FirstEdge;W!=NULL;W=W-Next)/*對V的每個鄰接點W-AdjV*/if(!VisitedW-AdjV)/*若W-AdjV未被訪問*/DFS(Graph,W-AdjV,x);/*則遞歸訪問之*/*鄰接表存儲-無權圖的單源最短路算法*/QueueCreateQueue()QueueQ;Q=(Queue)malloc(sizeof(structQue);Q-front=-1;Q-rear=-1;return(Q);voidAddQ(QueueQ,VertexS)Q-rear+;Q-datalistQ-rear=S;intDele

34、teQ(QueueQ)Q-front+;return(Q-datalistQ-front);intIsEmpty(QueueQ)if(Q-front=Q-rear)return1;elsereturn0;/*dist和path口全部初始化為-1*/voidUnweighted(LGraphGraph,VertexS)QueueQ;VertexV;PtrToAdjVNodeW;Q=CreateQueue();/*創(chuàng)建空隊列，MaxSize為外部定義的常數(shù)*/distS=0;/*初始化源點*/AddQ(Q,S);while(!IsEmpty(Q)V=DeleteQ(Q);for(W=Graph-G

35、V.FirstEdge;W!=NULL;W=W-Next)/*對V的每個鄰接點W-AdjV*/if(distW-AdjV=-1)/*若W-AdjV未被訪問過*/distW-AdjV=distV+1;/*W-AdjV到S的距離更新*/pathW-AdjV=V;/*將V記錄在S到W-AdjV的路徑上*/AddQ(Q,W-AdjV);/*while結(jié)束*/voidBFS(LGraphGraph,VertexV)PtrToAdjVNodeW;QueueQ;Q=CreateQueue();clrv(Graph);AddQ(Q,V);VisitedV=true;while(!IsEmpty(Q)V=Del

36、eteQ(Q);coutVGV.FirstEdge;W!=NULL;W=W-Next)if(VisitedW-AdjV=false)AddQ(Q,W-AdjV);VisitedW-AdjV=true;voidclr(LGraphGraph)inti,j;for(i=1;iNv;i+)disti=INF;pathi=-1;/鄰接表存儲-有權圖的單源最短路算法VertexFindMinDist(LGraphGraph,intcollected)/*返回未被收錄頂點中dist最小者*/VertexMinV,V;intMinDist=INF;for(V=1;VNv;V+)if(collectedV=f

37、alse&distVMinDist)/*若V未被收錄，且distV更小*/MinDist=distV;/*更新最小距離*/MinV=V;/*更新對應頂點*/if(MinDistGS.FirstEdge;for(W=Graph-GS.FirstEdge;W!=NULL;W=W-Next)distW-AdjV=W-Weight;pathW-AdjV=S;)for(V=1;VNv;V+)collectedV=false;/*先將起點收入集合*/distS=0;collected=true;while(true)/*V=未被收錄頂點中dist最小者*/V=FindMinDist(Graph,colle

38、cted);if(V=ERROR)/*break;/*若這本的V不存在*/算法結(jié)束*/collectedV=true;/*收錄V*/*對V若W-AdjV未被訪問過*/for(W=Graph-GV.FirstEdge;W!=NULL;W=W-Next)的每個鄰接點W-AdjV*/if(collectedW-AdjV=false)/*if(distV+W-WeightAdjV)distW-AdjV=distV+W-Weight;pathW-AdjV=V;)結(jié)束*/)/*whileMGraphtransform(LGrapha)/鄰接矩陣與鄰接表轉(zhuǎn)換(MGraphb;inti,j;ANodep;b=

39、(MGraph)malloc(sizeof(structMNode);b-Nv=a-Nv;b-Ne=a-Ne;for(i=1;iNv;i+)for(j=1;jNv;j+)b-Gij=INF;for(i=1;iNv;i+)(p=(ANode)malloc(sizeof(ANode);p=a-Gi.FirstEdge;while(p!=NULL)(b-Gip-AdjV=p-Weight;p=p-Next;)return(b);)voidoutM(MGraphgra)inti,j;cout鄰接表轉(zhuǎn)換為矩陣輸出：endl;for(i=1;iNv;i+)for(j=1;jNv;j+)printf(%5d,gra-Gij);printf(n);)voidoutL(LGraphGraph)inti,j,k,n;PtrToAdjVNodep;cout所建立的鄰接表為：；coutendl;for(i=1;iNv;i+)couti;p=Graph-Gi.FirstEdge;if(p=NULL)coutNULLNext!=NULL)cout