數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)一圖剖析

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱(chēng)： 實(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ù)類(lèi)型的定義，使用鄰接矩陣或鄰接表實(shí)現(xiàn)一個(gè)圖。圖的基本功能：1、圖的建立2、圖的銷(xiāo)毀3、深度優(yōu)先遍歷圖4、廣度優(yōu)先遍歷圖5、使用普里姆算法生成最小生成樹(shù)6、使用克魯斯卡爾算法生成最小生成樹(shù)7、求指定頂點(diǎn)到其他各頂點(diǎn)的最短路徑8、其他：比如連通性判斷等自定義操作編寫(xiě)測(cè)試main()函數(shù)測(cè)試圖的正確性2. 程序分析 本實(shí)驗(yàn)要求掌握?qǐng)D基本操作的實(shí)現(xiàn)方法，了解最小生成樹(shù)的思想和相關(guān)概念，了解最短路徑的思想和相關(guān)概念，學(xué)

2、習(xí)使用圖解決實(shí)際問(wèn)題的能力。2.1 存儲(chǔ)結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu)：1.不帶權(quán)值的無(wú)向圖鄰接矩陣 2.帶權(quán)值的無(wú)向圖鄰接矩陣 3.帶權(quán)值的有向圖鄰接矩陣 1不帶權(quán)值的無(wú)向圖鄰接矩陣2帶權(quán)值的無(wú)向圖鄰接矩陣.3.帶權(quán)值的有向圖鄰接矩陣備注：1. 在使用打印元素、BFS、DFS 采用無(wú)權(quán)值的無(wú)向圖鄰接矩陣存儲(chǔ)方式2. 在使用PRIM、KRUSKAL、3. 在使用最短路徑的算法時(shí)采用具有權(quán)值的有向圖鄰接矩陣存儲(chǔ)方式2.2 關(guān)鍵算法分析一圖的鄰接矩陣構(gòu)造函數(shù)：1.關(guān)鍵算法：template<class f>Graph<f>:Graph(f a, int n, int e) /帶權(quán)值的圖的構(gòu)

3、造函數(shù)int i, j, k, height;f s1, s2;vnum = n;arcnum = e;for (k = 0; k < n; k+) vertexk = ak; /初始化頂點(diǎn)for (k = 0; k<n; k+)for (i = 0; i < n; i+)arcki = -1;if (i = k) arcki = 0; /初始化權(quán)值的大小visitedk = 0;cout << endl;for (k = 0; k<e; k+) /初始化邊cout << "請(qǐng)輸入線(xiàn)性鏈接節(jié)點(diǎn):"cin >> s1

4、 >> s2 >> height;arcconvert(s1)convert(s2) = height;arcconvert(s2)convert(s1) = arcconvert(s1)convert(s2); /采用無(wú)向圖帶權(quán)值的鄰接矩陣cout << endl;cout << "所得鄰接矩陣為：" << endl; for (k = 0; k<n; k+)for (i = 0; i < n; i+)if (arcki = -1)cout << "" <<

5、 " "else cout << arcki << " " /打印鄰接矩陣的格式cout << endl;cout << endl2.算法的時(shí)間復(fù)雜度有構(gòu)造可知，初始化時(shí)其時(shí)間復(fù)雜度：O(n2)二深度優(yōu)先便利DFS:1.關(guān)鍵算法從某頂點(diǎn)v出發(fā)并訪(fǎng)問(wèn)訪(fǎng)問(wèn)v的第一個(gè)未訪(fǎng)問(wèn)的鄰接點(diǎn)w， 訪(fǎng)問(wèn)w的第一個(gè)未訪(fǎng)問(wèn)的鄰接點(diǎn)u， 若當(dāng)前頂點(diǎn)的所有鄰接點(diǎn)都被訪(fǎng)問(wèn)過(guò)，則回溯，從上一級(jí)頂點(diǎn)的下一個(gè)未訪(fǎng)問(wèn)過(guò)的頂點(diǎn)開(kāi)始深度優(yōu)先遍歷直到所有和v路徑相通的頂點(diǎn)都被訪(fǎng)問(wèn)到；2.代碼圖解：深度優(yōu)先遍歷示意圖3.代碼詳解：template&l

6、t;class f>void Graph<f>:DFS(int v)cout << vertexv;visitedv = 1; for (int j = 0; j < vnum; j+) /連通圖 if (visitedj = 0) && (arcvj >= 1) DFS(j); /當(dāng)存在回路時(shí)，則連通深一層遍歷 4.時(shí)間復(fù)雜度 時(shí)間復(fù)雜度：O(n2)空間復(fù)雜度：棧的深度O(n)輔助空間O(n)三廣度遍歷BFS1.關(guān)鍵算法訪(fǎng)問(wèn)頂點(diǎn)v依次訪(fǎng)問(wèn)v的所有未被訪(fǎng)問(wèn)的鄰接點(diǎn)v1,v2,v3分別從v1,v2,v3出發(fā)依次訪(fǎng)問(wèn)它們未被訪(fǎng)問(wèn)的鄰接點(diǎn)反復(fù)

7、 ，直到所有和v路徑相通的頂點(diǎn)都被訪(fǎng)問(wèn)到；2.代碼圖解3.代碼詳解1.初始化隊(duì)列Q 2.訪(fǎng)問(wèn)頂點(diǎn)v， visitedv=1 3. while(隊(duì)列非空) 3.1 v=隊(duì)頭元素出隊(duì) 3.2 訪(fǎng)問(wèn)隊(duì)頭元素的所有未訪(fǎng)問(wèn)的鄰接點(diǎn)4.時(shí)間復(fù)雜度 時(shí)間復(fù)雜度：O(n2) 空間復(fù)雜度：輔助空間O(n)四.最小生成樹(shù)普里姆算法1,關(guān)鍵思路一般情況下，假設(shè)n個(gè)頂點(diǎn)分成兩個(gè)集合：U(包含已落在生成樹(shù)上的結(jié)點(diǎn))和V-U(尚未落在生成樹(shù)上的頂點(diǎn))，則在所有連通U中頂點(diǎn)和V-U中頂點(diǎn)的邊中選取權(quán)值最小的邊。主數(shù)據(jù)結(jié)構(gòu)： 鄰接矩陣輔助數(shù)據(jù)結(jié)構(gòu)： int adjvexMAXSIZE; / U集中的頂點(diǎn)序號(hào) int lowc

8、ostMAXSIZE; / Uà(V-U)的最小權(quán)值邊2.代碼圖解 3;代碼詳解template<class f>void Graph<f>:Prim()for (int i = 0; i < vnum; i+) /輔助數(shù)組存儲(chǔ)所有到的V0邊adjvexi = 0; lowcosti = arc0i; lowcost0 = 0;for (int j = 1; j < vnum; j+) /循環(huán)n-1次int k = Mininum(lowcost); /求下一個(gè)頂點(diǎn)cout << vertexadjvexk << "

9、;->" << vertexk << endl; lowcostk = 0; /U=U+Vkfor (int j = 0; j < vnum; j+) /設(shè)置輔助數(shù)組 if (lowcostj != 0 && arckj < lowcostj)lowcostj = arckj;adjvexj = k;4,時(shí)間復(fù)雜度：時(shí)間復(fù)雜度O(n2)，適合稠密圖五.最小生成樹(shù)-克魯斯卡爾算法1,關(guān)鍵思路先構(gòu)造一個(gè)只含n個(gè)頂點(diǎn)的子圖SG，然后從權(quán)值最小的邊開(kāi)始，若它的添加不使SG中產(chǎn)生回路，則在SG上加上這條邊，如此重復(fù)，直至加上n-1條邊為

10、止。2.代碼圖解： 3.代碼詳解template<class f>void Graph<f>:Kruskal() /最小生成樹(shù)kruskal算法 cout<<"Krusal算法結(jié)果為："<<endl;int vsetMAXSIZE;for (int i = 0; i < vnum; i+) vseti = i; int k = 0, j = 0; while (k < vnum - 1)int m = vedgelistj.fromv, n = vedgelistj.endv;int sn1 = vsetm;int

11、 sn2 = vsetn; /兩個(gè)頂點(diǎn)分屬不同的集合if (sn1 != sn2)cout << vertexm << "->" << vertexn << endl;k+;for (int i = 0; i < vnum; i+)if (vseti = sn2)vseti = sn1; /集合sn2全部改成sn1j+;4.時(shí)間復(fù)雜度 時(shí)間復(fù)雜度O(nlogn)，適合稀疏圖六最短路徑Dijkstra算法1.關(guān)鍵代碼 按路徑長(zhǎng)度遞增的次序產(chǎn)生源點(diǎn)到其余各頂點(diǎn)的最短路徑。 1)設(shè)置集合s存儲(chǔ)已求得的最短路徑的頂點(diǎn)， 2

12、)初始狀態(tài)：s=源點(diǎn)v 3)疊代算法： 直接與v相連的最近頂點(diǎn)vi,加入s 從v經(jīng)過(guò)vi可以到達(dá)的頂點(diǎn)中最短的，加入s 2.代碼圖解3.代碼詳解emplate<class f>void Graph<f>:ShotPath(f x) /關(guān)于最短路徑的初始化int v=convert(x); for (int i = 0; i < vnum; i+) /初始化路徑和點(diǎn) si=0; diski = arcvi;if (diski != maxs) pathi = v; else pathi = -1;sv = 1; diskv = 0;pathv=-1;for (int

13、 i = 0; i < vnum; i+) /反復(fù)經(jīng)過(guò)從該點(diǎn)到其他點(diǎn)的路徑 if (v = FindMin() = -1) continue; sv = 1;for (int j = 0; j < vnum; j+)if (!sj && (diskj>arcvj + diskv)diskj = arcvj + diskv;pathj = v;Print(); /打印路徑長(zhǎng)度和遍歷 4.時(shí)間復(fù)雜度時(shí)間復(fù)雜度為：n2七判斷連通圖算法template<class f>bool Graph<f>:judgegraph()DFS(convert(

14、vertex0);if(count=vnum) cout<<"該圖為連通圖！*輸入成功！"<<endl; return false; else cout<<"該圖不為連通圖！*請(qǐng)重新輸入"<<endl; return true; 時(shí)間復(fù)雜度：n23. 程序運(yùn)行結(jié)果 1. 測(cè)試主函數(shù)流程：函數(shù)流程圖：1. 輸入圖的連接邊并打印構(gòu)造下面所示圖的鄰接矩陣： 2.判斷圖連通是否成功3.BFS DFS PRIM算法的實(shí)現(xiàn)4.克魯斯卡爾算法實(shí)現(xiàn)過(guò)程4. 有向圖鄰接矩陣的構(gòu)建插入V0位置后打印距離并開(kāi)始回溯總結(jié)1.調(diào)試時(shí)出現(xiàn)的問(wèn)題及解決的方法 問(wèn)題一：prim算法中 解決方法：調(diào)整循環(huán)條件，修正函數(shù)體注意有無(wú)Next的區(qū)別 問(wèn)題二：BFS和DFS同時(shí)在一個(gè)類(lèi)里作用時(shí)會(huì)輸出錯(cuò)誤 解決方案：每次BFS/DFS使用時(shí)都把visited數(shù)組初始化一遍 問(wèn)題三：在最短路徑，經(jīng)常出現(xiàn)了停止輸入的情況 解決方法：改return為continue，并修改打印算法2.心得體會(huì) 通過(guò)本次實(shí)驗(yàn)，基本熟練掌握了c+基本語(yǔ)句，尤其對(duì)圖的結(jié)構(gòu)及應(yīng)用有了較深了解；調(diào)試代碼時(shí)盡量做到完成一個(gè)代碼段調(diào)試一次，可以最快檢測(cè)出錯(cuò)誤所在；類(lèi)的封裝和調(diào)用，類(lèi)的共有成員和私有成員的設(shè)置。3.下一步的改進(jìn) 第一，設(shè)置增加圖節(jié)點(diǎn)和邊的