北郵數(shù)據(jù)結(jié)構(gòu)實驗第二次實驗圖

1、數(shù)據(jù)結(jié)構(gòu)實驗報告1.實驗要求(1)實驗?zāi)康耐ㄟ^選擇下面5個題目之一進行實現(xiàn)，掌握如下內(nèi)容：掌握圖基本操作的實現(xiàn)方法了解最小生成樹的思想和相關(guān)概念了解最短路徑的思想和相關(guān)概念學(xué)習使用圖解決實際問題的能力(2)實驗內(nèi)容根據(jù)圖的抽象數(shù)據(jù)類型的定義，使用鄰接矩陣或鄰接表實現(xiàn)一個圖。圖的基本功能：1、圖的建立2、圖的銷毀3、深度優(yōu)先遍歷圖4、廣度優(yōu)先遍歷圖5、使用普里姆算法生成最小生成樹6、使用克魯斯卡爾算法生成最小生成樹7、求指定頂點到其他各頂點的最短路徑8、其他：比如連通性判斷等自定義操作編寫測試main()函數(shù)測試圖的正確性2.程序分析存儲結(jié)構(gòu)圖：(1)帶權(quán)值的無向圖V096V1 2V2(2)帶權(quán)

2、值的有向圖V0V1 2V2關(guān)鍵算法分析(1)深度優(yōu)先遍歷int visitedMAXSIZE尸false;templatevoid MGraph:DFS(int v) coutvertexv;visitedv=true;for(int j=0;jvNum;j+)if(arcvj=1&!visitedj) DFS(j);時間復(fù)雜度：O(n2)(2)廣度優(yōu)先遍歷int queueMAXSIZE;int f=0,r=0;coutvertexv;visitv=true;queue+r=v;while(f!=r)v=queue+f;for(int j=0;jvNum;j+) if(arcvj=1&!vi

3、sitj)coutvertexj;visitj=true;queue+r=j; 時間復(fù)雜度：O (n2)(3)普利姆算法int adjvexMAXSIZE;int lowcostMAXSIZE;int MAX=10000;templateint mininum(MGraph G,int a口) int min=MAX;int k=0;for(int i=0;i;i+) if(ai!=0&aimin)romV=i;Ek.endV=j;Ek.weight=ij; k+;for(i=0;i;i+) for(j=i+1;jEj.weight) VEdge t=Ei;Ei=Ej； Ej=t； const

4、 int MAX_VERTEXT=20;template void MGraph: Kruskal(VEdge E,int n,int e) int vsetMAX_VERTEXT;for(int i=0;in;i+) vseti=i;romV,n=Ej.endV;int sn1=vsetm;程序運行結(jié)果(1)流程圖：初始化帶權(quán)值的無向圖深度優(yōu)先遍歷，廣度優(yōu)先遍歷!用普利姆算法求最小生成樹I用克魯斯卡爾算法求最小生成樹初始化帶權(quán)值的有向圖用Floyd算法求任意兩點間最短路徑，并判斷連通性刪除圖(2)本程序所用的圖帶權(quán)值的無向圖V0 9V12V2帶權(quán)值的有向圖/ V0V1 2V2(3)程序結(jié)果4

5、.總結(jié)(1)遇到的問題：私有數(shù)據(jù)訪問權(quán)的問題，在編程時應(yīng)該注意(2)心得體會：通過這次實驗，我掌握了圖基本操作的實現(xiàn)方法，了解最小生成樹的思想 和相關(guān)概念，了解最短路徑的思想和相關(guān)概念等等。(3)改進：可以適當對某些步驟進行合并或省略，使程序更加簡潔。源代碼：#includeusing namespace std;const int MAXSIZE=20;const int MAX_EDGE=20;const int MAX_VALUE=1000;struct VEdgeint fromV;romV=i;Ek.endV=j;Ek.weight=ij;k+;for(i=0;i;i+)for(j=

6、i+1;jEj.weight)VEdge t=Ei;Ei=Ej;Ej=t;const int MAX_VERTEXT=20;templatevoid MGraph: Kruskal(VEdge E,int n,int e)int vsetMAX_VERTEXT;for(int i=0;in;i+) vseti=i;romV,n=Ej.endV;int sn1=vsetm;/m 所屬的集合int sn2=vsetn;/n 所屬的集合if(sn1!=sn2)coutVmVnendl;k+;for(int i=0;in;i+)if(vseti=sn2)/ 集合編號為sn2 的全部改為 sn1vset

7、i=sn1;j+;/ 求最短路徑/ 連通性判斷int distMAXSIZEMAXSIZE;int pathMAXSIZEMAXSIZE;templatevoid Floyd(MGraph G)for(int i=0;i;i+)/ 尋找最短路徑for(int j=0；j；j+)(distij=ij;if(distij!=MAX_VALUE) pathij=i;elsepathij=-1;for(int k=0;k;k+)for(int i=0;i;i+)for(int j=0;j;j+) if(distik+distkjdistij)/更新迭代數(shù)組 Disk叩(distij=distik+di

8、stkj;pathij=k;cout任意兩點間的最短路徑(以矩陣表示)：endl;int l=1;for(int i=0;i;i+)for(int j=0;j;j+)(coutdistij coutendl;l=1;void main()int v,e;cout請輸入頂點數(shù)(21)和邊數(shù)(ve;if(v20|v0|e20)cout輸入錯誤！endl;char ch20=a,b,c,d,e,f,g,h,i,j,k,T,m,n,o,p,q,r,s,t; MGraph A(ch,v,e);couts;cout深度優(yōu)先遍歷：endl;(s);coutendl;coutk;cout廣度優(yōu)先遍歷：endl;(k);coutendl;cout普利姆算法求最小生成樹：endl;(A);cou