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

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

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

3、長度，接著便到了第二次創(chuàng)建圖，直至循環(huán)結(jié)束。（3） 程序的功能:求給出帶權(quán)圖的任意兩點，輸出最短路徑長度并給出其最短路徑所經(jīng)過的頂點。在實際應(yīng)用中可以將交通網(wǎng)絡(luò)化成帶權(quán)的圖，圖中頂點表示城市，邊代表城市之間的公路，邊上的權(quán)值表示公路的長度。這樣可以發(fā)現(xiàn)兩個地方之間有無公路可連，在幾條公路可通的情況下，可以找到那條路徑最短。也就是現(xiàn)在地圖app中的功能。（4）測試數(shù)據(jù):包括正確的輸入及其輸出結(jié)果和含有錯誤的輸入及其輸出結(jié)果。 在有向圖中輸入錯誤的數(shù)據(jù)（頂點與頂點方向相反），會輸出逆向信息。2、 概要設(shè)計1.主程序流程（a） 主程序首先多組輸入一個n，在n不為0的前提下循環(huán)執(zhí)行（b） 調(diào)用 Bui

4、ldGraph()函數(shù)，創(chuàng)建一個圖并以鄰接表的形式存儲（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)先搜索并直

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

6、二維數(shù)組的形式輸出鄰接矩陣（m） 調(diào)用Floyd(gra,D,pa);函數(shù)求得多源最短路徑，存儲在D這個二維數(shù)組中，給出起點，終點直接輸出。2.所有用到的抽象數(shù)據(jù)類型（1）邊的定義 （a）表示邊的起點和終點 （b）邊的權(quán)重 （2） 鄰接表的表結(jié)點的定義 （a）鄰接點下標(biāo) （b）邊權(quán)重 （c）指向下一個鄰接點的指針 （3）鄰接表的頂點表頭結(jié)點的定義 （a）邊表頭指針 （b）存頂點的數(shù)據(jù) （c）鄰接表類型的 AdjList存儲鄰接表的頭結(jié)點（4） 鄰接表對應(yīng)圖結(jié)點的定義 （a）頂點數(shù) （b）邊數(shù) （c）鄰接表 （5）鄰接矩陣的定義 （a） 頂點數(shù) （b） 邊數(shù) （c）二維數(shù)組形式的鄰接矩陣 （6）

7、 BFS存數(shù)據(jù)的隊列 （a）隊頭 front標(biāo)記 （b）隊頭 rear標(biāo)記 （c）存數(shù)據(jù)的數(shù)組（7）用于輸出最短路徑的棧 （a）棧頂top標(biāo)記 （b）存數(shù)據(jù)的數(shù)組3.設(shè)計程序的各個模塊（即函數(shù)）功能及設(shè)計思想（1） CreateGraph( int VertexNum )函數(shù)功能：初始化一個有VertexNum個頂點但沒有邊的圖 設(shè)計思想：（a）根據(jù)鄰接表結(jié)構(gòu)體分配一塊空間（b）初始化圖的頂點數(shù)和邊數(shù)（c）初始化鄰接表頭指針（d）注意：這里默認(rèn)頂點編號從1開始，到Graph->Nv（e）初始化dist與path數(shù)組（2） InsertEdge( LGraph Graph, Edge E,

8、 int c )函數(shù)功能：在建立的圖中插入邊設(shè)計思想：（a）輸入v1，v2，建立一個v2的新的鄰接點（b）將V2插入V1的表頭，用c做標(biāo)志位，在調(diào)用函數(shù)時輸入（c）若c=2，表示圖為無向圖，還要插入邊 <V2, V1>（d）接著為V1建立新的鄰接點，將V1插入V2的表頭 （3） BuildGraph()函數(shù)功能：輸入頂點和邊數(shù)，定義有向圖和無向圖，建立圖，并返回鄰接表類型的指針設(shè)計思想：（a）讀入頂點個數(shù)，調(diào)用CreateGraph(Nv)初始化有Nv個頂點但沒有邊的圖（b）讀入邊數(shù)，定義有向、無向，如果有邊，建立邊結(jié)點，讀入邊，格式為"起點 終點 權(quán)重"，插入

9、鄰接表（c）注意：如果權(quán)重不是整型，Weight的讀入格式要改（4） clrv(LGraph g)函數(shù)功能：初始化圖的訪問數(shù)組Visited為0設(shè)計思想：重置被DFS和BFS修改過的visited數(shù)組（5） DFS( LGraph Graph, Vertex V ,int x)函數(shù)功能： 以V為出發(fā)點對鄰接表存儲的圖Graph進行DFS搜索設(shè)計思想:（a）首先訪問出發(fā)點v，并將其標(biāo)記為已訪問過；（b）然后依次從v出發(fā)搜索v的每個鄰接點w。若w未曾訪問過，則以w為新的出發(fā)點繼續(xù)進行深度優(yōu)先遍歷，直至圖中所有和源點v有路徑相通的頂點(亦稱為從源點可達(dá)的頂點)均已被訪問為止。（c）若此時圖中仍有未訪

10、問的頂點，則另選一個尚未訪問的頂點作為新的源點重復(fù)上述過程，直至圖中所有頂點均已被訪問為止。（d）也就是訪問頂點v，從v的未被訪問的鄰接點中選取一個頂點w，從w出發(fā)進行深度優(yōu)先遍歷，重復(fù)上述兩步，直至圖中所有和v有路徑相通的頂點都被訪問到。（6） CreateQueue()函數(shù)功能：初始化一個隊列設(shè)計思想：（a）隊列的front與rear分別置-1（b）為數(shù)組分配空間（7）AddQ(Queue Q, Vertex S)函數(shù)功能：向隊列中添加元素設(shè)計思想：（a）將rear位置挪一位（b）在rear這位加入一個數(shù)（8） DeleteQ(Queue Q)函數(shù)功能：隊列中刪除一個元素，并返回設(shè)計思想：

11、（a）從隊列的頭出隊（b）也就是front位置加一（c）將front 這位的數(shù)據(jù)彈出（9）IsEmpty(Queue Q)函數(shù)功能：判斷隊列是否為空設(shè)計思想：（a）判斷front的位置與rear是否相等（10）Unweighted ( LGraph Graph, Vertex S )函數(shù)功能：輸入兩點，求對應(yīng)不帶權(quán)值的圖的最短路徑設(shè)計思想：（a）按照遞增（非遞減）的順序找出各個頂點的最短路，類似于BFS（b）先創(chuàng)建空隊列, MaxSize為外部定義的常數(shù)（c）初始化源點.distS = 0（d）對V的每個鄰接點W->AdjV（e）若W->AdjV未被訪問過, W->AdjV到

12、S的距離更新（f）將V記錄在S到W->AdjV的路徑上 （11）BFS( LGraph Graph, Vertex V)函數(shù)功能：向隊列中添加元素設(shè)計思想：（a）頂點v入隊列。（b）當(dāng)隊列非空時則繼續(xù)執(zhí)行，否則算法結(jié)束。（c）出隊列取得隊頭頂點v；訪問頂點v并標(biāo)記頂點v已被訪問。（d）查找頂點v的第一個鄰接頂點first。（e）若v的鄰接頂點first未被訪問過的，則first入隊列。（f）繼續(xù)查找頂點v的另一個新的鄰接頂點first，轉(zhuǎn)到步驟（e）。（g）直到頂點v的所有未被訪問過的鄰接點處理完。轉(zhuǎn)到步驟（f）。（12） clr(LGraph Graph)函數(shù)功能：重置dist數(shù)組與p

13、ath數(shù)組設(shè)計思想：（a）重置最短路徑的舉例與路徑（13）FindMinDist( LGraph Graph, int collected )函數(shù)功能：傳入一個dist中沒有被收錄(collected對應(yīng)為-1)的數(shù)設(shè)計思想：（a）V從1到頂點最大的下標(biāo)（b）若V未被收錄，且distV更小 （c）更新最小距離更新對應(yīng)頂點 （d） 若找到最小dist，返回對應(yīng)的頂點下標(biāo)（e）若這樣的頂點不存在，返回錯誤標(biāo)記（14）Dijkstra( LGraph Graph, Vertex S )函數(shù)功能：求出輸入Vertex S的單源最短路徑設(shè)計思想：（a）Dijkstra算法開始采用的是一種貪心的策略，聲明

14、一個數(shù)組dist來保存源點到各個頂點的最短距離和一個保存已經(jīng)找到了最短路徑的頂點的集合T（b）初始時，原點 s 的路徑權(quán)重被賦為 0 （diss = 0）（c）若對于頂點 s 存在能直接到達(dá)的邊（s,m），則把dism設(shè)為w（s, m）,同時把所有其他（s不能直接到達(dá)的）頂點的路徑長度設(shè)為無窮大（d）初始時，集合T只有頂點s。（e）從dis數(shù)組選擇最小值（貪心），則該值就是源點s到該值對應(yīng)的頂點的最短路徑，并且把該點加入到T中，OK，此時完成一個頂點，（f）我們需要看看新加入的頂點是否可以到達(dá)其他頂點并且看看通過該頂點到達(dá)其他點的路徑長度是否比源點直接到達(dá)短，如果是，那么就替換這些頂點在dis

15、中的值。 （g）然后，又從dis中找出最小值，重復(fù)上述動作，直到T中包含了圖的所有頂點。（15）transform(LGraph a)函數(shù)功能：鄰接矩陣與鄰接表轉(zhuǎn)換設(shè)計思想：（a）分析鄰接矩陣與鄰接表的異同（b）鄰接表有一個頭結(jié)點數(shù)組，每一個對應(yīng)一串鏈表，跟著的是每一個頂點與鄰接點相連（c）鄰接矩陣則是一個二維數(shù)組，兩點有邊值為權(quán)重，沒有則初始化為無窮（d）先初始化一個空的二維數(shù)組（e）再對應(yīng)鄰接表每個頭結(jié)點遍歷其鏈表，將其值對應(yīng)的加入到鄰接矩陣中（16）outM(MGraph gra)函數(shù)功能：傳入鄰接矩陣結(jié)構(gòu)體，輸出鄰接矩陣設(shè)計思想：（a）相當(dāng)于輸出一個二維數(shù)組（17）outL(

16、LGraph Graph)函數(shù)功能：傳入鄰接表結(jié)構(gòu)體，輸出鄰接表設(shè)計思想：（a）第一個循環(huán)遍歷每個頭結(jié)點（b）在第一個循環(huán)中表結(jié)點的地址不為空則輸出（還要輸出權(quán)值）（18）Floyd( MGraph Graph, WeightType DmaxVnum, Vertex pathmaxVnum )函數(shù)功能：Floyd算法求出多源最短路徑設(shè)計思想：（a）通過Floyd計算圖G=(V,E)中各個頂點的最短路徑時，需要引入兩個矩陣，矩陣S中的元素aij表示頂點i(第i個頂點)到頂點j(第j個頂點)的距離。矩陣P中的元素bij，表示頂點i到頂點j經(jīng)過了bij記錄的值所表示的頂點。（b）假設(shè)圖G中頂點個數(shù)

17、為N，則需要對矩陣D和矩陣P進行N次更新。（c）初始時，矩陣D中頂點aij的距離為頂點i到頂點j的權(quán)值（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）同理，第k次更新時，如果”aij的距離” > “aik-1+ak-1j”，則更新aij為”aik-1+ak-1j”,bij=bik-1。更新N次之后，求出最短路徑（19）Strack createStr()函數(shù)

18、功能：創(chuàng)建一個棧設(shè)計思想：（a）分配空間，top = -1（20）push(Strack ptr,int v)函數(shù)功能：向棧中添加元素設(shè)計思想：（a）top加一（b）對應(yīng)位置存為v（21）pop(Strack ptr)函數(shù)功能：出棧設(shè)計思想：（a）先將棧頂元素彈出，top減一（22）sIsEmpty(Strack ptr)函數(shù)功能：判斷棧是否為空設(shè)計思想：（a）若果top=-1，為空，否則返回0（23）outpath(int v)函數(shù)功能：輸出最短路徑設(shè)計思想：（a）由于存最短路徑的path數(shù)組每位存的只是上一個頂點，所以每次查找都會不斷地找到每個頂點的上級，直至pathv=-1，會形成一個方

19、向的路徑，就要利用堆棧后進先出的特點輸出。（b）在path存的數(shù)據(jù)不為-1時，將他們?nèi)繅喝霔Ｖ?，再將他們?nèi)枯敵?、 詳細(xì)設(shè)計1. 程序流程圖建立圖插入邊初始化圖BFSDFS創(chuàng)建鄰接表D無權(quán)圖最短路徑轉(zhuǎn)鄰接矩陣Dijkstra算法求最小值Floyd算法2. 數(shù)據(jù)類型的實現(xiàn)（1）邊的定義 typedef struct ENode *PtrToENode;struct ENode Vertex V1, V2; /* 有向邊<V1, V2> */ WeightType Weight; /* 權(quán)重 */;typedef PtrToENode Edge;（2） 鄰接表的表結(jié)點的定義 typ

20、edef struct AdjVNode *PtrToAdjVNode;struct AdjVNode Vertex AdjV; /* 鄰接點下標(biāo) */ WeightType Weight; /* 邊權(quán)重 */ PtrToAdjVNode Next; /* 指向下一個鄰接點的指針 */;typedef PtrToAdjVNode ANode;（3）鄰接表的頂點表頭結(jié)點的定義 typedef struct Vnode PtrToAdjVNode FirstEdge;/* 邊表頭指針 */ DataType Data; /* 存頂點的數(shù)據(jù) */ /* 注意：很多情況下，頂點無數(shù)據(jù)，此時Data可以

21、不用出現(xiàn) */ AdjListmaxVnum; /* AdjList是鄰接表類型 */（4） 鄰接表對應(yīng)圖結(jié)點的定義 typedef struct GNode *PtrToGNode;struct GNode int Nv; /* 頂點數(shù) */ int Ne; /* 邊數(shù) */ AdjList G; /* 鄰接表 */;typedef PtrToGNode LGraph; /* 以鄰接表方式存儲的圖類型 */（5）鄰接矩陣的定義typedef struct MNode *PtrToMNode;struct MNode int Nv; /* 頂點數(shù) */ int Ne; /* 邊數(shù) */ Wei

22、ghtType GmaxVnummaxVnum; /* 鄰接矩陣 */;typedef PtrToMNode MGraph; /* 以鄰接矩陣存儲的圖類型 */（6） BFS存數(shù)據(jù)的隊列typedef struct Que *Queue;struct Que int front; int rear; int datalistmaxVnum;（7）用于輸出最短路徑的棧typedef struct Str *Strack;struct Str int top; int StrlistmaxVnum;3. 重要函數(shù)的偽代碼（1） 無權(quán)圖的單源最短路徑void Unweighted(Vertex s)

23、 Enqueue (s,q); while(隊列不空) v = Deququ(q); for(v的每個鄰接點w) if(w沒被訪問過) 更新w的距離； pathw=v; Enqueue(w,q); (2) 有權(quán)圖的單源最短路徑void Dijkstra(Vertex s)while(1) v = 未收錄頂點中的dist最小者； if(這樣的v不存在) break; collectedv = true; for(v的每個鄰接點w) if(w沒被收錄) if(distv + v到w的權(quán)值 < distw) 更新w的最短距離； pathw = v; （3）Depth-first search訪

24、問頂點v；visitedv=1；/算法執(zhí)行前visitedn=0w=頂點v的第一個鄰接點；while（w存在）if（w未被訪問）從頂點w出發(fā)遞歸執(zhí)行該算法；w=頂點v的下一個鄰接點；（4）BFS廣度優(yōu)先搜索初始化隊列Q；visitedn=0；訪問頂點v；visitedv=1；頂點v入隊列Q； while（隊列Q非空） v=隊列Q的對頭元素出隊； w=頂點v的第一個鄰接點； while（w存在） 如果w未訪問，則訪問頂點w； visitedw=1； 頂點w入隊列Q； w=頂點v的下一個鄰接點。4、 調(diào)試分析（1） 調(diào)試過程中遇到的問題是如何解決的。我是將每一個部分分開設(shè)計，運行成功再將他們整合到

25、一起，不免會出現(xiàn)各種各樣的問題，單獨拿出去就可以運行，但放在一起沒有報錯，可就是做不對。而且后來我發(fā)現(xiàn)早成這種現(xiàn)象的不是因為程序有大問題，是一些根本就沒有注意的小點造成的，例如定義的i加入到程序中就會被其中的i覆蓋，結(jié)構(gòu)體定義的不同等等，讓我明白以后需要注重整體，在意細(xì)節(jié)，才能快速的完成任務(wù)。（2）算法的時空分析和改進設(shè)想；首先，利用鄰接矩陣一定是稠密圖才合算，對DFS時間復(fù)雜度為O（n2），廣度優(yōu)先搜索相同。而利用鄰接表存儲稀疏圖合算。對DFS時間復(fù)雜度為O(n+e)，廣度優(yōu)先搜索相同F(xiàn)loyd-Warshall算法的時間復(fù)雜度為O(N3)，空間復(fù)雜度為O(N2)。Dijkstra：O(n2

26、)使用與權(quán)值為非負(fù)的圖的單源最短路徑。（2） 經(jīng)驗和體會通過這次設(shè)計我得到很深的體會，要好好的利用所學(xué)的知識，遇到難題要盡快查閱資料，已得到解決。5、 用戶使用說明1. 先輸入共要創(chuàng)建幾個圖（多組輸入）2. 輸入創(chuàng)建圖的頂點數(shù)3. 輸入創(chuàng)建圖的邊數(shù)4. 定義圖有無方向(1為有向圖，2為無向圖)5. 根據(jù)邊數(shù)輸入起點、終點、和權(quán)值6. 輸入DFS與BFS的起點7. 輸入兩個點求最短路徑6、 測試結(jié)果建立圖： 1 2 125 46 8 334 1頂點數(shù)：6邊長：6深度搜索起始頂點：1結(jié)果：1 5 6 4 3 2廣度搜索起始頂點：1結(jié)果：1 5 2 6 4 3輸入1,4,不帶權(quán)值的最短路徑：1 5

27、4長度為：2輸入1,4,不帶權(quán)值的最短路徑：1 2 3 4長度為：6開始測試：7、 測試情況測試成功，程序正常進行結(jié)果正確。1.對于第一次循環(huán)（無向圖）：DFS：1 5 4 2 3BFS：1 5 2 6 4 3不帶權(quán)的1到4最短路徑為：1 5 4長度為：2帶權(quán)的1到4最短路徑為：1 2 3 4長度為：6Floyd算法中求最短路徑也為62. 對于第二次循環(huán)（有向圖）：由于V6與其他頂點反向，所以DFS：1 5 4 3 2 正確BFS：1 5 2 4 3 正確不帶權(quán)的1到6最短路徑為：無因為1到6逆向帶權(quán)的1到4最短路徑為：無因為1到6逆向而在Floyd算法中求1到4最短路徑長度還是：6 正確附錄

28、（源代碼）：#include<iostream>#include<stdio.h>#include<stdlib.h>#define INF 100#define ERROR 200#define flase 0#define true 1#define maxVnum 100 /* 最大頂點數(shù)設(shè)為100 */typedef int Vertex; /* 用頂點下標(biāo)表示頂點,為整型 */ /* 圖的鄰接表表示法 */typedef int WeightType; /* 邊的權(quán)值設(shè)為整型 */typedef char DataType; /* 頂點存儲的數(shù)據(jù)類

29、型設(shè)為字符型 */ using namespace std; int distmaxVnum; int pathmaxVnum; int collectmaxVnum; /BFS存數(shù)據(jù)的隊列typedef struct Que *Queue;struct Que int front; int rear; int datalistmaxVnum;/輸出路徑的棧typedef struct Str *Strack;struct Str int top; int StrlistmaxVnum;/* 邊的定義 */typedef struct ENode *PtrToENode;struct ENod

30、e Vertex V1, V2; /* 有向邊<V1, V2> */ WeightType Weight; /* 權(quán)重 */;typedef PtrToENode Edge;/* 鄰接點的定義 */typedef struct AdjVNode *PtrToAdjVNode;struct AdjVNode Vertex AdjV; /* 鄰接點下標(biāo) */ WeightType Weight; /* 邊權(quán)重 */ PtrToAdjVNode Next; /* 指向下一個鄰接點的指針 */;typedef PtrToAdjVNode ANode;/* 頂點表頭結(jié)點的定義 */typed

31、ef struct Vnode PtrToAdjVNode FirstEdge;/* 邊表頭指針 */ DataType Data; /* 存頂點的數(shù)據(jù) */ /* 注意：很多情況下，頂點無數(shù)據(jù)，此時Data可以不用出現(xiàn) */ AdjListmaxVnum; /* AdjList是鄰接表類型 */* 圖結(jié)點的定義 */typedef struct GNode *PtrToGNode;struct GNode int Nv; /* 頂點數(shù) */ int Ne; /* 邊數(shù) */ AdjList G; /* 鄰接表 */;typedef PtrToGNode LGraph; /* 以鄰接表方式存儲

32、的圖類型 */typedef struct MNode *PtrToMNode;struct MNode int Nv; /* 頂點數(shù) */ int Ne; /* 邊數(shù) */ WeightType GmaxVnummaxVnum; /* 鄰接矩陣 */;typedef PtrToMNode MGraph; /* 以鄰接矩陣存儲的圖類型 */LGraph CreateGraph( int VertexNum ) /* 初始化一個有VertexNum個頂點但沒有邊的圖 */ Vertex V; LGraph Graph; Graph = (LGraph)malloc( sizeof(struct

33、GNode) ); /* 建立圖 */ Graph->Nv = VertexNum; Graph->Ne = 0; /* 初始化鄰接表頭指針 */ /* 注意：這里默認(rèn)頂點編號從1開始，到Graph->Nv */ for (V = 1; V <= Graph->Nv; V+) Graph->GV.FirstEdge = NULL; distV = -1; pathV = -1; return Graph;void InsertEdge( LGraph Graph, Edge E, int c ) PtrToAdjVNode NewNode; /* 插入邊 &

34、lt;V1, V2> */ /* 為V2建立新的鄰接點 */ NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode); NewNode->AdjV = E->V2; NewNode->Weight = E->Weight; /* 將V2插入V1的表頭 */ NewNode->Next = Graph->GE->V1.FirstEdge; Graph->GE->V1.FirstEdge = NewNode; if(c = 2) /* 若是無向圖，還要插入邊 <V2, V1&g

35、t; */ /* 為V1建立新的鄰接點 */ NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode); NewNode->AdjV = E->V1; NewNode->Weight = E->Weight; /* 將V1插入V2的表頭 */ NewNode->Next = Graph->GE->V2.FirstEdge; Graph->GE->V2.FirstEdge = NewNode; LGraph BuildGraph() LGraph Graph; Edge E; Vertex

36、 V; int Nv, i; cout<<"輸入圖的頂點個數(shù):" scanf("%d", &Nv); /* 讀入頂點個數(shù) */ Graph = CreateGraph(Nv); /* 初始化有Nv個頂點但沒有邊的圖 */ cout<<"輸入圖的邊數(shù):" scanf("%d", &(Graph->Ne); /* 讀入邊數(shù) */ int c; cout<<"定義圖為(1.有向)(2.無向):" cin>>c; if ( Graph

37、->Ne != 0 ) /* 如果有邊 */ E = (Edge)malloc( sizeof(struct ENode) ); /* 建立邊結(jié)點 */ /* 讀入邊，格式為"起點 終點 權(quán)重" */ for (i=0; i<Graph->Ne; i+) printf("v1,v2,weight:"); scanf("%d %d %d", &E->V1, &E->V2, &E->Weight); /* 注意：如果權(quán)重不是整型，Weight的讀入格式要改 */ InsertEd

38、ge( Graph, E ,c ); return Graph;int VisitedmaxVnum;void clrv(LGraph g) int i; for(i = 1; i <= g->Nv; i+ ) Visitedi = 0;void DFS( LGraph Graph, Vertex V ,int x) /* 以V為出發(fā)點對鄰接表存儲的圖Graph進行DFS搜索 */ PtrToAdjVNode W; if(x = 1) clrv(Graph); x+; cout<<V<<" " VisitedV = true; /* 標(biāo)記

39、V已訪問 */ for( W=Graph->GV.FirstEdge; W != NULL; W=W->Next ) /* 對V的每個鄰接點W->AdjV */ if ( !VisitedW->AdjV ) /* 若W->AdjV未被訪問 */ DFS( Graph, W->AdjV,x); /* 則遞歸訪問之 */* 鄰接表存儲 - 無權(quán)圖的單源最短路算法 */Queue CreateQueue() Queue Q; Q = (Queue)malloc(sizeof(struct Que); Q->front = -1; Q->rear = -

40、1; return (Q);void AddQ(Queue Q, Vertex S) Q->rear+; Q->datalistQ->rear = S;int DeleteQ(Queue Q) Q->front+; return (Q->datalistQ->front);int IsEmpty(Queue Q) if(Q->front = Q->rear) return 1; else return 0;/* dist和path全部初始化為-1 */void Unweighted ( LGraph Graph, Vertex S ) Queue

41、 Q; Vertex V; PtrToAdjVNode W; Q = CreateQueue(); /* 創(chuàng)建空隊列, MaxSize為外部定義的常數(shù) */ distS = 0; /* 初始化源點 */ AddQ (Q, S); while( !IsEmpty(Q) ) V = DeleteQ(Q); for ( W = Graph->GV.FirstEdge; W != NULL; W = W->Next ) /* 對V的每個鄰接點W->AdjV */ if ( distW->AdjV=-1 ) /* 若W->AdjV未被訪問過 */ distW->Adj

42、V = distV+1; /* W->AdjV到S的距離更新 */ pathW->AdjV = V; /* 將V記錄在S到W->AdjV的路徑上 */ AddQ(Q, W->AdjV); /* while結(jié)束*/void BFS( LGraph Graph, Vertex V) PtrToAdjVNode W; Queue Q; Q = CreateQueue(); clrv(Graph); AddQ(Q,V); VisitedV = true; while(!IsEmpty(Q) V = DeleteQ(Q); cout<<V<<"

43、" for(W = Graph->GV.FirstEdge; W != NULL; W = W->Next) if(VisitedW->AdjV = false) AddQ(Q,W->AdjV); VisitedW->AdjV = true; void clr(LGraph Graph) int i,j; for(i = 1; i <= Graph->Nv; i+) disti = INF; pathi = -1; / 鄰接表存儲 - 有權(quán)圖的單源最短路算法Vertex FindMinDist( LGraph Graph, int colle

44、cted ) /* 返回未被收錄頂點中dist最小者 */ Vertex MinV, V; int MinDist = INF; for (V = 1; V <= Graph->Nv; V+) if ( collectedV = false && distV < MinDist) /* 若V未被收錄，且distV更小 */ MinDist = distV; /* 更新最小距離 */ MinV = V; /* 更新對應(yīng)頂點 */ if (MinDist < INF) /* 若找到最小dist */ return MinV; /* 返回對應(yīng)的頂點下標(biāo) */

45、else return ERROR; /* 若這樣的頂點不存在，返回錯誤標(biāo)記 */void Dijkstra( LGraph Graph, Vertex S ) int collectedmaxVnum; Vertex V; PtrToAdjVNode W; /* 初始化：此處默認(rèn)鄰接矩陣中不存在的邊用INFINITY表示 */ clr(Graph); W = Graph->GS.FirstEdge; for(W = Graph->GS.FirstEdge; W!=NULL;W = W->Next) distW->AdjV = W->Weight; pathW-&

46、gt;AdjV = S; for(V = 1; V <= Graph->Nv; V+) collectedV = false; /* 先將起點收入集合 */ distS = 0; collectedS = true; while(true) /* V = 未被收錄頂點中dist最小者 */ V = FindMinDist( Graph, collected ); if ( V = ERROR ) /* 若這樣的V不存在 */ break; /* 算法結(jié)束 */ collectedV = true; /* 收錄V */ for ( W = Graph->GV.FirstEdge

47、; W != NULL; W = W->Next ) /* 對V的每個鄰接點W->AdjV */ if ( collectedW->AdjV = false ) /* 若W->AdjV未被訪問過 */ if(distV+W->Weight < distW->AdjV) distW->AdjV = distV + W->Weight; pathW->AdjV = V; /* while結(jié)束*/MGraph transform(LGraph a)/鄰接矩陣與鄰接表轉(zhuǎn)換 MGraph b; int i,j; ANode p; b = (MG

48、raph)malloc(sizeof(struct MNode); b->Nv = a->Nv; b->Ne = a->Ne; for(i=1; i<=b->Nv; i+) for(j=1; j<=b->Nv; j+) b->Gij=INF; for(i=1; i<=b->Nv; i+) p=(ANode)malloc(sizeof(ANode); p=a->Gi.FirstEdge; while(p!=NULL) b->Gip->AdjV=p->Weight; p = p->Next; return (b);void outM(MGraph gra) int i,j; cout<<"鄰接表轉(zhuǎn)換為矩陣輸出:"<<endl; for(