數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)一圖[推薦]-文庫吧
2025-10-30 18:01 本頁面
【正文】 = 0。i vnum。i++){if(vset[i] == sn2)vset[i] = sn1。//集合sn2全部改成sn1}}j++。} } 時(shí)間復(fù)雜度O(nlogn)，適合稀疏圖六．最短路徑——Dijkstra算法 ? 按路徑長度遞增的次序產(chǎn)生源點(diǎn)到其余各頂點(diǎn)的最短路徑。? 1)設(shè)置集合s存儲已求得的最短路徑的頂點(diǎn)，? 2)初始狀態(tài)：s=源點(diǎn)v ? 3)疊代算法：? 直接與v相連的最近頂點(diǎn)vi,加入s ? 從v經(jīng)過vi可以到達(dá)的頂點(diǎn)中最短的，加入s……第10頁 北京郵電大學(xué)信息與通信工程學(xué)院emplate void Graph::ShotPath(f x)//關(guān)于最短路徑的初始化 { int v=convert(x)。for(int i = 0。i vnum。i++)//初始化路徑和點(diǎn){s[i]=0。disk[i] = arc[v][i]。if(disk[i]!= maxs)path[i] = v。else path[i] =1。} s[v] = 1。disk[v] = 0。path[v]=1。for(int i = 0。i vnum。i++)//反復(fù)經(jīng)過從該點(diǎn)到其他點(diǎn)的路徑{if((v = FindMin())==1)continue。s[v] = 1。for(int j = 0。j vnum。j++)if(!s[j] amp。amp。(disk[j]arc[v][j] + disk[v])){第11頁 北京郵電大學(xué)信息與通信工程學(xué)院disk[j] = arc[v][j] + disk[v]。path[j] = v。} } Print()。//打印路徑長度和遍歷} 時(shí)間復(fù)雜度為：n^2七．判斷連通圖算法template bool Graph::judgegraph(){ DFS(convert(vertex[0]))。if(count==vnum){coutreturn false。} else {coutreturn true。} }時(shí)間復(fù)雜度：n^2：第12頁 北京郵電大學(xué)信息與通信工程學(xué)院函數(shù)流程圖：構(gòu)造下面所示圖的鄰接矩陣：第13頁 北京郵電大學(xué)信息與通信工程學(xué)院 DFS PRIM算法的實(shí)現(xiàn)第14頁 北京郵電大學(xué)信息與通信工程學(xué)院第15頁 北京郵電大學(xué)信息與通信工程學(xué)院插入V0位置后打印距離并開始回溯總結(jié)問題一：prim算法中解決方法：調(diào)整循環(huán)條件，修正函數(shù)體注意有無Next的區(qū)別第16頁 北京郵電大學(xué)信息與通信工程學(xué)院問題二：BFS和DFS同時(shí)在一個(gè)類里作用時(shí)會(huì)輸出錯(cuò)誤解決方案：每次BFS/DFS使用時(shí)都把visited數(shù)組初始化一遍問題三：在最短路徑，經(jīng)常出現(xiàn)了停止輸入的情況解決方法：改return為continue，并修改打印算法 通過本次實(shí)驗(yàn)，基本熟練掌握了c++基本語句，尤其對圖的結(jié)構(gòu)及應(yīng)用有了較深了解；調(diào)試代碼時(shí)盡量做到完成一個(gè)代碼段調(diào)試一次，可以最快檢測出錯(cuò)誤所在；類的封裝和調(diào)用，類的共有成員和私有成員的設(shè)置。第一，設(shè)置增加圖節(jié)點(diǎn)和邊的函數(shù)第二，實(shí)現(xiàn)圖形化輸出圖的路徑的功能第三，主函數(shù)設(shè)計(jì)簡單，不要過于累贅1)利用dfs算法衍生生成判斷是否為連通圖的連通算法2)采用graph類實(shí)現(xiàn)所有圖的所有算法，所需的數(shù)據(jù)類型均在私有成員內(nèi)，封裝 3)利用convert函數(shù)采取象意輸入，采用ABCD的節(jié)點(diǎn)輸入方式而并非轉(zhuǎn)化成01234再輸入。4)BFS中采用c++標(biāo)準(zhǔn)庫的。5)打印鄰接矩陣時(shí)，打印出非鏈接的∞符號和與自身路徑的0距離 6)判斷圖為非連通圖后，提示輸入錯(cuò)誤，重新輸入圖元素第17頁第二篇：數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)圖數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)六實(shí)驗(yàn)內(nèi)容:圖的基本操作實(shí)驗(yàn)要求:1)))：可單獨(dú)完成，也可兩人一組。實(shí)驗(yàn)?zāi)康?1)熟悉C/C++基本編程,)通過實(shí)驗(yàn),：1)只完成第一和第二題，根據(jù)情況得4，5分；2）完成前3題，根據(jù)情況得5至7分；3）在2）基礎(chǔ)上，選做四）中題目，根據(jù)情況得8至10分。題目:一)建立一個(gè)無向圖+遍歷+插入(1)以數(shù)組表示法作為存儲結(jié)構(gòu)，從鍵盤依次輸入頂點(diǎn)數(shù)、弧數(shù)與各弧信息建立一個(gè)無向圖；(2)對（1）中生成的無向圖進(jìn)行廣度優(yōu)先遍歷并打印結(jié)果；(3)向（1）中生成的無向圖插入一條新弧并打印結(jié)果；二)建立一個(gè)有向圖+遍歷+插入+刪除(1)以鄰接表作為圖的存儲結(jié)構(gòu)，從鍵盤輸入圖的頂點(diǎn)與弧的信息建立一個(gè)有向圖；(2)對（1）中生成的有向圖進(jìn)行深度優(yōu)先遍歷并打印結(jié)果；(3)在（1）中生成的有向圖中，分別插入與刪除一條弧并打印其結(jié)果；(4)在（1）中生成的有向圖中，分別插入與刪除一個(gè)頂點(diǎn)并打印結(jié)果；(5)在（1）中生成的有向圖中,各頂點(diǎn)的入度與出度并打印結(jié)果；三）基本應(yīng)用題（1）編寫算法，判斷圖中指定的兩個(gè)頂點(diǎn)是否連通。（2）編寫算法，判斷圖的連通性。如果不連通，求連通分量的個(gè)數(shù)（3）編寫算法，判斷圖中任意兩個(gè)頂點(diǎn)的連通性（4）編寫算法，判斷圖中是否存在回路。（5）實(shí)現(xiàn)圖的廣度優(yōu)先搜索算法。四）高級應(yīng)用題（1）實(shí)現(xiàn)Prim算法（2）實(shí)現(xiàn)Kruskal算法（3）實(shí)現(xiàn)迪杰斯特拉算法（4）實(shí)現(xiàn)拓?fù)渑判蛩惴ǎ?）實(shí)現(xiàn)關(guān)鍵路徑算法第三篇：北化航天工業(yè)學(xué)院~數(shù)據(jù)結(jié)構(gòu)~實(shí)驗(yàn)5圖實(shí)驗(yàn)五：圖的應(yīng)用班級學(xué)號姓名一、實(shí)驗(yàn)預(yù)備知識復(fù)習(xí)C++中的全局變量的概念。復(fù)習(xí)圖的鄰接矩陣和鄰接表兩種存儲方式。復(fù)習(xí)圖的兩種遍歷方法和求圖的最小生成樹的方法。二、實(shí)驗(yàn)?zāi)康恼莆請D的鄰接矩陣和鄰接表兩種存儲方法。掌握有關(guān)圖的操作算法并用高級語言實(shí)現(xiàn)。熟悉圖的構(gòu)造算法，了解實(shí)際問題的求解效率與采用何種存儲結(jié)構(gòu)與算法有著密切聯(lián)系。掌握圖的兩種搜索路徑的遍歷算法。掌握求圖的最小生成樹的普里姆算法和克魯斯卡爾算法。三、實(shí)驗(yàn)內(nèi)容創(chuàng)建給定的圖，從鄰接表和鄰接矩陣兩種存儲方式中選擇一種。對所創(chuàng)建的圖進(jìn)行深度和廣度優(yōu)先搜索遍歷，給出遍歷過程中的頂點(diǎn)序列。3 求圖的最小生成樹，按構(gòu)造順序輸出邊的序列。編寫一個(gè)主函數(shù)，將上面函數(shù)連在一起，構(gòu)成一個(gè)完整程序。將實(shí)驗(yàn)源程序調(diào)試并運(yùn)行。四、實(shí)驗(yàn)要求所建立的圖為：l 用鄰接表存儲結(jié)構(gòu)時(shí)，所創(chuàng)建的單鏈表以結(jié)點(diǎn)
職業(yè)教育相關(guān)推薦
鄂ICP備17016276號-1