數據結構課程設計最短路徑

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

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

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

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

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

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

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

8、 c )函數功能：在建立的圖中插入邊設計思想：（a）輸入v1，v2，建立一個v2的新的鄰接點（b）將V2插入V1的表頭，用c做標志位，在調用函數時輸入（c）若c=2，表示圖為無向圖，還要插入邊 （d）接著為V1建立新的鄰接點，將V1插入V2的表頭 （3） BuildGraph()函數功能：輸入頂點和邊數，定義有向圖和無向圖，建立圖，并返回鄰接表類型的指針設計思想：（a）讀入頂點個數，調用CreateGraph(Nv)初始化有Nv個頂點但沒有邊的圖（b）讀入邊數，定義有向、無向，如果有邊，建立邊結點，讀入邊，格式為起點 終點 權重，插入鄰接表（c）注意：如果權重不是整型，Weight的讀入格式要

9、改（4） clrv(LGraph g)函數功能：初始化圖的訪問數組Visited為0設計思想：重置被DFS和BFS修改過的visited數組（5） DFS( LGraph Graph, Vertex V ,int x)函數功能： 以V為出發(fā)點對鄰接表存儲的圖Graph進行DFS搜索設計思想:（a）首先訪問出發(fā)點v，并將其標記為已訪問過；（b）然后依次從v出發(fā)搜索v的每個鄰接點w。若w未曾訪問過，則以w為新的出發(fā)點繼續(xù)進行深度優(yōu)先遍歷，直至圖中所有和源點v有路徑相通的頂點(亦稱為從源點可達的頂點)均已被訪問為止。（c）若此時圖中仍有未訪問的頂點，則另選一個尚未訪問的頂點作為新的源點重復上述過程，

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

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

12、 Graph, Vertex V)函數功能：向隊列中添加元素設計思想：（a）頂點v入隊列。（b）當隊列非空時則繼續(xù)執(zhí)行，否則算法結束。（c）出隊列取得隊頭頂點v；訪問頂點v并標記頂點v已被訪問。（d）查找頂點v的第一個鄰接頂點first。（e）若v的鄰接頂點first未被訪問過的，則first入隊列。（f）繼續(xù)查找頂點v的另一個新的鄰接頂點first，轉到步驟（e）。（g）直到頂點v的所有未被訪問過的鄰接點處理完。轉到步驟（f）。（12） clr(LGraph Graph)函數功能：重置dist數組與path數組設計思想：（a）重置最短路徑的舉例與路徑（13）FindMinDist( LGra

13、ph Graph, int collected )函數功能：傳入一個dist中沒有被收錄(collected對應為-1)的數設計思想：（a）V從1到頂點最大的下標（b）若V未被收錄，且distV更小 （c）更新最小距離更新對應頂點 （d） 若找到最小dist，返回對應的頂點下標（e）若這樣的頂點不存在，返回錯誤標記（14）Dijkstra( LGraph Graph, Vertex S )函數功能：求出輸入Vertex S的單源最短路徑設計思想：（a）Dijkstra算法開始采用的是一種貪心的策略，聲明一個數組dist來保存源點到各個頂點的最短距離和一個保存已經找到了最短路徑的頂點的集合T（b

14、）初始時，原點 s 的路徑權重被賦為 0 （diss = 0）（c）若對于頂點 s 存在能直接到達的邊（s,m），則把dism設為w（s, m）,同時把所有其他（s不能直接到達的）頂點的路徑長度設為無窮大（d）初始時，集合T只有頂點s。（e）從dis數組選擇最小值（貪心），則該值就是源點s到該值對應的頂點的最短路徑，并且把該點加入到T中，OK，此時完成一個頂點，（f）我們需要看看新加入的頂點是否可以到達其他頂點并且看看通過該頂點到達其他點的路徑長度是否比源點直接到達短，如果是，那么就替換這些頂點在dis中的值。（g）然后，又從dis中找出最小值，重復上述動作，直到T中包含了圖的所有頂點。（15

15、）transform(LGraph a)函數功能：鄰接矩陣與鄰接表轉換設計思想：（a）分析鄰接矩陣與鄰接表的異同（b）鄰接表有一個頭結點數組，每一個對應一串鏈表，跟著的是每一個頂點與鄰接點相連（c）鄰接矩陣則是一個二維數組，兩點有邊值為權重，沒有則初始化為無窮（d）先初始化一個空的二維數組（e）再對應鄰接表每個頭結點遍歷其鏈表，將其值對應的加入到鄰接矩陣中（16）outM(MGraph gra)函數功能：傳入鄰接矩陣結構體，輸出鄰接矩陣設計思想：（a）相當于輸出一個二維數組（17）outL(LGraph Graph)函數功能：傳入鄰接表結構體，輸出鄰接表設計思想：（a）第一個循環(huán)遍歷每個頭結點

16、（b）在第一個循環(huán)中表結點的地址不為空則輸出（還要輸出權值）（18）Floyd( MGraph Graph, WeightType DmaxVnum, Vertex pathmaxVnum )函數功能：Floyd算法求出多源最短路徑設計思想：（a）通過Floyd計算圖G=(V,E)中各個頂點的最短路徑時，需要引入兩個矩陣，矩陣S中的元素aij表示頂點i(第i個頂點)到頂點j(第j個頂點)的距離。矩陣P中的元素bij，表示頂點i到頂點j經過了bij記錄的值所表示的頂點。（b）假設圖G中頂點個數為N，則需要對矩陣D和矩陣P進行N次更新。（c）初始時，矩陣D中頂點aij的距離為頂點i到頂點j的權值（

17、d）如果i和j不相鄰，則aij=，矩陣P的值為頂點bij的j的值（e），對矩陣D進行N次更新（f）第1次更新時，如果”aij的距離” “ai0+a0j”(ai0+a0j表示”i與j之間經過第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()函數功能：創(chuàng)建一個棧設計思想：（a）分配空間，top = -1（20）push(Strack ptr,int v)函數功能：向棧

18、中添加元素設計思想：（a）top加一（b）對應位置存為v（21）pop(Strack ptr)函數功能：出棧設計思想：（a）先將棧頂元素彈出，top減一（22）sIsEmpty(Strack ptr)函數功能：判斷棧是否為空設計思想：（a）若果top=-1，為空，否則返回0（23）outpath(int v)函數功能：輸出最短路徑設計思想：（a）由于存最短路徑的path數組每位存的只是上一個頂點，所以每次查找都會不斷地找到每個頂點的上級，直至pathv=-1，會形成一個方向的路徑，就要利用堆棧后進先出的特點輸出。（b）在path存的數據不為-1時，將他們全部壓入棧中，再將他們全部輸出3、 詳細

19、設計1. 程序流程圖建立圖插入邊初始化圖BFSDFS創(chuàng)建鄰接表D無權圖最短路徑轉鄰接矩陣Dijkstra算法求最小值Floyd算法2. 數據類型的實現(xiàn)（1）邊的定義 typedef struct ENode *PtrToENode;struct ENode Vertex V1, V2; /* 有向邊 */ WeightType Weight; /* 權重 */;typedef PtrToENode Edge;（2） 鄰接表的表結點的定義 typedef struct AdjVNode *PtrToAdjVNode;struct AdjVNode Vertex AdjV; /* 鄰接點下標 */

20、 WeightType Weight; /* 邊權重 */ PtrToAdjVNode Next; /* 指向下一個鄰接點的指針 */;typedef PtrToAdjVNode ANode;（3）鄰接表的頂點表頭結點的定義 typedef struct Vnode PtrToAdjVNode FirstEdge;/* 邊表頭指針 */ DataType Data; /* 存頂點的數據 */ /* 注意：很多情況下，頂點無數據，此時Data可以不用出現(xiàn) */ AdjListmaxVnum; /* AdjList是鄰接表類型 */（4） 鄰接表對應圖結點的定義 typedef struct GN

21、ode *PtrToGNode;struct GNode int Nv; /* 頂點數 */ int Ne; /* 邊數 */ AdjList G; /* 鄰接表 */;typedef PtrToGNode LGraph; /* 以鄰接表方式存儲的圖類型 */（5）鄰接矩陣的定義typedef struct MNode *PtrToMNode;struct MNode int Nv; /* 頂點數 */ int Ne; /* 邊數 */ WeightType GmaxVnummaxVnum; /* 鄰接矩陣 */;typedef PtrToMNode MGraph; /* 以鄰接矩陣存儲的圖類

22、型 */（6） BFS存數據的隊列typedef struct Que *Queue;struct Que int front; int rear; int datalistmaxVnum;（7）用于輸出最短路徑的棧typedef struct Str *Strack;struct Str int top; int StrlistmaxVnum;3. 重要函數的偽代碼（1） 無權圖的單源最短路徑void Unweighted(Vertex s) Enqueue (s,q); while(隊列不空) v = Deququ(q); for(v的每個鄰接點w) if(w沒被訪問過) 更新w的距離；

23、pathw=v; Enqueue(w,q); (2) 有權圖的單源最短路徑void Dijkstra(Vertex s)while(1) v = 未收錄頂點中的dist最小者； if(這樣的v不存在) break; collectedv = true; for(v的每個鄰接點w) if(w沒被收錄) if(distv + v到w的權值 distw) 更新w的最短距離； pathw = v; （3）Depth-first search訪問頂點v；visitedv=1；/算法執(zhí)行前visitedn=0w=頂點v的第一個鄰接點；while（w存在）if（w未被訪問）從頂點w出發(fā)遞歸執(zhí)行該算法；w=頂

24、點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、 調試分析（1） 調試過程中遇到的問題是如何解決的。我是將每一個部分分開設計，運行成功再將他們整合到一起，不免會出現(xiàn)各種各樣的問題，單獨拿出去就可以運行，但放在一起沒有報錯，可就是做不對。而且后來我發(fā)現(xiàn)早成這種現(xiàn)象的不是因為程序有大問題，是一些根本就沒有注意的小

25、點造成的，例如定義的i加入到程序中就會被其中的i覆蓋，結構體定義的不同等等，讓我明白以后需要注重整體，在意細節(jié)，才能快速的完成任務。（2）算法的時空分析和改進設想；首先，利用鄰接矩陣一定是稠密圖才合算，對DFS時間復雜度為O（n2），廣度優(yōu)先搜索相同。而利用鄰接表存儲稀疏圖合算。對DFS時間復雜度為O(n+e)，廣度優(yōu)先搜索相同F(xiàn)loyd-Warshall算法的時間復雜度為O(N3)，空間復雜度為O(N2)。Dijkstra：O(n2)使用與權值為非負的圖的單源最短路徑。（2） 經驗和體會通過這次設計我得到很深的體會，要好好的利用所學的知識，遇到難題要盡快查閱資料，已得到解決。5、 用戶使用說

26、明1. 先輸入共要創(chuàng)建幾個圖（多組輸入）2. 輸入創(chuàng)建圖的頂點數3. 輸入創(chuàng)建圖的邊數4. 定義圖有無方向(1為有向圖，2為無向圖)5. 根據邊數輸入起點、終點、和權值6. 輸入DFS與BFS的起點7. 輸入兩個點求最短路徑6、 測試結果建立圖： 1 2 125 46 8 334 1頂點數：6邊長：6深度搜索起始頂點：1結果：1 5 6 4 3 2廣度搜索起始頂點：1結果：1 5 2 6 4 3輸入1,4,不帶權值的最短路徑：1 5 4長度為：2輸入1,4,不帶權值的最短路徑：1 2 3 4長度為：6開始測試：7、 測試情況測試成功，程序正常進行結果正確。1.對于第一次循環(huán)（無向圖）：DFS：

27、1 5 4 2 3BFS：1 5 2 6 4 3不帶權的1到4最短路徑為：1 5 4長度為：2帶權的1到4最短路徑為：1 2 3 4長度為：6Floyd算法中求最短路徑也為62. 對于第二次循環(huán)（有向圖）：由于V6與其他頂點反向，所以DFS：1 5 4 3 2 正確BFS：1 5 2 4 3 正確不帶權的1到6最短路徑為：無因為1到6逆向帶權的1到4最短路徑為：無因為1到6逆向而在Floyd算法中求1到4最短路徑長度還是：6 正確附錄（源代碼）：#include#include#include#define INF 100#define ERROR 200#define flase 0#def

28、ine true 1#define maxVnum 100 /* 最大頂點數設為100 */typedef int Vertex; /* 用頂點下標表示頂點,為整型 */ /* 圖的鄰接表表示法 */typedef int WeightType; /* 邊的權值設為整型 */typedef char DataType; /* 頂點存儲的數據類型設為字符型 */ using namespace std; int distmaxVnum; int pathmaxVnum; int collectmaxVnum; /BFS存數據的隊列typedef struct Que *Queue;struct

29、Que int front; int rear; int datalistmaxVnum;/輸出路徑的棧typedef struct Str *Strack;struct Str int top; int StrlistmaxVnum;/* 邊的定義 */typedef struct ENode *PtrToENode;struct ENode Vertex V1, V2; /* 有向邊 */ WeightType Weight; /* 權重 */;typedef PtrToENode Edge;/* 鄰接點的定義 */typedef struct AdjVNode *PtrToAdjVNod

30、e;struct AdjVNode Vertex AdjV; /* 鄰接點下標 */ WeightType Weight; /* 邊權重 */ PtrToAdjVNode Next; /* 指向下一個鄰接點的指針 */;typedef PtrToAdjVNode ANode;/* 頂點表頭結點的定義 */typedef struct Vnode PtrToAdjVNode FirstEdge;/* 邊表頭指針 */ DataType Data; /* 存頂點的數據 */ /* 注意：很多情況下，頂點無數據，此時Data可以不用出現(xiàn) */ AdjListmaxVnum; /* AdjList是鄰

31、接表類型 */* 圖結點的定義 */typedef struct GNode *PtrToGNode;struct GNode int Nv; /* 頂點數 */ int Ne; /* 邊數 */ AdjList G; /* 鄰接表 */;typedef PtrToGNode LGraph; /* 以鄰接表方式存儲的圖類型 */typedef struct MNode *PtrToMNode;struct MNode int Nv; /* 頂點數 */ int Ne; /* 邊數 */ WeightType GmaxVnummaxVnum; /* 鄰接矩陣 */;typedef PtrToMN

32、ode MGraph; /* 以鄰接矩陣存儲的圖類型 */LGraph CreateGraph( int VertexNum ) /* 初始化一個有VertexNum個頂點但沒有邊的圖 */ Vertex V; LGraph Graph; Graph = (LGraph)malloc( sizeof(struct GNode) ); /* 建立圖 */ Graph-Nv = VertexNum; Graph-Ne = 0; /* 初始化鄰接表頭指針 */ /* 注意：這里默認頂點編號從1開始，到Graph-Nv */ for (V = 1; V Nv; V+) Graph-GV.FirstEd

33、ge = NULL; distV = -1; pathV = -1; return Graph;void InsertEdge( LGraph Graph, Edge E, int c ) PtrToAdjVNode NewNode; /* 插入邊 */ /* 為V2建立新的鄰接點 */ NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode); NewNode-AdjV = E-V2; NewNode-Weight = E-Weight; /* 將V2插入V1的表頭 */ NewNode-Next = Graph-GE-V1.FirstE

34、dge; Graph-GE-V1.FirstEdge = NewNode; if(c = 2) /* 若是無向圖，還要插入邊 */ /* 為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() LGra

35、ph Graph; Edge E; Vertex V; int Nv, i; cout輸入圖的頂點個數:; scanf(%d, &Nv); /* 讀入頂點個數 */ Graph = CreateGraph(Nv); /* 初始化有Nv個頂點但沒有邊的圖 */ coutNe); /* 讀入邊數 */ int c; coutc; if ( Graph-Ne != 0 ) /* 如果有邊 */ E = (Edge)malloc( sizeof(struct ENode) ); /* 建立邊結點 */ /* 讀入邊，格式為起點 終點 權重 */ for (i=0; iNe; i+) printf(v1

36、,v2,weight:); scanf(%d %d %d, &E-V1, &E-V2, &E-Weight); /* 注意：如果權重不是整型，Weight的讀入格式要改 */ InsertEdge( Graph, E ,c ); return Graph;int VisitedmaxVnum;void clrv(LGraph g) int i; for(i = 1; i Nv; i+ ) Visitedi = 0;void DFS( LGraph Graph, Vertex V ,int x) /* 以V為出發(fā)點對鄰接表存儲的圖Graph進行DFS搜索 */ PtrToAdjVNode W;

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

38、dQ(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 Q; Vertex V; PtrToAdjVNode W; Q = CreateQueue(); /*

39、創(chuàng)建空隊列, MaxSize為外部定義的常數 */ 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-AdjV = distV+1; /* W-AdjV到S的距離更新 */ pathW-AdjV = V; /* 將V記錄在S到W-AdjV的路徑上 */ AddQ

40、(Q, W-AdjV); /* while結束*/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); coutVGV.FirstEdge; W != NULL; W = W-Next) if(VisitedW-AdjV = false) AddQ(Q,W-AdjV); VisitedW-AdjV = true; void clr(LGraph

41、 Graph) int i,j; for(i = 1; i Nv; i+) disti = INF; pathi = -1; / 鄰接表存儲 - 有權圖的單源最短路算法Vertex FindMinDist( LGraph Graph, int collected ) /* 返回未被收錄頂點中dist最小者 */ Vertex MinV, V; int MinDist = INF; for (V = 1; V Nv; V+) if ( collectedV = false & distV MinDist) /* 若V未被收錄，且distV更小 */ MinDist = distV; /* 更新最

42、小距離 */ MinV = V; /* 更新對應頂點 */ if (MinDist GS.FirstEdge; for(W = Graph-GS.FirstEdge; W!=NULL;W = W-Next) distW-AdjV = W-Weight; pathW-AdjV = S; for(V = 1; V Nv; V+) collectedV = false; /* 先將起點收入集合 */ distS = 0; collectedS = true; while(true) /* V = 未被收錄頂點中dist最小者 */ V = FindMinDist( Graph, collected ); if ( V = ERROR ) /* 若這樣的V不存在 */ break; /* 算法結束 */ collectedV = true; /* 收錄V */ for ( W = Graph-GV.FirstEdge; W != NULL; W = W-Next ) /* 對V的每個鄰接點W-AdjV */ if ( collectedW-AdjV = false ) /* 若W-AdjV未被訪