圖的遍歷和生成樹求解實現(xiàn)的課程結(jié)構(gòu)設(shè)計-在線瀏覽
2024-08-06 15:35本頁面
【正文】 。164。164。164。164。164。||endl。y39。 cins。 if(o==2) { n=0。 o=0。 MGraph_L G。 ALGraph gra。 break。 ljjzprint(G)。 case 2: cout鄰接表顯示如下：endl。 break。 BFSTraverse(gra)。 break。 DFStra(gra)。 break。break。break。 for(i=0。++i) for(int j=0。++j) g[i+1][j+1]=[i][j].adj。 MiniSpanTree_PRIM(g,)。 } case 6:if(n==0){cout無權(quán)圖沒有最小生成樹。} else if(l0){cout該圖為非強連通圖(含有多個連通分量)，最小生成樹不存在endl。} else { cout克魯斯卡爾算法:endl。 break。 DFSTraverse_fen(gra)。 } coutendl是否繼續(xù)？y/n:。 if(y==39。) break。}鄰接矩陣存儲：int creatMGraph_L(MGraph_L amp。 int i,j,w。 cin。 for(i=0。++i) { cin[i]。i。j。 [i][j].info=NULL。k。 cinv1v2w。//確定頂點V1和V2在圖中的位置 j=localvex(G,v2)。 [j][i].adj=w。i!=。j!=。amp。 } if(n=1)cout這是一個有權(quán)圖endl。 cout圖G鄰接矩陣創(chuàng)建成功！endl。}鄰接矩陣的輸出：void ljjzprint(MGraph_L G) //鄰接矩陣的輸出{ int i,j。i!=。j!=。} else {cout[i][j].adj 。 } } else { for(i=0。++i) { for(j=0。++j) { if([i][j].adj==int_max){cout∞ 。} } coutendl。gra,MGraph_L G)//用鄰接表存儲圖{ int i=0,j=0。//,*tem,*p。i!=。 [i].firstarc=NULL。i!=。j!=。 arcadjvex=j。 [i].firstarc=arc。 =。 return 1。 for(i=0。++i) { ArcNode *p。 p=[i].firstarc。 p=pnextarc。 coutendl。Q)//初始化隊列{ ==(QueuePtr)malloc(sizeof(QNode))。//存儲分配失敗 next=NULL。}入隊：Status EnQueue(LinkQueue amp。 p=(QueuePtr)malloc(sizeof(QNode))。//存儲分配失敗 pdata=e。 next=p。 return 1。Q,QElemType amp。 if(==)return 0。 e=pdata。 if(==p)=。 return 1。 return 0。 LinkQueue q。i!=。 InitQueue(q)。i!=。 cout[i].data。 while(!QueueEmpty(q)) { DeQueue(q,e)。we=0。 cout[we].data。 } } } }}深度優(yōu)先遍歷：int DFS(ALGraph gra,int i){ visited[i]=1。 cout[i].data。we=0。 if(visited[we]==0) DFS(gra,we)。 } return 1。 for(i=0。++i) { visited[i]=0。j!=。 } return 0。 for(i=0。++i) visited[i]=0。j!=。 coutendl。 } } return 0。圖的廣度優(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）。所以在程序中定義了全局變量n（初值為0）,來判斷創(chuàng)建的無向圖是有權(quán)圖還是無權(quán)圖，n0為有權(quán)圖，此時輸出的時候用∞代替10000；n=0為無權(quán)圖，此時輸出的時候用0代替10000. ，比如無權(quán)圖沒有最小生成樹，非強連通圖沒有最小生成樹等。 ，n的值會大于1，第二次創(chuàng)無權(quán)圖時也會被程序認(rèn)為有權(quán)圖，所以在程序中在定義全局變量o（初值為0）,來判斷創(chuàng)建了幾次圖，當(dāng)?shù)诙蝿?chuàng)建圖，即o=2時，所有全局變量在開始全歸零。 測試結(jié)果創(chuàng)建一個無權(quán)圖：創(chuàng)建一個費強連通的有權(quán)圖：創(chuàng)建一個有權(quán)連通圖： 用戶手冊。在線性表中，數(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)。對一個圖我們還定義了連通分量，所以將圖存到電腦中時，我們對連通分量得有個算法。算法的實現(xiàn)從人腦到電腦的轉(zhuǎn)變是比較復(fù)雜的一件事，要求做到具體到實現(xiàn)該方法的每一個步驟，然后再將每一個步驟通過代碼實現(xiàn)。通過本次的課程設(shè)計，我對數(shù)據(jù)結(jié)構(gòu)有了一定的認(rèn)識，明白了數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)，數(shù)據(jù)關(guān)系，及對其操作的方法。 源代碼：include iostreaminclude using namespace std。//全局變量，判斷有權(quán)圖和無權(quán)圖static int o=0。//全局變量，清除BUGdefine inf 9999//最小值的最大值define max 20//最大頂點個數(shù)typedef int VRType,QElemType,Status。 //|||||||||||||||||||||||||鄰接矩陣|||||||||||||||||||||||||||||||//鄰接矩陣定義typedef struct ArcCell{ VRType adj。對無權(quán)圖，用1或0表示相鄰否；對帶權(quán)圖，則為權(quán)值類型 InfoType *info。typedef struct{ VertexType vexs[max]。//鄰接矩陣 int vexnum,arum。//int localvex(MGraph_L G,char v)//返回V的位置{ int i=0。 return i。G)//創(chuàng)建圖用鄰接矩陣表示{ char v1,v2。 cout請輸入頂點和弧的個數(shù)endl。 cout輸入各個頂點endl。i。 } for(i=0。++i) for(j=0。++j) { [i][j].adj=int_max。 } for(int k=0。++k) { cout輸入一條邊依附的頂點和權(quán)endl。//輸入一條邊依附的兩點及權(quán)值 i=localvex(G,v1)。 [i][j].adj=w。 } for(i=0。++i) for(j=0。++j) { if([i][j].adj!=1amp。[i][j].adjint_max)n+=1。 else cout這是一個無權(quán)圖endl。 return 。 if(n==0) { for(i=0。++i) { for(j=0。++j) { if([i][j].adj==int
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號-1