1、#大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告題目： 圖的遍歷和生成樹(shù)求解 院（系）：計(jì)算機(jī)工程學(xué)院學(xué)生姓名:班級(jí)：學(xué)號(hào):起迄日期: 2011.6.20指導(dǎo)教師: 20102011年度 第 2 學(xué)期一、需求分析1.問(wèn)題描述：圖的遍歷和生成樹(shù)求解實(shí)現(xiàn)圖是一種較線性表和樹(shù)更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在線性表中，數(shù)據(jù)元素之間僅有線性關(guān)系，每個(gè)數(shù)據(jù)元素只有一個(gè)直接前驅(qū)和一個(gè)直接后繼；在樹(shù)形結(jié)構(gòu)中，數(shù)據(jù)元素之間有著明顯的層次關(guān)系，并且每一層上的數(shù)據(jù)元素可能和下一層中多個(gè)元素（及其孩子結(jié)點(diǎn)）相關(guān)但只能和上一層中一個(gè)元素（即雙親結(jié)點(diǎn)）相關(guān)；而在圖形結(jié)構(gòu)中，節(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意兩個(gè)數(shù)據(jù)元素之間都可能相關(guān)。生成樹(shù)求解主要利

2、用普利姆和克雷斯特算法求解最小生成樹(shù)，只有強(qiáng)連通圖才有生成樹(shù)。1) 先任意創(chuàng)建一個(gè)圖；2) 圖的DFS,BFS的遞歸和非遞歸算法的實(shí)現(xiàn)3) 最小生成樹(shù)（兩個(gè)算法）的實(shí)現(xiàn)，求連通分量的實(shí)現(xiàn)4) 要求用鄰接矩陣、鄰接表等多種結(jié)構(gòu)存儲(chǔ)實(shí)現(xiàn) 輸入數(shù)據(jù)類型為整型和字符型，輸出為整型和字符二、 概要設(shè)計(jì)1. 設(shè)計(jì)思路：a.圖的鄰接矩陣存儲(chǔ)：根據(jù)所建無(wú)向圖的結(jié)點(diǎn)數(shù)n,建立n*n的矩陣，其中元素全是無(wú)窮大（int_max），再將邊的信息存到數(shù)組中。其中無(wú)權(quán)圖的邊用1表示，無(wú)邊用0表示；有全圖的邊為權(quán)值表示，無(wú)邊用表示。b.圖的鄰接表存儲(chǔ)：將信息通過(guò)鄰接矩陣轉(zhuǎn)換到鄰接表中，即將鄰接矩陣的每一行都轉(zhuǎn)成鏈表的形式將

3、有邊的結(jié)點(diǎn)進(jìn)行存儲(chǔ)。c.圖的廣度優(yōu)先遍歷：假設(shè)從圖中的某個(gè)頂點(diǎn)v出發(fā)，在訪問(wèn)了v之后依次訪問(wèn)v的各個(gè)未曾訪問(wèn)過(guò)的鄰接點(diǎn)，然后再訪問(wèn)此鄰接點(diǎn)的未被訪問(wèn)的鄰接點(diǎn)，并使“先被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)”被訪問(wèn)，直至圖中所有已被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)到。若此時(shí)圖中還有未被訪問(wèn)的，則另選未被訪問(wèn)的重復(fù)以上步驟，是一個(gè)非遞歸過(guò)程。d.圖的深度優(yōu)先遍歷：假設(shè)從圖中某頂點(diǎn)v出發(fā)，依依次訪問(wèn)v的鄰接頂點(diǎn)，然后再繼續(xù)訪問(wèn)這個(gè)鄰接點(diǎn)的系一個(gè)鄰接點(diǎn)，如此重復(fù)，直至所有的點(diǎn)都被訪問(wèn)，這是個(gè)遞歸的過(guò)程。e.圖的連通分量：這是對(duì)一個(gè)非強(qiáng)連通圖的遍歷，從多個(gè)結(jié)點(diǎn)出發(fā)進(jìn)行搜索，而每一次從一個(gè)新的起始點(diǎn)

4、出發(fā)進(jìn)行搜索過(guò)程中得到的頂點(diǎn)訪問(wèn)序列恰為其連通分量的頂點(diǎn)集。本程序利用的圖的深度優(yōu)先遍歷算法。 2.數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：ADT Queue數(shù)據(jù)對(duì)象：D=ai| aiElemSet,i=1,2,3，n,n0數(shù)據(jù)關(guān)系：R1=<ai-1,ai>| ai-1,aiD,i=1,2,3,，n基本操作： InitQueue(&Q) 操作結(jié)果：構(gòu)造一個(gè)空隊(duì)列Q。 QueueEmpty(Q) 初始條件：Q為非空隊(duì)列。 操作結(jié)果：若Q為空隊(duì)列，則返回真，否則為假。 EnQueue(&Q,e) 初始條件：Q為非空隊(duì)列。 操作結(jié)果：插入元素e為Q的新的隊(duì)尾元素。 DeQueue(&Q,e

5、) 初始條件：Q為非空隊(duì)列。 操作結(jié)果：刪除Q的隊(duì)頭元素，并用e返回其值。ADT QueueADT Graph數(shù)據(jù)對(duì)象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。數(shù)據(jù)關(guān)系R： R=VR VR=<v,w>|v,wV且P（v，w）,<v,w>表示從v到w的弧， 謂詞P（v,w）定義了弧<v,w>的意義或信息基本操作P： CreatGraph(&G,V,VR); 初始條件：V是圖的頂點(diǎn)集，VR是圖中弧的集合。 操作結(jié)果：按V和VR的定義構(gòu)造圖G。 BFSTraverse(G,visit(); 初始條件：圖G存在，Visit是定點(diǎn)的應(yīng)用函數(shù)。 操作結(jié)果

6、：對(duì)圖進(jìn)行廣度優(yōu)先遍歷。在遍歷過(guò)程中對(duì)每個(gè)頂點(diǎn) 調(diào)用函數(shù)Visit一次且僅一次。一旦visit（）失 敗，則操作失敗。 DFSTraverse(G,visit(); 初始條件：圖G存在，Visit是定點(diǎn)的應(yīng)用函數(shù)。 操作結(jié)果：對(duì)圖進(jìn)行廣度優(yōu)先遍歷。在遍歷過(guò)程中對(duì)每個(gè)頂點(diǎn) 調(diào)用函數(shù)Visit一次且僅一次。一旦visit（）失 敗，則操作失敗。 DFStra_fen(G) 初始條件：圖G存在，存在圖的深度優(yōu)先遍歷算法。 操作結(jié)果：從多個(gè)頂點(diǎn)對(duì)圖進(jìn)行深度優(yōu)先遍歷，得到連通分量。ADT Graph;3. 軟件結(jié)構(gòu)設(shè)計(jì)：函數(shù)名返回值類型creatMGraph_L(G)intcreatadj(gra,G)

7、intljjzprint(G)voidadjprint(gra,G)voidBFSTraverse(gra)voidDFStra(gra)intDFSTraverse_fen(gra)intMiniSpanTree_PRIM(g,G.vexnum)intMiniSpanTREE_KRUSCAL(G,gra)void三、 詳細(xì)設(shè)計(jì) 1. 定義程序中所有用到的數(shù)據(jù)及其數(shù)據(jù)結(jié)構(gòu)，及其基本操作的實(shí)現(xiàn)；鄰接矩陣定義:typedef struct ArcCellVRType adj;/VRType是頂點(diǎn)關(guān)系類型。對(duì)無(wú)權(quán)圖，用1或0表示相鄰否；對(duì)帶權(quán)圖，則為權(quán)值類型InfoType *info;/該弧相關(guān)信

8、息的指針ArcCell,AdjMatrixmaxmax;typedef structVertexType vexsmax;/頂點(diǎn)向量AdjMatrix arcs;/鄰接矩陣int vexnum,arcnum;/圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)MGraph_L;鄰接表的定義:typedef struct ArcNode/弧結(jié)點(diǎn)int adjvex;/該弧指向的頂點(diǎn)的位置struct ArcNode *nextarc;/指向下一條弧的指針I(yè)nfoType *info;/該弧相關(guān)信息的指針ArcNode;typedef struct VNode/鄰接鏈表頂點(diǎn)頭接點(diǎn)VertexType data;/頂點(diǎn)信息Arc

9、Node *firstarc;/指向第一條依附該頂點(diǎn)的弧的指針VNode,AdjList;typedef struct/圖的定義AdjList verticesmax;int vexnum,arcnum;/圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)ALGraph;隊(duì)列定義:typedef struct QNodeQElemType data;struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front;/隊(duì)頭指針QueuePtr rear;/隊(duì)尾指針LinkQueue;2 主函數(shù)和其他函數(shù)的偽碼算法；主函數(shù)：int main()int s;char

10、y='y' cout<<"|¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤菜單¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤|"<<endl; cout<<"|-【0、創(chuàng)建一個(gè)無(wú)向圖-|&q

11、uot;<<endl; cout<<"|-【1、顯示該圖的鄰接矩陣-|"<<endl; cout<<"|-【2、顯示該圖的鄰接表-|"<<endl;cout<<"|-【3、廣度優(yōu)先遍歷-|"<<endl; cout<<"|-【4、深度優(yōu)先遍歷-|"<<endl; cout<<"|-【5、最小生成樹(shù)MiniSpanTree_PRIM算法-|"<<endl; cout&

12、lt;<"|-【6、最小生成樹(shù)MiniSpanTree_KRUSCAL算法-|"<<endl; cout<<"|-【7、連通分量-|"<<endl;cout<<"|¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤

13、4;¤¤¤¤¤¤¤¤¤|"<<endl;while(y='y')cout<<"請(qǐng)選擇菜單："<<endl; cin>>s;if(s=0)+o;if(o=2)n=0;l=0;o=0;switch(s)case 0:cout<<"創(chuàng)建一個(gè)無(wú)向圖："<<endl;MGraph_L G;creatMGraph_L(G);ALGraph gra;creatadj(gra,G);

14、break;case 1:cout<<"鄰接矩陣顯示如下："<<endl;ljjzprint(G); break; case 2: cout<<"鄰接表顯示如下："<<endl; adjprint(gra,G); break; case 3: cout<<"廣度優(yōu)先遍歷：" BFSTraverse(gra); cout<<endl; break; case 4:cout<<"深度優(yōu)先遍歷：" DFStra(gra); cout<

15、;<endl; break; case 5:if(n=0)cout<<"無(wú)權(quán)圖沒(méi)有最小生成樹(shù)"break;else if(l>0)cout<<"若該圖為非強(qiáng)連通圖(含有多個(gè)連通分量)時(shí)，最小生成樹(shù)不存在"<<endl;break;elseint i,gmaxmax;for(i=0;i!=G.vexnum;+i)for(int j=0;j!=G.vexnum;+j)gi+1j+1=G.arcsij.adj;cout<<"普利姆算法:"<<endl;MiniSpanT

16、ree_PRIM(g,G.vexnum);break; case 6:if(n=0)cout<<"無(wú)權(quán)圖沒(méi)有最小生成樹(shù)"break;else if(l>0)cout<<"該圖為非強(qiáng)連通圖(含有多個(gè)連通分量)，最小生成樹(shù)不存在"<<endl;break;elsecout<<"克魯斯卡爾算法:"<<endl; MiniSpanTREE_KRUSCAL(G,gra); break; case 7:cout<<"連通分量:"<<end

17、l;DFSTraverse_fen(gra); break;cout<<endl<<"是否繼續(xù)？y/n:" cin>>y; if(y='n') break;return 0;鄰接矩陣存儲(chǔ)：int creatMGraph_L(MGraph_L &G)/創(chuàng)建圖用鄰接矩陣表示char v1,v2;int i,j,w;cout<<"請(qǐng)輸入頂點(diǎn)和弧的個(gè)數(shù)"<<endl;cin>>G.vexnum>>G.arcnum;cout<<"輸入各

18、個(gè)頂點(diǎn)"<<endl;for(i=0;i<G.vexnum;+i)cin>>G.vexsi;for(i=0;i<G.vexnum;+i)for(j=0;j<G.vexnum;+j)G.arcsij.adj=int_max;G.=NULL;for(int k=0;k<G.arcnum;+k)cout<<"輸入一條邊依附的頂點(diǎn)和權(quán)"<<endl;cin>>v1>>v2>>w;/輸入一條邊依附的兩點(diǎn)及權(quán)值i=localvex(G,v1);/確

19、定頂點(diǎn)V1和V2在圖中的位置j=localvex(G,v2);G.arcsij.adj=w;G.arcsji.adj=w;for(i=0;i!=G.vexnum;+i)for(j=0;j!=G.vexnum;+j)if(G.arcsij.adj!=1&&G.arcsij.adj<int_max)n+=1;if(n>=1)cout<<"這是一個(gè)有權(quán)圖"<<endl;else cout<<"這是一個(gè)無(wú)權(quán)圖"<<endl;cout<<"圖G鄰接矩陣創(chuàng)建成功！&qu

20、ot;<<endl;return G.vexnum;鄰接矩陣的輸出：void ljjzprint(MGraph_L G) /鄰接矩陣的輸出int i,j;if(n=0)for(i=0;i!=G.vexnum;+i)for(j=0;j!=G.vexnum;+j)if(G.arcsij.adj=int_max)cout<<"0"<<" "else cout<<G.arcsij.adj<<" "cout<<endl;elsefor(i=0;i!=G.vexnum;+i)

21、for(j=0;j!=G.vexnum;+j)if(G.arcsij.adj=int_max)cout<<""<<" "else cout<<G.arcsij.adj<<" "cout<<endl;用鄰接表存儲(chǔ)圖：int creatadj(ALGraph &gra,MGraph_L G)/用鄰接表存儲(chǔ)圖int i=0,j=0;ArcNode *arc;/,*tem,*p;for(i=0;i!=G.vexnum;+i)gra.verticesi.data=G.vexsi

22、;gra.verticesi.firstarc=NULL;for(i=0;i!=G.vexnum;+i)for(j=0;j!=G.vexnum;+j)if(G.arcsij.adj!=int_max)arc=(ArcNode *)malloc(sizeof(ArcNode);arc->adjvex=j;arc->nextarc=gra.verticesi.firstarc;gra.verticesi.firstarc=arc;gra.vexnum=G.vexnum;gra.arcnum=G.arcnum;cout<<"圖G鄰接表創(chuàng)建成功！"<&

23、lt;endl;return 1;鄰接表輸出：void adjprint(ALGraph gra,MGraph_L G) /鄰接表輸出int i;for(i=0;i!=gra.vexnum;+i)ArcNode *p;cout<<""<<i<<","<<G.vexsi<<""p=gra.verticesi.firstarc;while(p!=NULL)cout<<"->"<<""<<p->

24、adjvex<<""p=p->nextarc;cout<<"->"<<"End"cout<<endl;初始化隊(duì)列：Status InitQueue(LinkQueue &Q)/初始化隊(duì)列Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)return 0;/存儲(chǔ)分配失敗Q.front->next=NULL;return 1;入隊(duì)：Status EnQueue(LinkQueue &Q,QEl

25、emType e)/入隊(duì),插入元素e為Q的新的隊(duì)尾元素QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p)return 0;/存儲(chǔ)分配失敗p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;return 1;出隊(duì)：Status DeQueue(LinkQueue &Q,QElemType &e)/出隊(duì)，若隊(duì)列不空，則刪除Q的隊(duì)頭元素，用e返回，并返回真，否則假Q(mào)ueuePtr p;if(Q.front=Q.rear)return 0;p=Q.front->next;

26、e=p->data;Q.front->next=p->next;if(Q.rear=p)Q.rear=Q.front;free(p);return 1;判斷隊(duì)為空：Status QueueEmpty(LinkQueue Q)/判斷隊(duì)為空if(Q.front=Q.rear) return 1;return 0;廣度優(yōu)先遍歷：void BFSTraverse(ALGraph gra)int i,e;LinkQueue q;for(i=0;i!=gra.vexnum;+i)visitedi=0;InitQueue(q);for(i=0;i!=gra.vexnum;+i)if(!vi

27、sitedi) visitedi=1;cout<<gra.verticesi.data;EnQueue(q,i);while(!QueueEmpty(q)DeQueue(q,e);for(we=firstadjvex(gra,gra.verticese);we>=0;we=nextadjvex(gra,gra.verticese,we)if(!visitedwe)visitedwe=1;cout<<gra.verticeswe.data;EnQueue(q,we);深度優(yōu)先遍歷：int DFS(ALGraph gra,int i)visitedi=1;int we

28、1;cout<<gra.verticesi.data;for(we=firstadjvex(gra,gra.verticesi);we>=0;we=nextadjvex(gra,gra.verticesi,we)we1=we;if(visitedwe=0)DFS(gra,we);we=we1;return 1;int DFStra(ALGraph gra)int i,j;for(i=0;i!=gra.vexnum;+i)visitedi=0;for(j=0;j!=gra.vexnum;+j)if(visitedj=0)DFS(gra,j);return 0;連通分量：int

29、DFSTraverse_fen(ALGraph gra)int i,j;for(i=0;i!=gra.vexnum;+i)visitedi=0;for(j=0;j!=gra.vexnum;+j)if(visitedj=0)DFS(gra,j);cout<<endl;l+;return 0;3. 主要函數(shù)的程序流程圖，實(shí)現(xiàn)設(shè)計(jì)中主程序和其他子模塊的算法，以流程圖的形式表示。圖的廣度優(yōu)先遍歷圖的鄰接矩陣存儲(chǔ)圖的鄰接表存儲(chǔ)圖的普利姆算法求最小生成樹(shù)4、 調(diào)試分析 1. 實(shí)際完成的情況說(shuō)明；a. 先任意創(chuàng)建一個(gè)圖；b. 圖的DFS,BFS的遞歸和非遞歸算法的實(shí)現(xiàn)c. 最小生成樹(shù)（兩個(gè)算法）

30、的實(shí)現(xiàn)，求連通分量的實(shí)現(xiàn)d. 要求用鄰接矩陣、鄰接表等多種結(jié)構(gòu)存儲(chǔ)實(shí)現(xiàn)支持的數(shù)據(jù)類型：整型和字符型2.程序的性能分析，包括時(shí)空分析；本程序的圖的遍歷是以鄰接表做圖的存儲(chǔ)結(jié)構(gòu)，其時(shí)間復(fù)雜度為O（n+e）。3.上機(jī)過(guò)程中出現(xiàn)的問(wèn)題及其解決方案； a.程序開(kāi)始對(duì)無(wú)權(quán)圖和有權(quán)圖的鄰接矩陣的輸出時(shí)，無(wú)邊都用的10000（無(wú)窮大int_max）表示的，這種表示和我們習(xí)慣上的0與的表示有差異。所以在程序中定義了全局變量n（初值為0）,來(lái)判斷創(chuàng)建的無(wú)向圖是有權(quán)圖還是無(wú)權(quán)圖，n>0為有權(quán)圖，此時(shí)輸出的時(shí)候用代替10000；n=0為無(wú)權(quán)圖，此時(shí)輸出的時(shí)候用0代替10000. b.程序中有的功能對(duì)某些圖是不適

31、用的，比如無(wú)權(quán)圖沒(méi)有最小生成樹(shù)，非強(qiáng)連通圖沒(méi)有最小生成樹(shù)等。所以在程序中又新增了全局變量l,l>0時(shí)表示為非強(qiáng)連通圖，則在求最小生成樹(shù)時(shí)報(bào)錯(cuò)。 C.當(dāng)程序先創(chuàng)建一個(gè)有權(quán)圖后，n的值會(huì)大于1，第二次創(chuàng)無(wú)權(quán)圖時(shí)也會(huì)被程序認(rèn)為有權(quán)圖，所以在程序中在定義全局變量o（初值為0）,來(lái)判斷創(chuàng)建了幾次圖，當(dāng)?shù)诙蝿?chuàng)建圖，即o=2時(shí)，所有全局變量在開(kāi)始全歸零。4. 程序中可以改進(jìn)的地方說(shuō)明；當(dāng)建立一個(gè)圖時(shí)先得求其連通分量，從而確定全局變量l的值，從而才能判斷該圖是否有最小生成樹(shù)。5、 測(cè)試結(jié)果創(chuàng)建一個(gè)無(wú)權(quán)圖：創(chuàng)建一個(gè)費(fèi)強(qiáng)連通的有權(quán)圖：創(chuàng)建一個(gè)有權(quán)連通圖：6、 用戶手冊(cè)a.先選0創(chuàng)建一個(gè)圖。b.選擇y繼續(xù)操

32、作。c.按照菜單編碼選擇操作。七、體會(huì)與自我評(píng)價(jià) 在做這個(gè)程序的時(shí)候你首先必須知道圖的一些概念，圖是一種較線性表和樹(shù)更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在線性表中，數(shù)據(jù)元素之間僅有線性關(guān)系，每個(gè)數(shù)據(jù)元素只有一個(gè)直接前驅(qū)和一個(gè)直接后繼；在樹(shù)形結(jié)構(gòu)中，數(shù)據(jù)元素之間有著明顯的層次關(guān)系，并且每一層上的數(shù)據(jù)元素可能和下一層中多個(gè)元素（及其孩子結(jié)點(diǎn)）相關(guān)但只能和上一層中一個(gè)元素（即雙親結(jié)點(diǎn)）相關(guān)；而在圖形結(jié)構(gòu)中，節(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意兩個(gè)數(shù)據(jù)元素之間都可能相關(guān)。當(dāng)我們拿到一個(gè)圖時(shí)，我們對(duì)該圖的遍歷就要有一些方法，所以有了深度優(yōu)先遍歷和廣度優(yōu)先遍歷，我們要明白這兩種遍歷是怎么實(shí)現(xiàn)的，然后根據(jù)我們?nèi)四X中的方法把

33、它寫(xiě)成電腦算法。對(duì)一個(gè)圖我們還定義了連通分量，所以將圖存到電腦中時(shí)，我們對(duì)連通分量得有個(gè)算法。求圖的最小生成樹(shù)有兩種算法，普利姆是從結(jié)點(diǎn)出發(fā)尋找權(quán)最小的邊，知道所有結(jié)點(diǎn)都練通了；而克魯斯卡爾算法則是從邊出發(fā)，尋找使圖連通的權(quán)值最小邊的方法。算法的實(shí)現(xiàn)從人腦到電腦的轉(zhuǎn)變是比較復(fù)雜的一件事，要求做到具體到實(shí)現(xiàn)該方法的每一個(gè)步驟，然后再將每一個(gè)步驟通過(guò)代碼實(shí)現(xiàn)。這要求我們要明確各個(gè)數(shù)據(jù)元素和個(gè)元素之間的關(guān)系，然后才能明確使用算法去調(diào)用這些數(shù)據(jù)。通過(guò)本次的課程設(shè)計(jì)，我對(duì)數(shù)據(jù)結(jié)構(gòu)有了一定的認(rèn)識(shí)，明白了數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)，數(shù)據(jù)關(guān)系，及對(duì)其操作的方法。但同時(shí)也發(fā)現(xiàn)在自己有很多的不足，在使用語(yǔ)言和如何精煉語(yǔ)言需要

34、進(jìn)行更多的訓(xùn)練。 源代碼：#include <iostream>#include <malloc.h>using namespace std;#define int_max 10000/最大值static int n=0;/全局變量，判斷有權(quán)圖和無(wú)權(quán)圖static int o=0;/全局變量，清除BUGstatic int l=0;/全局變量，清除BUG#define inf 9999/最小值的最大值#define max 20/最大頂點(diǎn)個(gè)數(shù)typedef int VRType,QElemType,Status;typedef char InfoType,VertexT

35、ype; /|鄰接矩陣|/-鄰接矩陣定義-typedef struct ArcCellVRType adj;/VRType是頂點(diǎn)關(guān)系類型。對(duì)無(wú)權(quán)圖，用1或0表示相鄰否；對(duì)帶權(quán)圖，則為權(quán)值類型InfoType *info;/該弧相關(guān)信息的指針ArcCell,AdjMatrixmaxmax;typedef structVertexType vexsmax;/頂點(diǎn)向量AdjMatrix arcs;/鄰接矩陣int vexnum,arcnum;/圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)MGraph_L;/-int localvex(MGraph_L G,char v)/返回V的位置int i=0;while(G.vexs

36、i!=v)+i;return i;int creatMGraph_L(MGraph_L &G)/創(chuàng)建圖用鄰接矩陣表示char v1,v2;int i,j,w;cout<<"請(qǐng)輸入頂點(diǎn)和弧的個(gè)數(shù)"<<endl;cin>>G.vexnum>>G.arcnum;cout<<"輸入各個(gè)頂點(diǎn)"<<endl;for(i=0;i<G.vexnum;+i)cin>>G.vexsi;for(i=0;i<G.vexnum;+i)for(j=0;j<G.vexnum;

37、+j)G.arcsij.adj=int_max;G.=NULL;for(int k=0;k<G.arcnum;+k)cout<<"輸入一條邊依附的頂點(diǎn)和權(quán)"<<endl;cin>>v1>>v2>>w;/輸入一條邊依附的兩點(diǎn)及權(quán)值i=localvex(G,v1);/確定頂點(diǎn)V1和V2在圖中的位置j=localvex(G,v2);G.arcsij.adj=w;G.arcsji.adj=w;for(i=0;i!=G.vexnum;+i)for(j=0;j!=G.vexnum;+j)if(G.a

38、rcsij.adj!=1&&G.arcsij.adj<int_max)n+=1;if(n>=1)cout<<"這是一個(gè)有權(quán)圖"<<endl;else cout<<"這是一個(gè)無(wú)權(quán)圖"<<endl;cout<<"圖G鄰接矩陣創(chuàng)建成功！"<<endl;return G.vexnum;void ljjzprint(MGraph_L G) /鄰接矩陣的輸出int i,j;if(n=0)for(i=0;i!=G.vexnum;+i)for(j=0;

39、j!=G.vexnum;+j)if(G.arcsij.adj=int_max)cout<<"0"<<" "else cout<<G.arcsij.adj<<" "cout<<endl;elsefor(i=0;i!=G.vexnum;+i)for(j=0;j!=G.vexnum;+j)if(G.arcsij.adj=int_max)cout<<""<<" "else cout<<G.arcsij.adj

40、<<" "cout<<endl;/|/-鄰接表的定義-typedef struct ArcNode/弧結(jié)點(diǎn)int adjvex;/該弧指向的頂點(diǎn)的位置struct ArcNode *nextarc;/指向下一條弧的指針I(yè)nfoType *info;/該弧相關(guān)信息的指針ArcNode;typedef struct VNode/鄰接鏈表頂點(diǎn)頭接點(diǎn)VertexType data;/頂點(diǎn)信息ArcNode *firstarc;/指向第一條依附該頂點(diǎn)的弧的指針VNode,AdjList;typedef struct/圖的定義AdjList verticesma

41、x;int vexnum,arcnum;/圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)ALGraph;int creatadj(ALGraph &gra,MGraph_L G)/用鄰接表存儲(chǔ)圖int i=0,j=0;ArcNode *arc;for(i=0;i!=G.vexnum;+i)gra.verticesi.data=G.vexsi;gra.verticesi.firstarc=NULL;for(i=0;i!=G.vexnum;+i)for(j=0;j!=G.vexnum;+j)if(G.arcsij.adj!=int_max)arc=(ArcNode *)malloc(sizeof(ArcNode);

42、arc->adjvex=j;arc->nextarc=gra.verticesi.firstarc;gra.verticesi.firstarc=arc;gra.vexnum=G.vexnum;gra.arcnum=G.arcnum;cout<<"圖G鄰接表創(chuàng)建成功！"<<endl;return 1;void adjprint(ALGraph gra,MGraph_L G) /鄰接表輸出int i;for(i=0;i!=gra.vexnum;+i)ArcNode *p;cout<<""<<i&l

43、t;<","<<G.vexsi<<""p=gra.verticesi.firstarc;while(p!=NULL)cout<<"->"<<""<<p->adjvex<<""p=p->nextarc;cout<<"->"<<"End"cout<<endl;/|/-隊(duì)列定義-typedef struct QNodeQEle

44、mType data;struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front;/隊(duì)頭指針QueuePtr rear;/隊(duì)尾指針LinkQueue;/-Status InitQueue(LinkQueue &Q)/初始化隊(duì)列Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)return 0;/存儲(chǔ)分配失敗Q.front->next=NULL;return 1;Status EnQueue(LinkQueue &Q,QElemType e)

45、/入隊(duì),插入元素e為Q的新的隊(duì)尾元素QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p)return 0;/存儲(chǔ)分配失敗p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;return 1;Status DeQueue(LinkQueue &Q,QElemType &e)/出隊(duì)，若隊(duì)列不空，則刪除Q的隊(duì)頭元素，用e返回，并返回真，否則假Q(mào)ueuePtr p;if(Q.front=Q.rear)return 0;p=Q.front->next;e=p->data

46、;Q.front->next=p->next;if(Q.rear=p)Q.rear=Q.front;free(p);return 1;Status QueueEmpty(LinkQueue Q)/判斷隊(duì)為空if(Q.front=Q.rear) return 1;return 0;/-圖的遍歷-int visitedmax;/訪問(wèn)標(biāo)記int we;int firstadjvex(ALGraph gra,VNode v)/返回依附頂點(diǎn)V的第一個(gè)點(diǎn) /即以V為尾的第一個(gè)結(jié)點(diǎn)if(v.firstarc!=NULL)return v.firstarc->adjvex;int nexta

47、djvex(ALGraph gra,VNode v,int w)/返回依附頂點(diǎn)V的相對(duì)于W的下一個(gè)頂點(diǎn)ArcNode *p;p=v.firstarc;while(p!=NULL&&p->adjvex!=w)p=p->nextarc;if(p->adjvex=w&&p->nextarc!=NULL)p=p->nextarc;return p->adjvex;if(p->adjvex=w&&p->nextarc=NULL)return -10;/-廣度優(yōu)先遍歷-void BFSTraverse(ALGr

48、aph gra)int i,e;LinkQueue q;for(i=0;i!=gra.vexnum;+i)visitedi=0;InitQueue(q);for(i=0;i!=gra.vexnum;+i)if(!visitedi) visitedi=1;cout<<gra.verticesi.data;EnQueue(q,i);while(!QueueEmpty(q)DeQueue(q,e);for(we=firstadjvex(gra,gra.verticese);we>=0;we=nextadjvex(gra,gra.verticese,we)if(!visitedwe)

49、visitedwe=1;cout<<gra.verticeswe.data;EnQueue(q,we);/-深度優(yōu)先遍歷-int DFS(ALGraph gra,int i)visitedi=1;int we1;cout<<gra.verticesi.data;for(we=firstadjvex(gra,gra.verticesi);we>=0;we=nextadjvex(gra,gra.verticesi,we)we1=we;if(visitedwe=0)DFS(gra,we);we=we1;return 1;int DFStra(ALGraph gra)in

50、t i,j;for(i=0;i!=gra.vexnum;+i)visitedi=0;for(j=0;j!=gra.vexnum;+j)if(visitedj=0)DFS(gra,j);return 0;/-求連通分量-int DFSTraverse_fen(ALGraph gra)int i,j;for(i=0;i!=gra.vexnum;+i)visitedi=0;for(j=0;j!=gra.vexnum;+j)if(visitedj=0)DFS(gra,j);cout<<endl;l+;return 0;/-最小生成樹(shù)的普利姆算法-typedef structint adjvex;int lowcost;closedge;int MiniSpanTree_PRIM(int gmax,int n) int lowcostmax,prevexmax; /lowcost存儲(chǔ)當(dāng)前集合分別到剩余結(jié)點(diǎn)的最小權(quán)值 /prevex存儲(chǔ)最短路徑的前一個(gè)結(jié)點(diǎn)int i,j,k,min;for(i=2;i<=n;i+) /n個(gè)頂點(diǎn)，n-1條邊lowcosti=g1i; /初始化prevexi=1; /頂點(diǎn)未加入到最小生成樹(shù)中l(wèi)owcost1=0