數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)--圖-展示頁(yè)
2024-11-15 22:14本頁(yè)面
【正文】 ][i]。i vnum。(VU)的最小權(quán)值邊第6頁(yè) 北京郵電大學(xué)信息與通信工程學(xué)院第7頁(yè) 北京郵電大學(xué)信息與通信工程學(xué)院3。// U集中的頂點(diǎn)序號(hào)第5頁(yè) 北京郵電大學(xué)信息與通信工程學(xué)院intlowcost[MAXSIZE]。//當(dāng)存在回路時(shí)，則連通深一層遍歷} 時(shí)間復(fù)雜度：O(n2)空間復(fù)雜度：棧的深度O(n)輔助空間O(n)第4頁(yè) 北京郵電大學(xué)信息與通信工程學(xué)院三．廣度遍歷BFS ①訪問(wèn)頂點(diǎn)v ②依次訪問(wèn)v的所有未被訪問(wèn)的鄰接點(diǎn)v1,v2,v3…③分別從v1,v2,v3…出發(fā)依次訪問(wèn)它們未被訪問(wèn)的鄰接點(diǎn) ④反復(fù)①②③，直到所有和v路徑相通的頂點(diǎn)都被訪問(wèn)到；，visited[v]=1(隊(duì)列非空) v=隊(duì)頭元素出隊(duì) 訪問(wèn)隊(duì)頭元素的所有未訪問(wèn)的鄰接點(diǎn) 時(shí)間復(fù)雜度：O(n2)空間復(fù)雜度：輔助空間O(n)——普里姆算法1,關(guān)鍵思路一般情況下，假設(shè)n個(gè)頂點(diǎn)分成兩個(gè)集合：U(包含已落在生成樹(shù)上的結(jié)點(diǎn))和VU(尚未落在生成樹(shù)上的頂點(diǎn))，則在所有連通U中頂點(diǎn)和VU中頂點(diǎn)的邊中選取權(quán)值最小的邊。amp。j vnum。i n。//采用無(wú)向圖帶權(quán)值的鄰接矩陣} cout for(k = 0。arc[convert(s1)][convert(s2)] = height。//初始化權(quán)值的大小}visited[k] = 0。i++){arc[k][i] =1。kfor(i = 0。k++){ vertex[k] = a[k]。for(k = 0。vnum = n。 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)：1．不帶權(quán)值的無(wú)向圖鄰接矩陣第1頁(yè) 北京郵電大學(xué)信息與通信工程學(xué)院[備注]：、BFS、DFS 采用無(wú)權(quán)值的無(wú)向圖鄰接矩陣存儲(chǔ)方式 、KRUSKAL、 關(guān)鍵算法分析第2頁(yè) 北京郵電大學(xué)信息與通信工程學(xué)院一．圖的鄰接矩陣構(gòu)造函數(shù)：： template Graph::Graph(f a[], int n, int e)//帶權(quán)值的圖的構(gòu)造函數(shù) { int i, j, k, height。四）高級(jí)應(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)鍵路徑算法第二篇：數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)一 圖[推薦]北京郵電大學(xué)信息與通信工程學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱： 實(shí)驗(yàn)二——圖 學(xué)生姓名： 佘晨陽(yáng) 班級(jí)： 2014211117 班內(nèi)序號(hào)： 20 學(xué)號(hào)： 2014210491 日期： 2015年12月05日1．實(shí)驗(yàn)要求根據(jù)圖的抽象數(shù)據(jù)類型的定義，使用鄰接矩陣或鄰接表實(shí)現(xiàn)一個(gè)圖。如果不連通，求連通分量的個(gè)數(shù)（3）編寫(xiě)算法，判斷圖中任意兩個(gè)頂點(diǎn)的連通性（4）編寫(xiě)算法，判斷圖中是否存在回路。題目:一)建立一個(gè)無(wú)向圖+遍歷+插入(1)以數(shù)組表示法作為存儲(chǔ)結(jié)構(gòu)，從鍵盤(pán)依次輸入頂點(diǎn)數(shù)、弧數(shù)與各弧信息建立一個(gè)無(wú)向圖；(2)對(duì)（1）中生成的無(wú)向圖進(jìn)行廣度優(yōu)先遍歷并打印結(jié)果；(3)向（1）中生成的無(wú)向圖插入一條新弧并打印結(jié)果；二)建立一個(gè)有向圖+遍歷+插入+刪除(1)以鄰接表作為圖的存儲(chǔ)結(jié)構(gòu)，從鍵盤(pán)輸入圖的頂點(diǎn)與弧的信息建立一個(gè)有向圖；(2)對(duì)（1）中生成的有向圖進(jìn)行深度優(yōu)先遍歷并打印結(jié)果；(3)在（1）中生成的有向圖中，分別插入與刪除一條弧并打印其結(jié)果；(4)在（1）中生成的有向圖中，分別插入與刪除一個(gè)頂點(diǎn)并打印結(jié)果；(5)在（1）中生成的有向圖中,各頂點(diǎn)的入度與出度并打印結(jié)果；三）基本應(yīng)用題（1）編寫(xiě)算法，判斷圖中指定的兩個(gè)頂點(diǎn)是否連通。第一篇：數(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++基本編程,)通過(guò)實(shí)驗(yàn),：1)只完成第一和第二題，根據(jù)情況得4，5分；2）完成前3題，根據(jù)情況得5至7分；3）在2）基礎(chǔ)上，選做四）中題目，根據(jù)情況得8至10分。（2）編寫(xiě)算法，判斷圖的連通性。（5）實(shí)現(xiàn)圖的廣度優(yōu)先搜索算法。圖的基本功能：圖的建立圖的銷毀深度優(yōu)先遍歷圖廣度優(yōu)先遍歷圖使用普里姆算法生成最小生成樹(shù)使用克魯斯卡爾算法生成最小生成樹(shù)求指定頂點(diǎn)到其他各頂點(diǎn)的最短路徑其他：比如連通性判斷等自定義操作編寫(xiě)測(cè)試main()函數(shù)測(cè)試圖的正確性本實(shí)驗(yàn)要求掌握?qǐng)D基本操作的實(shí)現(xiàn)方法，了解最小生成樹(shù)的思想和相關(guān)概念，了解最短路徑的思想和相關(guān)概念，學(xué)習(xí)使用圖解決實(shí)際問(wèn)題的能力。f s1, s2。arum = e。k n。}//初始化頂點(diǎn)for(k = 0。i n。if(i == k)arc[k][i] = 0。} cout //初始化邊{cout cin s1 s2 height。arc[convert(s2)][convert(s1)] = arc[convert(s1)][convert(s2)]。kfor(i = 0。i++){if(arc[k][i] ==1)cout else cout //打印鄰接矩陣的格式}cout } cout 第3頁(yè) 北京郵電大學(xué)信息與通信工程學(xué)院有構(gòu)造可知，初始化時(shí)其時(shí)間復(fù)雜度：O(n2)二．深度優(yōu)先便利DFS:①?gòu)哪稠旤c(diǎn)v出發(fā)并訪問(wèn)②訪問(wèn)v的第一個(gè)未訪問(wèn)的鄰接點(diǎn)w，訪問(wèn)w的第一個(gè)未訪問(wèn)的鄰接點(diǎn)u，……③若當(dāng)前頂點(diǎn)的所有鄰接點(diǎn)都被訪問(wèn)過(guò)，則回溯，從上一級(jí)頂點(diǎn)的下一個(gè)未訪問(wèn)過(guò)的頂點(diǎn)開(kāi)始深度優(yōu)先遍歷④直到所有和v路徑相通的頂點(diǎn)都被訪問(wèn)到； ：深度優(yōu)先遍歷示意圖 ：template void Graph::DFS(int v){ cout for(int j = 0。j++)//連通圖if((visited[j] == 0)amp。(arc[v][j] = 1))DFS(j)。主數(shù)據(jù)結(jié)構(gòu)：鄰接矩陣 輔助數(shù)據(jù)結(jié)構(gòu)：intadjvex[MAXSIZE]。// U224。代碼詳解template void Graph::Prim(){ for(int i = 0。i++)//輔助數(shù)組存儲(chǔ)所有到的V0邊{adjvex[i] = 0。} lowcost[0] = 0。j vnum。//求下一個(gè)頂點(diǎn)cout ” lowcost[k] = 0。j vnum。amp。adjvex[j] = k。：template void Graph::Kruskal()//最小生成樹(shù)—kruskal算法{ coutint k = 0, j = 0。int sn1 = vset[m]。//兩個(gè)頂點(diǎn)分屬第9頁(yè) 北京郵電大學(xué)信息與通信工程學(xué)院不同的集合 if(sn1!= sn2){cout ” k++。i vnum。//集合sn2全部改成sn1}}j++。? 1)設(shè)置集合s存儲(chǔ)已求得的最短路徑的頂點(diǎn)，? 2)初始狀態(tài)：s=源點(diǎn)v ? 3)疊代算法：? 直接與v相連的最近頂點(diǎn)vi,加入s ? 從v經(jīng)過(guò)vi可以到達(dá)的頂點(diǎn)中最短的，加入s……第10頁(yè) 北京郵電大學(xué)信息與通信工程學(xué)院emplate void Graph::ShotPath(f x)//關(guān)于最短路徑的初始化 { int v=convert(x)。i vnum。disk[i] = arc[v][i]。else path[i] =1。disk[v] = 0。for(int i = 0。i++)//反復(fù)經(jīng)過(guò)從該點(diǎn)到其他點(diǎn)的路徑{if((v = FindMin())==1)continue。for(int j = 0。j++)if(!s[j] amp。(disk[j]arc[v][j] + disk[v])){第11頁(yè) 北京郵電大學(xué)信息與通信工程學(xué)院disk[j] = arc[v][j] + disk[v]。
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1