數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)一圖[推薦](已修改)
2025-11-08 18:01 本頁(yè)面
【正文】 第一篇：數(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)先遍歷圖使用普里姆算法生成最小生成樹使用克魯斯卡爾算法生成最小生成樹求指定頂點(diǎn)到其他各頂點(diǎn)的最短路徑其他：比如連通性判斷等自定義操作編寫測(cè)試main()函數(shù)測(cè)試圖的正確性本實(shí)驗(yàn)要求掌握?qǐng)D基本操作的實(shí)現(xiàn)方法，了解最小生成樹的思想和相關(guān)概念，了解最短路徑的思想和相關(guān)概念，學(xué)習(xí)使用圖解決實(shí)際問題的能力。 存儲(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。f s1, s2。vnum = n。arum = e。for(k = 0。k n。k++){ vertex[k] = a[k]。}//初始化頂點(diǎn)for(k = 0。kfor(i = 0。i n。i++){arc[k][i] =1。if(i == k)arc[k][i] = 0。//初始化權(quán)值的大小}visited[k] = 0。} cout //初始化邊{cout cin s1 s2 height。arc[convert(s1)][convert(s2)] = height。arc[convert(s2)][convert(s1)] = arc[convert(s1)][convert(s2)]。//采用無(wú)向圖帶權(quán)值的鄰接矩陣} cout for(k = 0。kfor(i = 0。i n。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ā)并訪問②訪問v的第一個(gè)未訪問的鄰接點(diǎn)w，訪問w的第一個(gè)未訪問的鄰接點(diǎn)u，……③若當(dāng)前頂點(diǎn)的所有鄰接點(diǎn)都被訪問過，則回溯，從上一級(jí)頂點(diǎn)的下一個(gè)未訪問過的頂點(diǎn)開始深度優(yōu)先遍歷④直到所有和v路徑相通的頂點(diǎn)都被訪問到； ：深度優(yōu)先遍歷示意圖 ：template void Graph::DFS(int v){ cout for(int j = 0。j vnum。j++)//連通圖if((visited[j] == 0)amp。amp。(arc[v][j] = 1))DFS(j)。//當(dāng)存在回路時(shí)，則連通深一層遍歷} 時(shí)間復(fù)雜度：O(n2)空間復(fù)雜度：棧的深度O(n)輔助空間O(n)第4頁(yè) 北京郵電大學(xué)信息與通信工程學(xué)院三．廣度遍歷BFS ①訪問頂點(diǎn)v ②依次訪問v的所有未被訪問的鄰接點(diǎn)v1,v2,v3…③分別從v1,v2,v3…出發(fā)依次訪問它們未被訪問的鄰接點(diǎn) ④反復(fù)①②③，直到所有和v路徑相通的頂點(diǎn)都被訪問到；，visited[v]=1(隊(duì)列非空) v=隊(duì)頭元素出隊(duì) 訪問隊(duì)頭元素的所有未訪問的鄰接點(diǎn) 時(shí)間復(fù)雜度：O(n2)空間復(fù)雜度：輔助空間O(n)——普里姆算法1,關(guān)鍵思路一般情況下，假設(shè)n個(gè)頂點(diǎn)分成兩個(gè)集合：U(包含已落在生成樹上的結(jié)點(diǎn))和VU(尚未落在生成樹上的頂點(diǎn))，則在所有連通U中頂點(diǎn)和VU中頂點(diǎn)的邊中選取權(quán)值最小的邊。主數(shù)據(jù)結(jié)構(gòu)：鄰接矩陣 輔助數(shù)據(jù)結(jié)構(gòu)：intadjvex[MAXSIZE]。// U集中的頂點(diǎn)序號(hào)第5頁(yè) 北京郵電大學(xué)信息與通信工程學(xué)院intlowcost[MAXSIZE]。// U224。(VU)的最小權(quán)值邊第6頁(yè) 北京郵電大學(xué)信息與通信工程學(xué)院第7頁(yè) 北京郵電大學(xué)信息與通信工程學(xué)院3。代碼詳解template void Graph::Prim(){ for(int i = 0。i vnum。i++)//輔助數(shù)組存儲(chǔ)所有到的V0邊{adjvex[i] = 0。lowcost[i] = arc[0][i]。} lowcost[0] = 0。for(int j = 1。j vnum。j++)//循環(huán)n1次{int k = Mininum(lowcost)。//求下一個(gè)頂點(diǎn)cout ” lowcost[k] = 0。//U=U+{Vk}for(int j = 0。j vnum。j++)//設(shè)置輔助數(shù)組{if((lowcost[j]!= 0 amp。amp。 arc[k][j] lowcost[j])){lowcost[j] = arc[k][j]。adjvex[j] = k。}}第8頁(yè) 北京郵電大學(xué)信息與通信工程學(xué)院} } 4,時(shí)間復(fù)雜度：時(shí)間復(fù)雜度O(n2)，適合稠密圖1,關(guān)鍵思路先構(gòu)造一個(gè)只含n個(gè)頂點(diǎn)的子圖SG，然后從權(quán)值最小的邊開始，若它的添加不使SG中產(chǎn)生回路，則在SG上加上這條邊，如此重復(fù)，直至加上n1條邊為止。：template void Graph::Kruskal()//最小生成樹—kruskal算法{ coutint k = 0, j = 0。while(k vnum1){int m = vedgelist[j].fromv, n = vedgelist[j].endv。int sn1 = vset[m]。int sn2 = vset[n]。//兩個(gè)頂點(diǎn)分屬第9頁(yè) 北京郵電大學(xué)信息與通信工程學(xué)院不同的集合 if(sn1!= sn2){cout ” k++。for(int i
職業(yè)教育相關(guān)推薦
鄂ICP備17016276號(hào)-1