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

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

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

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

4、ldGraph()函數(shù)，創(chuàng)建一個(gè)圖并以鄰接表的形式存儲(chǔ)（c） BuildGraph()函數(shù)輸入頂點(diǎn)、邊數(shù)調(diào)用CreateGraph(Nv）函數(shù)，初始化一個(gè)有Nv個(gè)頂點(diǎn)但沒(méi)有邊的圖，再根據(jù)結(jié)構(gòu)體Edge輸入每個(gè)邊的信息，調(diào)用InsertEdge( Graph, E ,c );函數(shù)將每條邊插入到僅僅初始化的圖中，完成一個(gè)圖的建立，并返回一個(gè)鄰接表類(lèi)型的結(jié)構(gòu)體（d） 主函數(shù)接到返回來(lái)的鄰接表結(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ù)求得多源最短路徑，存儲(chǔ)在D這個(gè)二維數(shù)組中，給出起點(diǎn)，終點(diǎn)直接輸出。2.所有用到的抽象數(shù)據(jù)類(lèi)型（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）鄰接表類(lèi)型的 AdjList存儲(chǔ)鄰接表的頭結(jié)點(diǎn)（4） 鄰接表對(duì)應(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)但沒(méi)有邊的圖 設(shè)計(jì)思想：（a）根據(jù)鄰接表結(jié)構(gòu)體分配一塊空間（b）初始化圖的頂點(diǎn)數(shù)和邊數(shù)（c）初始化鄰接表頭指針（d）注意：這里默認(rèn)頂點(diǎn)編號(hào)從1開(kāi)始，到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，表示圖為無(wú)向圖，還要插入邊 （d）接著為V1建立新的鄰接點(diǎn)，將V1插入V2的表頭 （3） BuildGraph()函數(shù)功能：輸入頂點(diǎn)和邊數(shù)，定義有向圖和無(wú)向圖，建立圖，并返回鄰接表類(lèi)型的指針設(shè)計(jì)思想：（a）讀入頂點(diǎn)個(gè)數(shù)，調(diào)用CreateGraph(Nv)初始化有Nv個(gè)頂點(diǎn)但沒(méi)有邊的圖（b）讀入邊數(shù)，定義有向、無(wú)向，如果有邊，建立邊結(jié)點(diǎn)，讀入邊，格式為起點(diǎn) 終點(diǎn) 權(quán)重，插入鄰接表（c）注意：如果權(quán)重不是整型，Weight的讀入格式要

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

10、直至圖中所有頂點(diǎn)均已被訪問(wèn)為止。（d）也就是訪問(wèn)頂點(diǎn)v，從v的未被訪問(wèn)的鄰接點(diǎn)中選取一個(gè)頂點(diǎn)w，從w出發(fā)進(jìn)行深度優(yōu)先遍歷，重復(fù)上述兩步，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪問(wè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)，求對(duì)應(yīng)不帶權(quán)值的圖的最短路徑設(shè)計(jì)思想：（a）按照遞增（非遞減）的順序找出各個(gè)頂點(diǎn)的最短路，類(lèi)似于BFS（b）先創(chuàng)建空隊(duì)列, MaxSize為外部定義的常數(shù)（c）初始化源點(diǎn).distS = 0（d）對(duì)V的每個(gè)鄰接點(diǎn)W-AdjV（e）若W-AdjV未被訪問(wèn)過(guò), 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；訪問(wèn)頂點(diǎn)v并標(biāo)記頂點(diǎn)v已被訪問(wèn)。（d）查找頂點(diǎn)v的第一個(gè)鄰接頂點(diǎn)first。（e）若v的鄰接頂點(diǎn)first未被訪問(wèn)過(guò)的，則first入隊(duì)列。（f）繼續(xù)查找頂點(diǎn)v的另一個(gè)新的鄰接頂點(diǎn)first，轉(zhuǎn)到步驟（e）。（g）直到頂點(diǎn)v的所有未被訪問(wèn)過(guò)的鄰接點(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中沒(méi)有被收錄(collected對(duì)應(yīng)為-1)的數(shù)設(shè)計(jì)思想：（a）V從1到頂點(diǎn)最大的下標(biāo)（b）若V未被收錄，且distV更小 （c）更新最小距離更新對(duì)應(yīng)頂點(diǎn) （d） 若找到最小dist，返回對(duì)應(yīng)的頂點(diǎn)下標(biāo)（e）若這樣的頂點(diǎn)不存在，返回錯(cuò)誤標(biāo)記（14）Dijkstra( LGraph Graph, Vertex S )函數(shù)功能：求出輸入Vertex S的單源最短路徑設(shè)計(jì)思想：（a）Dijkstra算法開(kāi)始采用的是一種貪心的策略，聲明一個(gè)數(shù)組dist來(lái)保存源點(diǎn)到各個(gè)頂點(diǎn)的最短距離和一個(gè)保存已經(jīng)找到了最短路徑的頂點(diǎn)的集合T（b

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

15、）transform(LGraph a)函數(shù)功能：鄰接矩陣與鄰接表轉(zhuǎn)換設(shè)計(jì)思想：（a）分析鄰接矩陣與鄰接表的異同（b）鄰接表有一個(gè)頭結(jié)點(diǎn)數(shù)組，每一個(gè)對(duì)應(yīng)一串鏈表，跟著的是每一個(gè)頂點(diǎn)與鄰接點(diǎn)相連（c）鄰接矩陣則是一個(gè)二維數(shù)組，兩點(diǎn)有邊值為權(quán)重，沒(méi)有則初始化為無(wú)窮（d）先初始化一個(gè)空的二維數(shù)組（e）再對(duì)應(yīng)鄰接表每個(gè)頭結(jié)點(diǎn)遍歷其鏈表，將其值對(duì)應(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）通過(guò)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)過(guò)了bij記錄的值所表示的頂點(diǎn)。（b）假設(shè)圖G中頂點(diǎn)個(gè)數(shù)為N，則需要對(duì)矩陣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），對(duì)矩陣D進(jìn)行N次更新（f）第1次更新時(shí)，如果”aij的距離” “ai0+a0j”(ai0+a0j表示”i與j之間經(jīng)過(guò)第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）對(duì)應(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)，所以每次查找都會(huì)不斷地找到每個(gè)頂點(diǎn)的上級(jí)，直至pathv=-1，會(huì)形成一個(gè)方向的路徑，就要利用堆棧后進(jìn)先出的特點(diǎn)輸出。（b）在path存的數(shù)據(jù)不為-1時(shí)，將他們?nèi)繅喝霔Ｖ校賹⑺麄內(nèi)枯敵?、 詳細(xì)

19、設(shè)計(jì)1. 程序流程圖建立圖插入邊初始化圖BFSDFS創(chuàng)建鄰接表D無(wú)權(quán)圖最短路徑轉(zhuǎn)鄰接矩陣Dijkstra算法求最小值Floyd算法2. 數(shù)據(jù)類(lèi)型的實(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)無(wú)數(shù)據(jù)，此時(shí)Data可以不用出現(xiàn) */ AdjListmaxVnum; /* AdjList是鄰接表類(lèi)型 */（4） 鄰接表對(duì)應(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; /* 以鄰接表方式存儲(chǔ)的圖類(lèi)型 */（5）鄰接矩陣的定義typedef struct MNode *PtrToMNode;struct MNode int Nv; /* 頂點(diǎn)數(shù) */ int Ne; /* 邊數(shù) */ WeightType GmaxVnummaxVnum; /* 鄰接矩陣 */;typedef PtrToMNode MGraph; /* 以鄰接矩陣存儲(chǔ)的圖類(lèi)

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） 無(wú)權(quán)圖的單源最短路徑void Unweighted(Vertex s) Enqueue (s,q); while(隊(duì)列不空) v = Deququ(q); for(v的每個(gè)鄰接點(diǎn)w) if(w沒(méi)被訪問(wèn)過(guò)) 更新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沒(méi)被收錄) if(distv + v到w的權(quán)值 distw) 更新w的最短距離； pathw = v; （3）Depth-first search訪問(wèn)頂點(diǎn)v；visitedv=1；/算法執(zhí)行前visitedn=0w=頂點(diǎn)v的第一個(gè)鄰接點(diǎn)；while（w存在）if（w未被訪問(wèn)）從頂點(diǎn)w出發(fā)遞歸執(zhí)行該算法；w=頂

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

25、點(diǎn)造成的，例如定義的i加入到程序中就會(huì)被其中的i覆蓋，結(jié)構(gòu)體定義的不同等等，讓我明白以后需要注重整體，在意細(xì)節(jié)，才能快速的完成任務(wù)。（2）算法的時(shí)空分析和改進(jìn)設(shè)想；首先，利用鄰接矩陣一定是稠密圖才合算，對(duì)DFS時(shí)間復(fù)雜度為O（n2），廣度優(yōu)先搜索相同。而利用鄰接表存儲(chǔ)稀疏圖合算。對(duì)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)和體會(huì)通過(guò)這次設(shè)計(jì)我得到很深的體會(huì)，要好好的利用所學(xué)的知識(shí)，遇到難題要盡快查閱資料，已得到解決。5、 用戶(hù)使用說(shuō)

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

27、1 5 4 2 3BFS：1 5 2 6 4 3不帶權(quán)的1到4最短路徑為：1 5 4長(zhǎng)度為：2帶權(quán)的1到4最短路徑為：1 2 3 4長(zhǎng)度為：6Floyd算法中求最短路徑也為62. 對(duì)于第二次循環(huán)（有向圖）：由于V6與其他頂點(diǎn)反向，所以DFS：1 5 4 3 2 正確BFS：1 5 2 4 3 正確不帶權(quán)的1到6最短路徑為：無(wú)因?yàn)?到6逆向帶權(quán)的1到4最短路徑為：無(wú)因?yàn)?到6逆向而在Floyd算法中求1到4最短路徑長(zhǎng)度還是：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)存儲(chǔ)的數(shù)據(jù)類(lèi)型設(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)無(wú)數(shù)據(jù)，此時(shí)Data可以不用出現(xiàn) */ AdjListmaxVnum; /* AdjList是鄰

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

32、ode MGraph; /* 以鄰接矩陣存儲(chǔ)的圖類(lèi)型 */LGraph CreateGraph( int VertexNum ) /* 初始化一個(gè)有VertexNum個(gè)頂點(diǎn)但沒(méi)有邊的圖 */ Vertex V; LGraph Graph; Graph = (LGraph)malloc( sizeof(struct GNode) ); /* 建立圖 */ Graph-Nv = VertexNum; Graph-Ne = 0; /* 初始化鄰接表頭指針 */ /* 注意：這里默認(rèn)頂點(diǎn)編號(hào)從1開(kāi)始，到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) /* 若是無(wú)向圖，還要插入邊 */ /* 為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)但沒(méi)有邊的圖 */ 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)對(duì)鄰接表存儲(chǔ)的圖Graph進(jìn)行DFS搜索 */ PtrToAdjVNode W;

37、if(x = 1) clrv(Graph); x+; coutVGV.FirstEdge; W != NULL; W=W-Next ) /* 對(duì)V的每個(gè)鄰接點(diǎn)W-AdjV */ if ( !VisitedW-AdjV ) /* 若W-AdjV未被訪問(wèn) */ DFS( Graph, W-AdjV,x); /* 則遞歸訪問(wèn)之 */* 鄰接表存儲(chǔ) - 無(wú)權(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 ) /* 對(duì)V的每個(gè)鄰接點(diǎn)W-AdjV */ if ( distW-AdjV=-1 ) /* 若W-AdjV未被訪問(wèn)過(guò) */ 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; / 鄰接表存儲(chǔ) - 有權(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; /* 更新對(duì)應(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 ) /* 對(duì)V的每個(gè)鄰接點(diǎn)W-AdjV */ if ( collectedW-AdjV = false ) /* 若W-AdjV未被訪