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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

17、d）如果i和j不相鄰，則aij=，矩陣P的值為頂點(diǎn)bij的j的值（e），對矩陣D進(jìn)行N次更新（f）第1次更新時(shí)，如果”aij的距離” “ai0+a0j”(ai0+a0j表示”i與j之間經(jīng)過第1個(gè)頂點(diǎn)的距離”)，則更新aij為”ai0+a0j”,更新bij=bi0。（g）同理，第k次更新時(shí)，如果”aij的距離” “aik-1+ak-1j”，則更新aij為”aik-1+ak-1j”,bij=bik-1。更新N次之后，求出最短路徑（19）Strack createStr()函數(shù)功能：創(chuàng)建一個(gè)棧設(shè)計(jì)思想：（a）分配空間，top = -1（20）push(Strack ptr,int v)函數(shù)功能：向棧

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

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

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

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

22、型 */（6） BFS存數(shù)據(jù)的隊(duì)列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) Enqueue (s,q); while(隊(duì)列不空) v = Deququ(q); for(v的每個(gè)鄰接點(diǎn)w) if(w沒被訪問過) 更新w的距離；

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

24、點(diǎn)v的下一個(gè)鄰接點(diǎn)；（4）BFS廣度優(yōu)先搜索初始化隊(duì)列Q；visitedn=0；訪問頂點(diǎn)v；visitedv=1；頂點(diǎn)v入隊(duì)列Q； while（隊(duì)列Q非空） v=隊(duì)列Q的對頭元素出隊(duì)； w=頂點(diǎn)v的第一個(gè)鄰接點(diǎn)； while（w存在） 如果w未訪問，則訪問頂點(diǎn)w； visitedw=1； 頂點(diǎn)w入隊(duì)列Q； w=頂點(diǎn)v的下一個(gè)鄰接點(diǎn)。4、 調(diào)試分析（1） 調(diào)試過程中遇到的問題是如何解決的。我是將每一個(gè)部分分開設(shè)計(jì)，運(yùn)行成功再將他們整合到一起，不免會出現(xiàn)各種各樣的問題，單獨(dú)拿出去就可以運(yùn)行，但放在一起沒有報(bào)錯，可就是做不對。而且后來我發(fā)現(xiàn)早成這種現(xiàn)象的不是因?yàn)槌绦蛴写髥栴}，是一些根本就沒有注意的小

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

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

27、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與其他頂點(diǎn)反向，所以DFS：1 5 4 3 2 正確BFS：1 5 2 4 3 正確不帶權(quán)的1到6最短路徑為：無因?yàn)?到6逆向帶權(quán)的1到4最短路徑為：無因?yàn)?到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 /* 最大頂點(diǎn)數(shù)設(shè)為100 */typedef int Vertex; /* 用頂點(diǎn)下標(biāo)表示頂點(diǎn),為整型 */ /* 圖的鄰接表表示法 */typedef int WeightType; /* 邊的權(quán)值設(shè)為整型 */typedef char DataType; /* 頂點(diǎn)存儲的數(shù)據(jù)類型設(shè)為字符型 */ using namespace std; int distmaxVnum; int pathmaxVnum; int collectmaxVnum; /BFS存數(shù)據(jù)的隊(duì)列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; /* 權(quán)重 */;typedef PtrToENode Edge;/* 鄰接點(diǎn)的定義 */typedef struct AdjVNode *PtrToAdjVNod

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

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

32、ode MGraph; /* 以鄰接矩陣存儲的圖類型 */LGraph CreateGraph( int VertexNum ) /* 初始化一個(gè)有VertexNum個(gè)頂點(diǎn)但沒有邊的圖 */ Vertex V; LGraph Graph; Graph = (LGraph)malloc( sizeof(struct GNode) ); /* 建立圖 */ Graph-Nv = VertexNum; Graph-Ne = 0; /* 初始化鄰接表頭指針 */ /* 注意：這里默認(rèn)頂點(diǎn)編號從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建立新的鄰接點(diǎn) */ 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建立新的鄰接點(diǎn) */ 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輸入圖的頂點(diǎn)個(gè)數(shù):; scanf(%d, &Nv); /* 讀入頂點(diǎn)個(gè)數(shù) */ Graph = CreateGraph(Nv); /* 初始化有Nv個(gè)頂點(diǎn)但沒有邊的圖 */ coutNe); /* 讀入邊數(shù) */ int c; coutc; if ( Graph-Ne != 0 ) /* 如果有邊 */ E = (Edge)malloc( sizeof(struct ENode) ); /* 建立邊結(jié)點(diǎn) */ /* 讀入邊，格式為起點(diǎn) 終點(diǎn) 權(quán)重 */ for (i=0; iNe; i+) printf(v1

36、,v2,weight:); scanf(%d %d %d, &E-V1, &E-V2, &E-Weight); /* 注意：如果權(quán)重不是整型，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ā)點(diǎn)對鄰接表存儲的圖Graph進(jìn)行DFS搜索 */ PtrToAdjVNode W;

37、if(x = 1) clrv(Graph); x+; coutVGV.FirstEdge; W != NULL; W=W-Next ) /* 對V的每個(gè)鄰接點(diǎn)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 = -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)建空隊(duì)列, MaxSize為外部定義的常數(shù) */ distS = 0; /* 初始化源點(diǎn) */ AddQ (Q, S); while( !IsEmpty(Q) ) V = DeleteQ(Q); for ( W = Graph-GV.FirstEdge; W != NULL; W = W-Next ) /* 對V的每個(gè)鄰接點(diǎn)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結(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); 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; / 鄰接表存儲 - 有權(quán)圖的單源最短路算法Vertex FindMinDist( LGraph Graph, int collected ) /* 返回未被收錄頂點(diǎn)中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; /* 更新對應(yīng)頂點(diǎn) */ 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; /* 先將起點(diǎn)收入集合 */ distS = 0; collectedS = true; while(true) /* V = 未被收錄頂點(diǎn)中dist最小者 */ V = FindMinDist( Graph, collected ); if ( V = ERROR ) /* 若這樣的V不存在 */ break; /* 算法結(jié)束 */ collectedV = true; /* 收錄V */ for ( W = Graph-GV.FirstEdge; W != NULL; W = W-Next ) /* 對V的每個(gè)鄰接點(diǎn)W-AdjV */ if ( collectedW-AdjV = false ) /* 若W-AdjV未被訪