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

##大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告題目： 圖的遍歷和生成樹求解 院（系）： 計(jì)算機(jī)工程學(xué)院 學(xué)生姓名: 班級(jí)：學(xué)號(hào): 起迄日期: 2023.6.20 指導(dǎo)教師: 2023—2023年度第2學(xué)期一、需求分析1.問(wèn)題描述：圖的遍歷和生成樹求解實(shí)現(xiàn)圖是一種較線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在線性表中，數(shù)據(jù)元素之間僅有線性關(guān)系，每個(gè)數(shù)據(jù)元素只有一個(gè)直接前驅(qū)和一個(gè)直接后繼；在樹形結(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)。生成樹求解重要運(yùn)用普利姆和克雷斯特算法求解最小生成樹，只有強(qiáng)連通圖才有生成樹。2.基本功能1)先任意創(chuàng)建一個(gè)圖；2)圖的DFS,BFS的遞歸和非遞歸算法的實(shí)現(xiàn)3)最小生成樹（兩個(gè)算法）的實(shí)現(xiàn)，求連通分量的實(shí)現(xiàn)4)規(guī)定用鄰接矩陣、鄰接表等多種結(jié)構(gòu)存儲(chǔ)實(shí)現(xiàn)3.輸入輸出輸入數(shù)據(jù)類型為整型和字符型，輸出為整型和字符二、概要設(shè)計(jì)設(shè)計(jì)思緒：a.圖的鄰接矩陣存儲(chǔ)：根據(jù)所建無(wú)向圖的結(jié)點(diǎn)數(shù)n,建立n*n的矩陣，其中元素全是無(wú)窮大（int_max），再將邊的信息存到數(shù)組中。其中無(wú)權(quán)圖的邊用1表達(dá)，無(wú)邊用0表達(dá)；有全圖的邊為權(quán)值表達(dá)，無(wú)邊用∞表達(dá)。b.圖的鄰接表存儲(chǔ)：將信息通過(guò)鄰接矩陣轉(zhuǎn)換到鄰接表中，即將鄰接矩陣的每一行都轉(zhuǎn)成鏈表的形式將有邊的結(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ù)以上環(huán)節(jié)，是一個(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)出發(fā)進(jìn)行搜索過(guò)程中得到的頂點(diǎn)訪問(wèn)序列恰為其連通分量的頂點(diǎn)集。本程序運(yùn)用的圖的深度優(yōu)先遍歷算法。2.數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：ADTQueue{數(shù)據(jù)對(duì)象：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)造一個(gè)空隊(duì)列Q。QueueEmpty(Q)初始條件：Q為非空隊(duì)列。操作結(jié)果：若Q為空隊(duì)列，則返回真，否則為假。EnQueue(&Q,e)初始條件：Q為非空隊(duì)列。操作結(jié)果：插入元素e為Q的新的隊(duì)尾元素。DeQueue(&Q,e)初始條件：Q為非空隊(duì)列。操作結(jié)果：刪除Q的隊(duì)頭元素，并用e返回其值。}ADTQueueADTGraph{數(shù)據(jù)對(duì)象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。數(shù)據(jù)關(guān)系R：R={VR}VR={<v,w>|v,w∈V且P（v，w）,<v,w>表達(dá)從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é)果：對(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)先遍歷，得到連通分量。}ADTGraph;軟件結(jié)構(gòu)設(shè)計(jì)：函數(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è)計(jì)定義程序中所有用到的數(shù)據(jù)及其數(shù)據(jù)結(jié)構(gòu)，及其基本操作的實(shí)現(xiàn)；鄰接矩陣定義:typedefstructArcCell{ VRTypeadj;//VRType是頂點(diǎn)關(guān)系類型。對(duì)無(wú)權(quán)圖，用1或0表達(dá)相鄰否；對(duì)帶權(quán)圖，則為權(quán)值類型 InfoType*info;//該弧相關(guān)信息的指針}ArcCell,AdjMatrix[max][max];typedefstruct{ VertexTypevexs[max];//頂點(diǎn)向量 AdjMatrixarcs;//鄰接矩陣 intvexnum,arcnum;//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)}MGraph_L;鄰接表的定義:typedefstructArcNode//弧結(jié)點(diǎn){ intadjvex;//該弧指向的頂點(diǎn)的位置 structArcNode*nextarc;//指向下一條弧的指針 InfoType*info;//該弧相關(guān)信息的指針}ArcNode;typedefstructVNode//鄰接鏈表頂點(diǎn)頭接點(diǎn){ VertexTypedata;//頂點(diǎn)信息 ArcNode*firstarc;//指向第一條依附該頂點(diǎn)的弧的指針}VNode,AdjList;typedefstruct//圖的定義{ AdjListvertices[max]; intvexnum,arcnum;//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)}ALGraph;隊(duì)列定義:typedefstructQNode{ QElemTypedata; structQNode*next;}QNode,*QueuePtr;typedefstruct{ QueuePtrfront;//隊(duì)頭指針 QueuePtrrear;//隊(duì)尾指針}LinkQueue;主函數(shù)和其他函數(shù)的偽碼算法；主函數(shù)：intmain(){ ints; chary='y';cout<<"||¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤菜單¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤||"<<endl;cout<<"||-------------------------【0、創(chuàng)建一個(gè)無(wú)向圖------------------------------||"<<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<<"請(qǐng)選擇菜單："<<endl;cin>>s; if(s==0) { ++o; if(o==2) { n=0; l=0; o=0; } } switch(s) { case0:cout<<"創(chuàng)建一個(gè)無(wú)向圖："<<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<<"無(wú)權(quán)圖沒有最小生成樹";break;} elseif(l>0){cout<<"若該圖為非強(qiáng)連通圖(具有多個(gè)連通分量)時(shí)，最小生成樹不存在"<<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<<"無(wú)權(quán)圖沒有最小生成樹";break;} elseif(l>0){cout<<"該圖為非強(qiáng)連通圖(具有多個(gè)連通分量)，最小生成樹不存在"<<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;}鄰接矩陣存儲(chǔ)：intcreatMGraph_L(MGraph_L&G)//創(chuàng)建圖用鄰接矩陣表達(dá){ charv1,v2; inti,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.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<<"輸入一條邊依附的頂點(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.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<<"這是一個(gè)有權(quán)圖"<<endl; elsecout<<"這是一個(gè)無(wú)權(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; } }}用鄰接表存儲(chǔ)圖：intcreatadj(ALGraph&gra,MGraph_LG)//用鄰接表存儲(chǔ)圖{ 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; }}初始化隊(duì)列：StatusInitQueue(LinkQueue&Q)//初始化隊(duì)列{ Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front)return0;//存儲(chǔ)分派失敗 Q.front->next=NULL; return1;}入隊(duì)：StatusEnQueue(LinkQueue&Q,QElemTypee)//入隊(duì),插入元素e為Q的新的隊(duì)尾元素{ QueuePtrp; p=(QueuePtr)malloc(sizeof(QNode)); if(!p)return0;//存儲(chǔ)分派失敗 p->data=e;p->next=NULL; Q.rear->next=p;Q.rear=p; return1;}出隊(duì)：StatusDeQueue(LinkQueue&Q,QElemType&e)//出隊(duì)，若隊(duì)列不空，則刪除Q的隊(duì)頭元素，用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;}判斷隊(duì)為空：StatusQueueEmpty(LinkQueueQ)//判斷隊(duì)為空{(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ù)的程序流程圖，實(shí)現(xiàn)設(shè)計(jì)中主程序和其他子模塊的算法，以流程圖的形式表達(dá)。圖的廣度優(yōu)先遍歷圖的鄰接矩陣存儲(chǔ)圖的鄰接表存儲(chǔ)圖的廣度優(yōu)先遍歷圖的鄰接矩陣存儲(chǔ)圖的鄰接表存儲(chǔ)圖的普利姆算法求最小生成樹圖的普利姆算法求最小生成樹調(diào)試分析實(shí)際完畢的情況說(shuō)明；a.先任意創(chuàng)建一個(gè)圖；b.圖的DFS,BFS的遞歸和非遞歸算法的實(shí)現(xiàn)c.最小生成樹（兩個(gè)算法）的實(shí)現(xiàn)，求連通分量的實(shí)現(xiàn)d.規(guī)定用鄰接矩陣、鄰接表等多種結(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.程序開始對(duì)無(wú)權(quán)圖和有權(quán)圖的鄰接矩陣的輸出時(shí)，無(wú)邊都用的10000（無(wú)窮大int_max）表達(dá)的，這種表達(dá)和我們習(xí)慣上的0與∞的表達(dá)有差異。所以在程序中定義了全局變量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ì)某些圖是不合用的，比如無(wú)權(quán)圖沒有最小生成樹，非強(qiáng)連通圖沒有最小生成樹等。所以在程序中又新增了全局變量l,l>0時(shí)表達(dá)為非強(qiáng)連通圖，則在求最小生成樹時(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í)，所有全局變量在開始全歸零。程序中可以改善的地方說(shuō)明；當(dāng)建立一個(gè)圖時(shí)先得求其連通分量，從而擬定全局變量l的值，從而才干判斷該圖是否有最小生成樹。測(cè)試結(jié)果創(chuàng)建一個(gè)無(wú)權(quán)圖：創(chuàng)建一個(gè)費(fèi)強(qiáng)連通的有權(quán)圖：創(chuàng)建一個(gè)有權(quán)連通圖：用戶手冊(cè)a.先選0創(chuàng)建一個(gè)圖。b.選擇y繼續(xù)操作。c.按照菜單編碼選擇操作。七、體會(huì)與自我評(píng)價(jià)在做這個(gè)程序的時(shí)候你一方面必須知道圖的一些概念，圖是一種較線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在線性表中，數(shù)據(jù)元素之間僅有線性關(guān)系，每個(gè)數(shù)據(jù)元素只有一個(gè)直接前驅(qū)和一個(gè)直接后繼；在樹形結(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中的方法把它寫成電腦算法。對(duì)一個(gè)圖我們還定義了連通分量，所以將圖存到電腦中時(shí)，我們對(duì)連通分量得有個(gè)算法。求圖的最小生成樹有兩種算法，普利姆是從結(jié)點(diǎn)出發(fā)尋找權(quán)最小的邊，知道所有結(jié)點(diǎn)都練通了；而克魯斯卡爾算法則是從邊出發(fā)，尋找使圖連通的權(quán)值最小邊的方法。算法的實(shí)現(xiàn)從人腦到電腦的轉(zhuǎn)變是比較復(fù)雜的一件事，規(guī)定做到具體到實(shí)現(xiàn)該方法的每一個(gè)環(huán)節(jié)，然后再將每一個(gè)環(huán)節(jié)通過(guò)代碼實(shí)現(xiàn)。這規(guī)定我們要明確各個(gè)數(shù)據(jù)元素和個(gè)元素之間的關(guān)系，然后才干明確使用算法去調(diào)用這些數(shù)據(jù)。通過(guò)本次的課程設(shè)計(jì)，我對(duì)數(shù)據(jù)結(jié)構(gòu)有了一定的結(jié)識(shí)，明白了數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)，數(shù)據(jù)關(guān)系，及對(duì)其操作的方法。但同時(shí)也發(fā)現(xiàn)在自己有很多的局限性，在使用語(yǔ)言和如何精煉語(yǔ)言需要進(jìn)行更多的訓(xùn)練。源代碼：#include<iostream>#include<malloc.h>usingnamespacestd;#defineint_max10000//最大值staticintn=0;//全局變量，判斷有權(quán)圖和無(wú)權(quán)圖staticinto=0;//全局變量，清除BUGstaticintl=0;//全局變量，清除BUG#defineinf9999//最小值的最大值#definemax20//最大頂點(diǎn)個(gè)數(shù)typedefintVRType,QElemType,Status;typedefcharInfoType,VertexType;//|||||||||||||||||||||||||鄰接矩陣|||||||||||||||||||||||||||||||//----------------------------鄰接矩陣定義-------------------------typedefstructArcCell{ VRTypeadj;//VRType是頂點(diǎn)關(guān)系類型。對(duì)無(wú)權(quán)圖，用1或0表達(dá)相鄰否；對(duì)帶權(quán)圖，則為權(quán)值類型 InfoType*info;//該弧相關(guān)信息的指針}ArcCell,AdjMatrix[max][max];typedefstruct{ VertexTypevexs[max];//頂點(diǎn)向量 AdjMatrixarcs;//鄰接矩陣 intvexnum,arcnum;//圖的當(dāng)前頂點(diǎn)數(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)建圖用鄰接矩陣表達(dá){ charv1,v2; inti,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.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<<"輸入一條邊依附的頂點(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.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<<"這是一個(gè)有權(quán)圖"<<endl; elsecout<<"這是一個(gè)無(wú)權(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é)點(diǎn){ intadjvex;//該弧指向的頂點(diǎn)的位置 structArcNode*nextarc;//指向下一條弧的指針 InfoType*info;//該弧相關(guān)信息的指針}ArcNode;typedefstructVNode//鄰接鏈表頂點(diǎn)頭接點(diǎn){ VertexTypedata;//頂點(diǎn)信息 ArcNode*firstarc;//指向第一條依附該頂點(diǎn)的弧的指針}VNode,AdjList;typedefstruct//圖的定義{ AdjListvertices[max]; intvexnum,arcnum;//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)}ALGraph;intcreatadj(ALGraph&gra,MGraph_LG)//用鄰接表存儲(chǔ)圖{ 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; }}//||||||||||||||||||||||||||||||||||||||||||||||||||||||||||//------------------------隊(duì)列定義------------------------typedefstructQNode{ QElemTypedata; structQNode*next;}QNode,*QueuePtr;typedefstruct{ QueuePtrfront;//隊(duì)頭指針 QueuePtrrear;//隊(duì)尾指針}LinkQueue;//---------------------------------------------------------StatusInitQueue(LinkQueue&Q)//初始化隊(duì)列{ Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front)return0;//存儲(chǔ)分派失敗 Q.front->next=NULL; return1;}StatusEnQueue(LinkQueue&Q,QElemTypee)//入隊(duì),插入元素e為Q的新的隊(duì)尾元素{ QueuePtrp; p=(QueuePtr)malloc(sizeof(QNode)); if(!p)return0;//存儲(chǔ)分派失敗 p->data=e;p->next=NULL; Q.rear->next=p;Q.rear=p; return1;}StatusDeQueue(LinkQueue&Q,QElemType&e)//出隊(duì)，若隊(duì)列不空，則刪除Q的隊(duì)頭元素，用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)//判斷隊(duì)為空{(diào) if(Q.front==Q.rear)return1; return0;}//----------------------------圖的遍歷----------------------------intvisited[max];//訪問(wèn)標(biāo)記intwe;intfirstadjvex(ALGraphgra,VNodev)//返回依附頂點(diǎn)V的第一個(gè)點(diǎn)//即以V為尾的第一個(gè)結(jié)點(diǎn){ if(v.firstarc!=NULL)returnv.firstarc->adjvex;}intnextadjvex(ALGraphgra,VNodev,intw)//返回依附頂點(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; 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[]存儲(chǔ)當(dāng)前集合分別到剩余結(jié)點(diǎn)的最小權(quán)值//prevex[]存儲(chǔ)最短途徑的前一個(gè)結(jié)點(diǎn) inti,j,k,min; for(i=2;i<=n;i++)//n個(gè)頂點(diǎn)，n-1條邊 { lowcost[i]=g[1][i];//初始化 prevex[i]=1;//頂點(diǎn)未加入到最小生成樹中 } lowcost[1]=0;//標(biāo)志頂點(diǎn)1加入U(xiǎn)集合 for(i=2;i<=n;i++)//形成n-1條邊的生成樹 { min=inf; k=0; for(j=2;j<=n;j++)//尋找滿足邊的一個(gè)頂點(diǎn)在U,另一個(gè)頂點(diǎn)在V的最小邊 if((lowcost[j]<min)&&(lowcost[j]!=0)) { min=lowcost[j]; k=j; } cout<<"("<<prevex[k]-1<<","<<k-1<<")"<<min; lowcost[k]=0;//頂點(diǎn)k加入U(xiǎn) for(j=2;j<=n;j++)//修改由頂點(diǎn)k到其他頂點(diǎn)邊的權(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é)點(diǎn) intbak;//弧另一結(jié)點(diǎn) 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)建一個(gè)無(wú)向圖------------------------------||"<<endl;cout<<"||-------------------------【1、顯示該圖的鄰