數(shù)據(jù)結(jié)構(gòu)課程設(shè)計之圖的遍歷和生成樹求解

##大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告題目： 圖的遍歷和生成樹求解 院（系）： 計算機工程學(xué)院 學(xué)生姓名: 班級：學(xué)號: 起迄日期: 2023.6.20 指導(dǎo)教師: 2023—2023年度第2學(xué)期一、需求分析1.問題描述：圖的遍歷和生成樹求解實現(xià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)。生成樹求解重要運用普利姆和克雷斯特算法求解最小生成樹，只有強連通圖才有生成樹。2.基本功能1)先任意創(chuàng)建一個圖；2)圖的DFS,BFS的遞歸和非遞歸算法的實現(xiàn)3)最小生成樹（兩個算法）的實現(xiàn)，求連通分量的實現(xiàn)4)規(guī)定用鄰接矩陣、鄰接表等多種結(jié)構(gòu)存儲實現(xiàn)3.輸入輸出輸入數(shù)據(jù)類型為整型和字符型，輸出為整型和字符二、概要設(shè)計設(shè)計思緒：a.圖的鄰接矩陣存儲：根據(jù)所建無向圖的結(jié)點數(shù)n,建立n*n的矩陣，其中元素全是無窮大（int_max），再將邊的信息存到數(shù)組中。其中無權(quán)圖的邊用1表達，無邊用0表達；有全圖的邊為權(quán)值表達，無邊用∞表達。b.圖的鄰接表存儲：將信息通過鄰接矩陣轉(zhuǎn)換到鄰接表中，即將鄰接矩陣的每一行都轉(zhuǎn)成鏈表的形式將有邊的結(jié)點進行存儲。c.圖的廣度優(yōu)先遍歷：假設(shè)從圖中的某個頂點v出發(fā)，在訪問了v之后依次訪問v的各個未曾訪問過的鄰接點，然后再訪問此鄰接點的未被訪問的鄰接點，并使“先被訪問的頂點的鄰接點”先于“后被訪問的頂點的鄰接點”被訪問，直至圖中所有已被訪問的頂點的鄰接點都被訪問到。若此時圖中尚有未被訪問的，則另選未被訪問的反復(fù)以上環(huán)節(jié)，是一個非遞歸過程。d.圖的深度優(yōu)先遍歷：假設(shè)從圖中某頂點v出發(fā)，依依次訪問v的鄰接頂點，然后再繼續(xù)訪問這個鄰接點的系一個鄰接點，如此反復(fù)，直至所有的點都被訪問，這是個遞歸的過程。e.圖的連通分量：這是對一個非強連通圖的遍歷，從多個結(jié)點出發(fā)進行搜索，而每一次從一個新的起始點出發(fā)進行搜索過程中得到的頂點訪問序列恰為其連通分量的頂點集。本程序運用的圖的深度優(yōu)先遍歷算法。2.數(shù)據(jù)結(jié)構(gòu)設(shè)計：ADTQueue{數(shù)據(jù)對象：D={ai|ai∈ElemSet,i=1,2,3……，n,n≥0}數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1,ai∈D,i=1,2,3,……，n}基本操作：InitQueue(&Q)操作結(jié)果：構(gòu)造一個空隊列Q。QueueEmpty(Q)初始條件：Q為非空隊列。操作結(jié)果：若Q為空隊列，則返回真，否則為假。EnQueue(&Q,e)初始條件：Q為非空隊列。操作結(jié)果：插入元素e為Q的新的隊尾元素。DeQueue(&Q,e)初始條件：Q為非空隊列。操作結(jié)果：刪除Q的隊頭元素，并用e返回其值。}ADTQueueADTGraph{數(shù)據(jù)對象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點集。數(shù)據(jù)關(guān)系R：R={VR}VR={<v,w>|v,w∈V且P（v，w）,<v,w>表達從v到w的弧，謂詞P（v,w）定義了弧<v,w>的意義或信息}基本操作P：CreatGraph(&G,V,VR);初始條件：V是圖的頂點集，VR是圖中弧的集合。操作結(jié)果：按V和VR的定義構(gòu)造圖G。BFSTraverse(G,visit());初始條件：圖G存在，Visit是定點的應(yīng)用函數(shù)。操作結(jié)果：對圖進行廣度優(yōu)先遍歷。在遍歷過程中對每個頂點調(diào)用函數(shù)Visit一次且僅一次。一旦visit（）失敗，則操作失敗。DFSTraverse(G,visit());初始條件：圖G存在，Visit是定點的應(yīng)用函數(shù)。操作結(jié)果：對圖進行廣度優(yōu)先遍歷。在遍歷過程中對每個頂點調(diào)用函數(shù)Visit一次且僅一次。一旦visit（）失敗，則操作失敗。DFStra_fen(G)初始條件：圖G存在，存在圖的深度優(yōu)先遍歷算法。操作結(jié)果：從多個頂點對圖進行深度優(yōu)先遍歷，得到連通分量。}ADTGraph;軟件結(jié)構(gòu)設(shè)計：函數(shù)名返回值類型creatMGraph_L(G)intcreatadj(gra,G)intljjzprint(G)voidadjprint(gra,G)voidBFSTraverse(gra)voidDFStra(gra)intDFSTraverse_fen(gra)intMiniSpanTree_PRIM(g,G.vexnum)intMiniSpanTREE_KRUSCAL(G,gra)void三、具體設(shè)計定義程序中所有用到的數(shù)據(jù)及其數(shù)據(jù)結(jié)構(gòu)，及其基本操作的實現(xiàn)；鄰接矩陣定義:typedefstructArcCell{ VRTypeadj;//VRType是頂點關(guān)系類型。對無權(quán)圖，用1或0表達相鄰否；對帶權(quán)圖，則為權(quán)值類型 InfoType*info;//該弧相關(guān)信息的指針}ArcCell,AdjMatrix[max][max];typedefstruct{ VertexTypevexs[max];//頂點向量 AdjMatrixarcs;//鄰接矩陣 intvexnum,arcnum;//圖的當(dāng)前頂點數(shù)和弧數(shù)}MGraph_L;鄰接表的定義:typedefstructArcNode//弧結(jié)點{ intadjvex;//該弧指向的頂點的位置 structArcNode*nextarc;//指向下一條弧的指針 InfoType*info;//該弧相關(guān)信息的指針}ArcNode;typedefstructVNode//鄰接鏈表頂點頭接點{ VertexTypedata;//頂點信息 ArcNode*firstarc;//指向第一條依附該頂點的弧的指針}VNode,AdjList;typedefstruct//圖的定義{ AdjListvertices[max]; intvexnum,arcnum;//圖的當(dāng)前頂點數(shù)和弧數(shù)}ALGraph;隊列定義:typedefstructQNode{ QElemTypedata; structQNode*next;}QNode,*QueuePtr;typedefstruct{ QueuePtrfront;//隊頭指針 QueuePtrrear;//隊尾指針}LinkQueue;主函數(shù)和其他函數(shù)的偽碼算法；主函數(shù)：intmain(){ ints; chary='y';cout<<"||¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤菜單¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤||"<<endl;cout<<"||-------------------------【0、創(chuàng)建一個無向圖------------------------------||"<<endl;cout<<"||-------------------------【1、顯示該圖的鄰接矩陣--------------------------||"<<endl;cout<<"||-------------------------【2、顯示該圖的鄰接表----------------------------||"<<endl; cout<<"||-------------------------【3、廣度優(yōu)先遍歷--------------------------------||"<<endl;cout<<"||-------------------------【4、深度優(yōu)先遍歷--------------------------------||"<<endl;cout<<"||-------------------------【5、最小生成樹MiniSpanTree_PRIM算法-------------||"<<endl;cout<<"||-------------------------【6、最小生成樹MiniSpanTree_KRUSCAL算法----------||"<<endl;cout<<"||-------------------------【7、連通分量------------------------------------||"<<endl; cout<<"||¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤||"<<endl; while(y=='y') { cout<<"請選擇菜單："<<endl;cin>>s; if(s==0) { ++o; if(o==2) { n=0; l=0; o=0; } } switch(s) { case0:cout<<"創(chuàng)建一個無向圖："<<endl; MGraph_LG; creatMGraph_L(G); ALGraphgra; creatadj(gra,G);break; case1:cout<<"鄰接矩陣顯示如下："<<endl; ljjzprint(G);break;case2:cout<<"鄰接表顯示如下："<<endl;adjprint(gra,G);break;case3:cout<<"廣度優(yōu)先遍歷：";BFSTraverse(gra);cout<<endl;break;case4: cout<<"深度優(yōu)先遍歷：";DFStra(gra);cout<<endl;break;case5: if(n==0){cout<<"無權(quán)圖沒有最小生成樹";break;} elseif(l>0){cout<<"若該圖為非強連通圖(具有多個連通分量)時，最小生成樹不存在"<<endl;break;} else { inti,g[max][max]; for(i=0;i!=G.vexnum;++i) for(intj=0;j!=G.vexnum;++j) g[i+1][j+1]=G.arcs[i][j].adj; cout<<"普利姆算法:"<<endl; MiniSpanTree_PRIM(g,G.vexnum); break; }case6:if(n==0){cout<<"無權(quán)圖沒有最小生成樹";break;} elseif(l>0){cout<<"該圖為非強連通圖(具有多個連通分量)，最小生成樹不存在"<<endl;break;} else { cout<<"克魯斯卡爾算法:"<<endl;MiniSpanTREE_KRUSCAL(G,gra);break; }case7:cout<<"連通分量:"<<endl; DFSTraverse_fen(gra);break; } cout<<endl<<"是否繼續(xù)？y/n:";cin>>y;if(y=='n')break; } return0;}鄰接矩陣存儲：intcreatMGraph_L(MGraph_L&G)//創(chuàng)建圖用鄰接矩陣表達{ charv1,v2; inti,j,w; cout<<"請輸入頂點和弧的個數(shù)"<<endl; cin>>G.vexnum>>G.arcnum; cout<<"輸入各個頂點"<<endl; for(i=0;i<G.vexnum;++i) { cin>>G.vexs[i]; } for(i=0;i<G.vexnum;++i) for(j=0;j<G.vexnum;++j) { G.arcs[i][j].adj=int_max; G.arcs[i][j].info=NULL; } for(intk=0;k<G.arcnum;++k) { cout<<"輸入一條邊依附的頂點和權(quán)"<<endl; cin>>v1>>v2>>w;//輸入一條邊依附的兩點及權(quán)值 i=localvex(G,v1);//擬定頂點V1和V2在圖中的位置 j=localvex(G,v2); G.arcs[i][j].adj=w; G.arcs[j][i].adj=w; } for(i=0;i!=G.vexnum;++i) for(j=0;j!=G.vexnum;++j) { if(G.arcs[i][j].adj!=1&&G.arcs[i][j].adj<int_max)n+=1; } if(n>=1)cout<<"這是一個有權(quán)圖"<<endl; elsecout<<"這是一個無權(quán)圖"<<endl; cout<<"圖G鄰接矩陣創(chuàng)建成功！"<<endl; returnG.vexnum;}鄰接矩陣的輸出：voidljjzprint(MGraph_LG)//鄰接矩陣的輸出{ inti,j; if(n==0) { for(i=0;i!=G.vexnum;++i) { for(j=0;j!=G.vexnum;++j) { if(G.arcs[i][j].adj==int_max){cout<<"0"<<"";} else{cout<<G.arcs[i][j].adj<<"";} } cout<<endl; } } else { for(i=0;i!=G.vexnum;++i) { for(j=0;j!=G.vexnum;++j) { if(G.arcs[i][j].adj==int_max){cout<<"∞"<<"";} else{cout<<G.arcs[i][j].adj<<"";} } cout<<endl; } }}用鄰接表存儲圖：intcreatadj(ALGraph&gra,MGraph_LG)//用鄰接表存儲圖{ inti=0,j=0; ArcNode*arc;//,*tem,*p; for(i=0;i!=G.vexnum;++i) { gra.vertices[i].data=G.vexs[i]; gra.vertices[i].firstarc=NULL; } for(i=0;i!=G.vexnum;++i) for(j=0;j!=G.vexnum;++j) { if(G.arcs[i][j].adj!=int_max) { arc=(ArcNode*)malloc(sizeof(ArcNode)); arc->adjvex=j; arc->nextarc=gra.vertices[i].firstarc; gra.vertices[i].firstarc=arc; } } gra.vexnum=G.vexnum; gra.arcnum=G.arcnum; cout<<"圖G鄰接表創(chuàng)建成功！"<<endl; return1;}鄰接表輸出：voidadjprint(ALGraphgra,MGraph_LG)//鄰接表輸出{ inti; for(i=0;i!=gra.vexnum;++i) { ArcNode*p; cout<<"["<<i<<","<<G.vexs[i]<<"]"; p=gra.vertices[i].firstarc; while(p!=NULL) { cout<<"->"<<"["<<p->adjvex<<"]"; p=p->nextarc; } cout<<"->"<<"End"; cout<<endl; }}初始化隊列：StatusInitQueue(LinkQueue&Q)//初始化隊列{ Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front)return0;//存儲分派失敗 Q.front->next=NULL; return1;}入隊：StatusEnQueue(LinkQueue&Q,QElemTypee)//入隊,插入元素e為Q的新的隊尾元素{ QueuePtrp; p=(QueuePtr)malloc(sizeof(QNode)); if(!p)return0;//存儲分派失敗 p->data=e;p->next=NULL; Q.rear->next=p;Q.rear=p; return1;}出隊：StatusDeQueue(LinkQueue&Q,QElemType&e)//出隊，若隊列不空，則刪除Q的隊頭元素，用e返回，并返回真，否則假{ QueuePtrp; if(Q.front==Q.rear)return0; p=Q.front->next; e=p->data; Q.front->next=p->next; if(Q.rear==p)Q.rear=Q.front; free(p); return1;}判斷隊為空：StatusQueueEmpty(LinkQueueQ)//判斷隊為空{(diào) if(Q.front==Q.rear)return1; return0;}廣度優(yōu)先遍歷：voidBFSTraverse(ALGraphgra){ inti,e; LinkQueueq; for(i=0;i!=gra.vexnum;++i)visited[i]=0; InitQueue(q); for(i=0;i!=gra.vexnum;++i) if(!visited[i]) { visited[i]=1; cout<<gra.vertices[i].data; EnQueue(q,i); while(!QueueEmpty(q)) { DeQueue(q,e); for(we=firstadjvex(gra,gra.vertices[e]);we>=0;we=nextadjvex(gra,gra.vertices[e],we)) { if(!visited[we]) { visited[we]=1; cout<<gra.vertices[we].data; EnQueue(q,we); } } } }}深度優(yōu)先遍歷：intDFS(ALGraphgra,inti){ visited[i]=1; intwe1; cout<<gra.vertices[i].data; for(we=firstadjvex(gra,gra.vertices[i]);we>=0;we=nextadjvex(gra,gra.vertices[i],we)) { we1=we; if(visited[we]==0) DFS(gra,we); we=we1; } return1;}intDFStra(ALGraphgra){ inti,j; for(i=0;i!=gra.vexnum;++i) { visited[i]=0; } for(j=0;j!=gra.vexnum;++j) { if(visited[j]==0)DFS(gra,j); } return0;}連通分量：intDFSTraverse_fen(ALGraphgra){ inti,j; for(i=0;i!=gra.vexnum;++i) visited[i]=0; for(j=0;j!=gra.vexnum;++j) { if(visited[j]==0) { DFS(gra,j); cout<<endl; l++; } } return0;}重要函數(shù)的程序流程圖，實現(xiàn)設(shè)計中主程序和其他子模塊的算法，以流程圖的形式表達。圖的廣度優(yōu)先遍歷圖的鄰接矩陣存儲圖的鄰接表存儲圖的廣度優(yōu)先遍歷圖的鄰接矩陣存儲圖的鄰接表存儲圖的普利姆算法求最小生成樹圖的普利姆算法求最小生成樹調(diào)試分析實際完畢的情況說明；a.先任意創(chuàng)建一個圖；b.圖的DFS,BFS的遞歸和非遞歸算法的實現(xiàn)c.最小生成樹（兩個算法）的實現(xiàn)，求連通分量的實現(xiàn)d.規(guī)定用鄰接矩陣、鄰接表等多種結(jié)構(gòu)存儲實現(xiàn)支持的數(shù)據(jù)類型：整型和字符型2.程序的性能分析，涉及時空分析；本程序的圖的遍歷是以鄰接表做圖的存儲結(jié)構(gòu)，其時間復(fù)雜度為O（n+e）。3.上機過程中出現(xiàn)的問題及其解決方案；a.程序開始對無權(quán)圖和有權(quán)圖的鄰接矩陣的輸出時，無邊都用的10000（無窮大int_max）表達的，這種表達和我們習(xí)慣上的0與∞的表達有差異。所以在程序中定義了全局變量n（初值為0）,來判斷創(chuàng)建的無向圖是有權(quán)圖還是無權(quán)圖，n>0為有權(quán)圖，此時輸出的時候用∞代替10000；n=0為無權(quán)圖，此時輸出的時候用0代替10000.b.程序中有的功能對某些圖是不合用的，比如無權(quán)圖沒有最小生成樹，非強連通圖沒有最小生成樹等。所以在程序中又新增了全局變量l,l>0時表達為非強連通圖，則在求最小生成樹時報錯。C.當(dāng)程序先創(chuàng)建一個有權(quán)圖后，n的值會大于1，第二次創(chuàng)無權(quán)圖時也會被程序認為有權(quán)圖，所以在程序中在定義全局變量o（初值為0）,來判斷創(chuàng)建了幾次圖，當(dāng)?shù)诙蝿?chuàng)建圖，即o=2時，所有全局變量在開始全歸零。程序中可以改善的地方說明；當(dāng)建立一個圖時先得求其連通分量，從而擬定全局變量l的值，從而才干判斷該圖是否有最小生成樹。測試結(jié)果創(chuàng)建一個無權(quán)圖：創(chuàng)建一個費強連通的有權(quán)圖：創(chuàng)建一個有權(quán)連通圖：用戶手冊a.先選0創(chuàng)建一個圖。b.選擇y繼續(xù)操作。c.按照菜單編碼選擇操作。七、體會與自我評價在做這個程序的時候你一方面必須知道圖的一些概念，圖是一種較線性表和樹更為復(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ù)雜的一件事，規(guī)定做到具體到實現(xiàn)該方法的每一個環(huán)節(jié)，然后再將每一個環(huán)節(jié)通過代碼實現(xiàn)。這規(guī)定我們要明確各個數(shù)據(jù)元素和個元素之間的關(guān)系，然后才干明確使用算法去調(diào)用這些數(shù)據(jù)。通過本次的課程設(shè)計，我對數(shù)據(jù)結(jié)構(gòu)有了一定的結(jié)識，明白了數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)，數(shù)據(jù)關(guān)系，及對其操作的方法。但同時也發(fā)現(xiàn)在自己有很多的局限性，在使用語言和如何精煉語言需要進行更多的訓(xùn)練。源代碼：#include<iostream>#include<malloc.h>usingnamespacestd;#defineint_max10000//最大值staticintn=0;//全局變量，判斷有權(quán)圖和無權(quán)圖staticinto=0;//全局變量，清除BUGstaticintl=0;//全局變量，清除BUG#defineinf9999//最小值的最大值#definemax20//最大頂點個數(shù)typedefintVRType,QElemType,Status;typedefcharInfoType,VertexType;//|||||||||||||||||||||||||鄰接矩陣|||||||||||||||||||||||||||||||//----------------------------鄰接矩陣定義-------------------------typedefstructArcCell{ VRTypeadj;//VRType是頂點關(guān)系類型。對無權(quán)圖，用1或0表達相鄰否；對帶權(quán)圖，則為權(quán)值類型 InfoType*info;//該弧相關(guān)信息的指針}ArcCell,AdjMatrix[max][max];typedefstruct{ VertexTypevexs[max];//頂點向量 AdjMatrixarcs;//鄰接矩陣 intvexnum,arcnum;//圖的當(dāng)前頂點數(shù)和弧數(shù)}MGraph_L;//-----------------------------------------------------------------intlocalvex(MGraph_LG,charv)//返回V的位置{ inti=0; while(G.vexs[i]!=v)++i; returni;}intcreatMGraph_L(MGraph_L&G)//創(chuàng)建圖用鄰接矩陣表達{ charv1,v2; inti,j,w; cout<<"請輸入頂點和弧的個數(shù)"<<endl; cin>>G.vexnum>>G.arcnum; cout<<"輸入各個頂點"<<endl; for(i=0;i<G.vexnum;++i) { cin>>G.vexs[i]; } for(i=0;i<G.vexnum;++i) for(j=0;j<G.vexnum;++j) { G.arcs[i][j].adj=int_max; G.arcs[i][j].info=NULL; } for(intk=0;k<G.arcnum;++k) { cout<<"輸入一條邊依附的頂點和權(quán)"<<endl; cin>>v1>>v2>>w;//輸入一條邊依附的兩點及權(quán)值 i=localvex(G,v1);//擬定頂點V1和V2在圖中的位置 j=localvex(G,v2); G.arcs[i][j].adj=w; G.arcs[j][i].adj=w; } for(i=0;i!=G.vexnum;++i) for(j=0;j!=G.vexnum;++j) { if(G.arcs[i][j].adj!=1&&G.arcs[i][j].adj<int_max)n+=1; } if(n>=1)cout<<"這是一個有權(quán)圖"<<endl; elsecout<<"這是一個無權(quán)圖"<<endl; cout<<"圖G鄰接矩陣創(chuàng)建成功！"<<endl; returnG.vexnum;}voidljjzprint(MGraph_LG)//鄰接矩陣的輸出{ inti,j; if(n==0) { for(i=0;i!=G.vexnum;++i) { for(j=0;j!=G.vexnum;++j) { if(G.arcs[i][j].adj==int_max){cout<<"0"<<"";} else{cout<<G.arcs[i][j].adj<<"";} } cout<<endl; } } else { for(i=0;i!=G.vexnum;++i) { for(j=0;j!=G.vexnum;++j) { if(G.arcs[i][j].adj==int_max){cout<<"∞"<<"";} else{cout<<G.arcs[i][j].adj<<"";} } cout<<endl; } }}//||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||//-------------------------鄰接表的定義-----------------------typedefstructArcNode//弧結(jié)點{ intadjvex;//該弧指向的頂點的位置 structArcNode*nextarc;//指向下一條弧的指針 InfoType*info;//該弧相關(guān)信息的指針}ArcNode;typedefstructVNode//鄰接鏈表頂點頭接點{ VertexTypedata;//頂點信息 ArcNode*firstarc;//指向第一條依附該頂點的弧的指針}VNode,AdjList;typedefstruct//圖的定義{ AdjListvertices[max]; intvexnum,arcnum;//圖的當(dāng)前頂點數(shù)和弧數(shù)}ALGraph;intcreatadj(ALGraph&gra,MGraph_LG)//用鄰接表存儲圖{ inti=0,j=0; ArcNode*arc; for(i=0;i!=G.vexnum;++i) { gra.vertices[i].data=G.vexs[i]; gra.vertices[i].firstarc=NULL; } for(i=0;i!=G.vexnum;++i) for(j=0;j!=G.vexnum;++j) { if(G.arcs[i][j].adj!=int_max) { arc=(ArcNode*)malloc(sizeof(ArcNode)); arc->adjvex=j; arc->nextarc=gra.vertices[i].firstarc; gra.vertices[i].firstarc=arc; } } gra.vexnum=G.vexnum; gra.arcnum=G.arcnum; cout<<"圖G鄰接表創(chuàng)建成功！"<<endl; return1;}voidadjprint(ALGraphgra,MGraph_LG)//鄰接表輸出{ inti; for(i=0;i!=gra.vexnum;++i) { ArcNode*p; cout<<"["<<i<<","<<G.vexs[i]<<"]"; p=gra.vertices[i].firstarc; while(p!=NULL) { cout<<"->"<<"["<<p->adjvex<<"]"; p=p->nextarc; } cout<<"->"<<"End"; cout<<endl; }}//||||||||||||||||||||||||||||||||||||||||||||||||||||||||||//------------------------隊列定義------------------------typedefstructQNode{ QElemTypedata; structQNode*next;}QNode,*QueuePtr;typedefstruct{ QueuePtrfront;//隊頭指針 QueuePtrrear;//隊尾指針}LinkQueue;//---------------------------------------------------------StatusInitQueue(LinkQueue&Q)//初始化隊列{ Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front)return0;//存儲分派失敗 Q.front->next=NULL; return1;}StatusEnQueue(LinkQueue&Q,QElemTypee)//入隊,插入元素e為Q的新的隊尾元素{ QueuePtrp; p=(QueuePtr)malloc(sizeof(QNode)); if(!p)return0;//存儲分派失敗 p->data=e;p->next=NULL; Q.rear->next=p;Q.rear=p; return1;}StatusDeQueue(LinkQueue&Q,QElemType&e)//出隊，若隊列不空，則刪除Q的隊頭元素，用e返回，并返回真，否則假{ QueuePtrp; if(Q.front==Q.rear)return0; p=Q.front->next; e=p->data; Q.front->next=p->next; if(Q.rear==p)Q.rear=Q.front; free(p); return1;}StatusQueueEmpty(LinkQueueQ)//判斷隊為空{(diào) if(Q.front==Q.rear)return1; return0;}//----------------------------圖的遍歷----------------------------intvisited[max];//訪問標(biāo)記intwe;intfirstadjvex(ALGraphgra,VNodev)//返回依附頂點V的第一個點//即以V為尾的第一個結(jié)點{ if(v.firstarc!=NULL)returnv.firstarc->adjvex;}intnextadjvex(ALGraphgra,VNodev,intw)//返回依附頂點V的相對于W的下一個頂點{ ArcNode*p; p=v.firstarc; while(p!=NULL&&p->adjvex!=w) { p=p->nextarc; } if(p->adjvex==w&&p->nextarc!=NULL) { p=p->nextarc; returnp->adjvex; } if(p->adjvex==w&&p->nextarc==NULL) return-10;}//----------------------------廣度優(yōu)先遍歷----------------------------voidBFSTraverse(ALGraphgra){ inti,e; LinkQueueq; for(i=0;i!=gra.vexnum;++i)visited[i]=0; InitQueue(q); for(i=0;i!=gra.vexnum;++i) if(!visited[i]) { visited[i]=1; cout<<gra.vertices[i].data; EnQueue(q,i); while(!QueueEmpty(q)) { DeQueue(q,e); for(we=firstadjvex(gra,gra.vertices[e]);we>=0;we=nextadjvex(gra,gra.vertices[e],we)) { if(!visited[we]) { visited[we]=1; cout<<gra.vertices[we].data; EnQueue(q,we); } } } }}//---------------------------------深度優(yōu)先遍歷--------------------------------intDFS(ALGraphgra,inti){ visited[i]=1; intwe1; cout<<gra.vertices[i].data; for(we=firstadjvex(gra,gra.vertices[i]);we>=0;we=nextadjvex(gra,gra.vertices[i],we)) { we1=we; if(visited[we]==0) DFS(gra,we); we=we1; } return1;}intDFStra(ALGraphgra){ inti,j; for(i=0;i!=gra.vexnum;++i) { visited[i]=0; } for(j=0;j!=gra.vexnum;++j) { if(visited[j]==0)DFS(gra,j); } return0;}//----------------------------求連通分量------------------------------intDFSTraverse_fen(ALGraphgra){ inti,j; for(i=0;i!=gra.vexnum;++i) visited[i]=0; for(j=0;j!=gra.vexnum;++j) { if(visited[j]==0) { DFS(gra,j); cout<<endl; l++; } } return0;}//-----------------------------最小生成樹的普利姆算法-----------------------------typedefstruct{ intadjvex; intlowcost;}closedge;intMiniSpanTree_PRIM(intg[][max],intn){ intlowcost[max],prevex[max];//lowcost[]存儲當(dāng)前集合分別到剩余結(jié)點的最小權(quán)值//prevex[]存儲最短途徑的前一個結(jié)點 inti,j,k,min; for(i=2;i<=n;i++)//n個頂點，n-1條邊 { lowcost[i]=g[1][i];//初始化 prevex[i]=1;//頂點未加入到最小生成樹中 } lowcost[1]=0;//標(biāo)志頂點1加入U集合 for(i=2;i<=n;i++)//形成n-1條邊的生成樹 { min=inf; k=0; for(j=2;j<=n;j++)//尋找滿足邊的一個頂點在U,另一個頂點在V的最小邊 if((lowcost[j]<min)&&(lowcost[j]!=0)) { min=lowcost[j]; k=j; } cout<<"("<<prevex[k]-1<<","<<k-1<<")"<<min; lowcost[k]=0;//頂點k加入U for(j=2;j<=n;j++)//修改由頂點k到其他頂點邊的權(quán)值 if(g[k][j]<lowcost[j]) { lowcost[j]=g[k][j]; prevex[j]=k; } cout<<endl; } return0;}//-------------------------最小生成樹的克魯斯卡爾算法---------------------------intacrvisited[max];//克魯斯卡爾弧標(biāo)記數(shù)組intfind(intacrvisited[],intf){ while(acrvisited[f]>0)f=acrvisited[f]; returnf;}typedefstructacr{ intpre;//弧的一結(jié)點 intbak;//弧另一結(jié)點 intweight;//弧的權(quán)}edg;voidMiniSpanTREE_KRUSCAL(MGraph_LG,ALGraphgra){ edgedgs[max]; inti,j,k=0; for(i=0;i!=G.vexnum;++i) for(j=i;j!=G.vexnum;++j) { if(G.arcs[i][j].adj!=int_max) { edgs[k].pre=i; edgs[k].bak=j; edgs[k].weight=G.arcs[i][j].adj; ++k; } } intx,y,m,n; intbuf,edf; for(i=0;i!=gra.arcnum;++i) acrvisited[i]=0; for(j=0;j!=G.arcnum;++j) { m=int_max; for(i=0;i!=G.arcnum;++i) { if(edgs[i].weight<m) { m=edgs[i].weight; x=edgs[i].pre; y=edgs[i].bak; n=i; } } buf=find(acrvisited,x); edf=find(acrvisited,y); edgs[n].weight=int_max; if(buf!=edf) { acrvisited[buf]=edf; cout<<"("<<x<<","<<y<<")"<<m; cout<<endl; } }}intmain(){ ints; chary='y';cout<<"||¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤菜單¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤||"<<endl;cout<<"||-------------------------【0、創(chuàng)建一個無向圖------------------------------||"<<endl;cout<<"||-------------------------【1、顯示該圖的鄰