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

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

3、造函數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; /初始化權值的大小visitedk = 0;cout << endl;for (k = 0; k<e; k+) /初始化邊cout << "請輸入線性鏈接節點:"cin >> s1

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

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

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

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

10、止。2.代碼圖解： 3.代碼詳解template<class f>void Graph<f>:Kruskal() /最小生成樹kruskal算法 cout<<"Krusal算法結果為："<<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.關鍵代碼 按路徑長度遞增的次序產生源點到其余各頂點的最短路徑。 1)設置集合s存儲已求得的最短路徑的頂點， 2

12、)初始狀態：s=源點v 3)疊代算法： 直接與v相連的最近頂點vi,加入s 從v經過vi可以到達的頂點中最短的，加入s 2.代碼圖解3.代碼詳解emplate<class f>void Graph<f>:ShotPath(f x) /關于最短路徑的初始化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+) /反復經過從該點到其他點的路徑 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. 程序運行結果 1. 測試主函數流程：函數流程圖：1. 輸入圖的連接邊并打印構造下面所示圖的鄰接矩陣： 2.判斷圖連通是否成功3.BFS DFS PRIM算法的實現4.克魯斯卡爾算法實現過程4. 有向圖鄰接矩陣的構建插入V0位置后打印距離并開始回溯總結1.調試時出現的問題及解決的方法 問題一：prim算法中 解決方法：調整循環條件，修正函數體注意有無Next的區別 問題二：BFS和DFS同時在一個類里作用時會輸出錯誤 解決方案：每次BFS/DFS使用時都把visited數組初始化一遍 問題三：在最短路徑，經常出現了停止輸入的情況 解決方法：改return為continue，并修改打印算法2.心得體會 通過本次實驗，基本熟練掌握了c+基本語句，尤其對圖的結構及應用有了較深了解；調試代碼時盡量做到完成一個代碼段調試一次，可以最快檢測出錯誤所在；類的封裝和調用，類的共有成員和私有成員的設置。3.下一步的改進 第一，設置增加圖節點和邊的