【文章內(nèi)容簡介】 stadjvex(gra,[e])。we=0。we=nextadjvex(gra,[e],we)) { if(!visited[we]) { visited[we]=1。 cout[we].data。 EnQueue(q,we)。 } } } }}深度優(yōu)先遍歷：int DFS(ALGraph gra,int i){ visited[i]=1。 int we1。 cout[i].data。 for(we=firstadjvex(gra,[i])。we=0。we=nextadjvex(gra,[i],we)) { we1=we。 if(visited[we]==0) DFS(gra,we)。 we=we1。 } return 1。}int DFStra(ALGraph gra){ int i,j。 for(i=0。i!=。++i) { visited[i]=0。 } for(j=0。j!=。++j) { if(visited[j]==0)DFS(gra,j)。 } return 0。}連通分量：int DFSTraverse_fen(ALGraph gra){ int i,j。 for(i=0。i!=。++i) visited[i]=0。 for(j=0。j!=。++j) { if(visited[j]==0) { DFS(gra,j)。 coutendl。 l++。 } } return 0。}3. 主要函數(shù)的程序流程圖，實現(xiàn)設(shè)計中主程序和其他子模塊的算法，以流程圖的形式表示。圖的廣度優(yōu)先遍歷圖的鄰接矩陣存儲圖的鄰接表存儲圖的普利姆算法求最小生成樹 調(diào)試分析 1. 實際完成的情況說明；a. 先任意創(chuàng)建一個圖；b. 圖的DFS,BFS的遞歸和非遞歸算法的實現(xiàn)c. 最小生成樹（兩個算法）的實現(xiàn)，求連通分量的實現(xiàn)d. 要求用鄰接矩陣、鄰接表等多種結(jié)構(gòu)存儲實現(xiàn)支持的數(shù)據(jù)類型：整型和字符型，包括時空分析；本程序的圖的遍歷是以鄰接表做圖的存儲結(jié)構(gòu)，其時間復(fù)雜度為O（n+e）。； ，無邊都用的10000（無窮大int_max）表示的，這種表示和我們習(xí)慣上的0與∞的表示有差異。所以在程序中定義了全局變量n（初值為0）,來判斷創(chuàng)建的無向圖是有權(quán)圖還是無權(quán)圖，n0為有權(quán)圖，此時輸出的時候用∞代替10000；n=0為無權(quán)圖，此時輸出的時候用0代替10000. ，比如無權(quán)圖沒有最小生成樹，非強(qiáng)連通圖沒有最小生成樹等。所以在程序中又新增了全局變量l,l0時表示為非強(qiáng)連通圖，則在求最小生成樹時報錯。 ，n的值會大于1，第二次創(chuàng)無權(quán)圖時也會被程序認(rèn)為有權(quán)圖，所以在程序中在定義全局變量o（初值為0）,來判斷創(chuàng)建了幾次圖，當(dāng)?shù)诙蝿?chuàng)建圖，即o=2時，所有全局變量在開始全歸零。4. 程序中可以改進(jìn)的地方說明；當(dāng)建立一個圖時先得求其連通分量，從而確定全局變量l的值，從而才能判斷該圖是否有最小生成樹。 測試結(jié)果創(chuàng)建一個無權(quán)圖：創(chuàng)建一個費強(qiáng)連通的有權(quán)圖：創(chuàng)建一個有權(quán)連通圖： 用戶手冊。七、體會與自我評價 在做這個程序的時候你首先必須知道圖的一些概念，圖是一種較線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在線性表中，數(shù)據(jù)元素之間僅有線性關(guān)系，每個數(shù)據(jù)元素只有一個直接前驅(qū)和一個直接后繼；在樹形結(jié)構(gòu)中，數(shù)據(jù)元素之間有著明顯的層次關(guān)系，并且每一層上的數(shù)據(jù)元素可能和下一層中多個元素（及其孩子結(jié)點）相關(guān)但只能和上一層中一個元素（即雙親結(jié)點）相關(guān)；而在圖形結(jié)構(gòu)中，節(jié)點之間的關(guān)系可以是任意的，圖中任意兩個數(shù)據(jù)元素之間都可能相關(guān)。當(dāng)我們拿到一個圖時，我們對該圖的遍歷就要有一些方法，所以有了深度優(yōu)先遍歷和廣度優(yōu)先遍歷，我們要明白這兩種遍歷是怎么實現(xiàn)的，然后根據(jù)我們?nèi)四X中的方法把它寫成電腦算法。對一個圖我們還定義了連通分量，所以將圖存到電腦中時，我們對連通分量得有個算法。求圖的最小生成樹有兩種算法，普利姆是從結(jié)點出發(fā)尋找權(quán)最小的邊，知道所有結(jié)點都練通了；而克魯斯卡爾算法則是從邊出發(fā)，尋找使圖連通的權(quán)值最小邊的方法。算法的實現(xiàn)從人腦到電腦的轉(zhuǎn)變是比較復(fù)雜的一件事，要求做到具體到實現(xiàn)該方法的每一個步驟，然后再將每一個步驟通過代碼實現(xiàn)。這要求我們要明確各個數(shù)據(jù)元素和個元素之間的關(guān)系，然后才能明確使用算法去調(diào)用這些數(shù)據(jù)。通過本次的課程設(shè)計，我對數(shù)據(jù)結(jié)構(gòu)有了一定的認(rèn)識，明白了數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)，數(shù)據(jù)關(guān)系，及對其操作的方法。但同時也發(fā)現(xiàn)在自己有很多的不足，在使用語言和如何精煉語言需要進(jìn)行更多的訓(xùn)練。 源代碼：include iostreaminclude using namespace std。define int_max 10000//最大值static int n=0。//全局變量，判斷有權(quán)圖和無權(quán)圖static int o=0。//全局變量，清除BUGstatic int l=0。//全局變量，清除BUGdefine inf 9999//最小值的最大值define max 20//最大頂點個數(shù)typedef int VRType,QElemType,Status。typedef char InfoType,VertexType。 //|||||||||||||||||||||||||鄰接矩陣|||||||||||||||||||||||||||||||//鄰接矩陣定義typedef struct ArcCell{ VRType adj。//VRType是頂點關(guān)系類型。對無權(quán)圖，用1或0表示相鄰否；對帶權(quán)圖，則為權(quán)值類型 InfoType *info。//該弧相關(guān)信息的指針}ArcCell,AdjMatrix[max][max]。typedef struct{ VertexType vexs[max]。//頂點向量 AdjMatrix arcs。//鄰接矩陣 int vexnum,arum。//圖的當(dāng)前頂點數(shù)和弧數(shù)}MGraph_L。//int localvex(MGraph_L G,char v)//返回V的位置{ int i=0。 while([i]!=v)++i。 return i。}int creatMGraph_L(MGraph_L amp。G)//創(chuàng)建圖用鄰接矩陣表示{ char v1,v2。 int i,j,w。 cout請輸入頂點和弧的個數(shù)endl。 cin。 cout輸入各個頂點endl。 for(i=0。i。++i) { cin[i]。 } for(i=0。i。++i) for(j=0。j。++j) { [i][j].adj=int_max。 [i][j].info=NULL。 } for(int k=0。k。++k) { cout輸入一條邊依附的頂點和權(quán)endl。 cinv1v2w。//輸入一條邊依附的兩點及權(quán)值 i=localvex(G,v1)。//確定頂點V1和V2在圖中的位置 j=localvex(G,v2)。 [i][j].adj=w。 [j][i].adj=w。 } for(i=0。i!=。++i) for(j=0。j!=。++j) { if([i][j].adj!=1amp。amp。[i][j].adjint_max)n+=1。 } if(n=1)cout這是一個有權(quán)圖endl。 else cout這是一個無權(quán)圖endl。 cout圖G鄰接矩陣創(chuàng)建成功！endl。 return 。}void ljjzprint(MGraph_L G) //鄰接矩陣的輸出{ int i,j。 if(n==0) { for(i=0。i!=。++i) { for(j=0。j!=。++j) { if([i][j].adj==int_max){cout0 。} else {cout[i][j].adj 。} } coutendl。 } } else { for(i=0。i!=。++i) { for(j=0。j!=。++j) { if([i][j].adj==int_max){cout∞ 。} else {cout[i][j].adj 。} } coutendl。 } }}//|||||||||||