數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)一圖[推薦]-展示頁(yè)
2024-11-13 18:01本頁(yè)面
【正文】 ath[v]=1。} s[v] = 1。if(disk[i]!= maxs)path[i] = v。i++)//初始化路徑和點(diǎn){s[i]=0。for(int i = 0。} } 時(shí)間復(fù)雜度O(nlogn)，適合稀疏圖六．最短路徑——Dijkstra算法 ? 按路徑長(zhǎng)度遞增的次序產(chǎn)生源點(diǎn)到其余各頂點(diǎn)的最短路徑。i++){if(vset[i] == sn2)vset[i] = sn1。for(int i = 0。int sn2 = vset[n]。while(k vnum1){int m = vedgelist[j].fromv, n = vedgelist[j].endv。}}第8頁(yè) 北京郵電大學(xué)信息與通信工程學(xué)院} } 4,時(shí)間復(fù)雜度：時(shí)間復(fù)雜度O(n2)，適合稠密圖1,關(guān)鍵思路先構(gòu)造一個(gè)只含n個(gè)頂點(diǎn)的子圖SG，然后從權(quán)值最小的邊開(kāi)始，若它的添加不使SG中產(chǎn)生回路，則在SG上加上這條邊，如此重復(fù)，直至加上n1條邊為止。 arc[k][j] lowcost[j])){lowcost[j] = arc[k][j]。j++)//設(shè)置輔助數(shù)組{if((lowcost[j]!= 0 amp。//U=U+{Vk}for(int j = 0。j++)//循環(huán)n1次{int k = Mininum(lowcost)。for(int j = 1。lowcost[i] = arc[0][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。第一篇：數(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è)圖。圖的基本功能：圖的建立圖的銷毀深度優(yōu)先遍歷圖廣度優(yōu)先遍歷圖使用普里姆算法生成最小生成樹(shù)使用克魯斯卡爾算法生成最小生成樹(shù)求指定頂點(diǎn)到其他各頂點(diǎn)的最短路徑其他：比如連通性判斷等自定義操作編寫測(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)
職業(yè)教育相關(guān)推薦
鄂ICP備17016276號(hào)-1