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

1、數(shù)據(jù)結(jié)構(gòu)實驗報告實驗名稱： 實驗二圖學生姓名： 佘晨陽班 級： 2014211117班內(nèi)序號： 20學 號： 2014210491日 期： 2015年12月05日1實驗要求根據(jù)圖的抽象數(shù)據(jù)類型的定義，使用鄰接矩陣或鄰接表實現(xiàn)一個圖。圖的基本功能：1、圖的建立2、圖的銷毀3、深度優(yōu)先遍歷圖4、廣度優(yōu)先遍歷圖5、使用普里姆算法生成最小生成樹6、使用克魯斯卡爾算法生成最小生成樹7、求指定頂點到其他各頂點的最短路徑8、其他：比如連通性判斷等自定義操作編寫測試main()函數(shù)測試圖的正確性2. 程序分析 本實驗要求掌握圖基本操作的實現(xiàn)方法，了解最小生成樹的思想和相關(guān)概念，了解最短路徑的思想和相關(guān)概念，學

2、習使用圖解決實際問題的能力。2.1 存儲結(jié)構(gòu) 存儲結(jié)構(gòu)：1.不帶權(quán)值的無向圖鄰接矩陣 2.帶權(quán)值的無向圖鄰接矩陣 3.帶權(quán)值的有向圖鄰接矩陣 1不帶權(quán)值的無向圖鄰接矩陣2帶權(quán)值的無向圖鄰接矩陣.3.帶權(quán)值的有向圖鄰接矩陣備注：1. 在使用打印元素、BFS、DFS 采用無權(quán)值的無向圖鄰接矩陣存儲方式2. 在使用PRIM、KRUSKAL、3. 在使用最短路徑的算法時采用具有權(quán)值的有向圖鄰接矩陣存儲方式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; /初始化頂點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 << "請輸入線性鏈接節(jié)點:"cin >> s1

4、 >> s2 >> height;arcconvert(s1)convert(s2) = height;arcconvert(s2)convert(s1) = arcconvert(s1)convert(s2); /采用無向圖帶權(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.算法的時間復雜度有構(gòu)造可知，初始化時其時間復雜度：O(n2)二深度優(yōu)先便利DFS:1.關(guān)鍵算法從某頂點v出發(fā)并訪問訪問v的第一個未訪問的鄰接點w， 訪問w的第一個未訪問的鄰接點u， 若當前頂點的所有鄰接點都被訪問過，則回溯，從上一級頂點的下一個未訪問過的頂點開始深度優(yōu)先遍歷直到所有和v路徑相通的頂點都被訪問到；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); /當存在回路時，則連通深一層遍歷 4.時間復雜度 時間復雜度：O(n2)空間復雜度：棧的深度O(n)輔助空間O(n)三廣度遍歷BFS1.關(guān)鍵算法訪問頂點v依次訪問v的所有未被訪問的鄰接點v1,v2,v3分別從v1,v2,v3出發(fā)依次訪問它們未被訪問的鄰接點反復

7、 ，直到所有和v路徑相通的頂點都被訪問到；2.代碼圖解3.代碼詳解1.初始化隊列Q 2.訪問頂點v， visitedv=1 3. while(隊列非空) 3.1 v=隊頭元素出隊 3.2 訪問隊頭元素的所有未訪問的鄰接點4.時間復雜度 時間復雜度：O(n2) 空間復雜度：輔助空間O(n)四.最小生成樹普里姆算法1,關(guān)鍵思路一般情況下，假設(shè)n個頂點分成兩個集合：U(包含已落在生成樹上的結(jié)點)和V-U(尚未落在生成樹上的頂點)，則在所有連通U中頂點和V-U中頂點的邊中選取權(quán)值最小的邊。主數(shù)據(jù)結(jié)構(gòu)： 鄰接矩陣輔助數(shù)據(jù)結(jié)構(gòu)： int adjvexMAXSIZE; / U集中的頂點序號 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ù)組存儲所有到的V0邊adjvexi = 0; lowcosti = arc0i; lowcost0 = 0;for (int j = 1; j < vnum; j+) /循環(huán)n-1次int k = Mininum(lowcost); /求下一個頂點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,時間復雜度：時間復雜度O(n2)，適合稠密圖五.最小生成樹-克魯斯卡爾算法1,關(guān)鍵思路先構(gòu)造一個只含n個頂點的子圖SG，然后從權(quán)值最小的邊開始，若它的添加不使SG中產(chǎn)生回路，則在SG上加上這條邊，如此重復，直至加上n-1條邊為

10、止。2.代碼圖解： 3.代碼詳解template<class f>void Graph<f>:Kruskal() /最小生成樹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; /兩個頂點分屬不同的集合if (sn1 != sn2)cout << vertexm << "->" << vertexn << endl;k+;for (int i = 0; i < vnum; i+)if (vseti = sn2)vseti = sn1; /集合sn2全部改成sn1j+;4.時間復雜度 時間復雜度O(nlogn)，適合稀疏圖六最短路徑Dijkstra算法1.關(guān)鍵代碼 按路徑長度遞增的次序產(chǎn)生源點到其余各頂點的最短路徑。 1)設(shè)置集合s存儲已求得的最短路徑的頂點， 2

12、)初始狀態(tài)：s=源點v 3)疊代算法： 直接與v相連的最近頂點vi,加入s 從v經(jīng)過vi可以到達的頂點中最短的，加入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+) /初始化路徑和點 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+) /反復經(jīng)過從該點到其他點的路徑 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(); /打印路徑長度和遍歷 4.時間復雜度時間復雜度為：n2七判斷連通圖算法template<class f>bool Graph<f>:judgegraph()DFS(convert(

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