圖的遍歷和生成樹求解實(shí)現(xiàn) 課程設(shè)計(jì)報(bào)告

中北大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)說明書

學(xué)生姓名:郭燕文學(xué)號(hào)：1021011720學(xué)院:軟件學(xué)院專業(yè):軟件工程題目:圖的遍歷和生成樹求解實(shí)現(xiàn)成績指導(dǎo)教師尹四清、薛海麗

2011年12月19日設(shè)計(jì)目的：《數(shù)據(jù)結(jié)構(gòu)》課程主要介紹最常用的數(shù)據(jù)結(jié)構(gòu)，闡明各種數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系，討論其在計(jì)算機(jī)中的存儲(chǔ)表示，以及在其上進(jìn)行各種運(yùn)算時(shí)的實(shí)現(xiàn)算法，并對(duì)算法的效率進(jìn)行簡單的分析和討論。進(jìn)行數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)要達(dá)到以下目的：了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力；初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測試等基本方法和技能；提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問題的能力；訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。2設(shè)計(jì)內(nèi)容和要求設(shè)計(jì)內(nèi)容：采用合適的存儲(chǔ)結(jié)構(gòu)來創(chuàng)建圖，并實(shí)現(xiàn)圖的遍歷；（2）計(jì)算圖的最小生成樹，求聯(lián)通分量設(shè)計(jì)要求：（1）先任意創(chuàng)建一個(gè)圖；（2)

圖的DFS,BFS的遞歸和非遞歸算法的實(shí)現(xiàn)（3)

最小生成樹（兩個(gè)算法）的實(shí)現(xiàn)，求連通分量的實(shí)現(xiàn)（4)

要求用鄰接矩陣、鄰接表、十字鏈表多種結(jié)構(gòu)存儲(chǔ)實(shí)現(xiàn)3．本設(shè)計(jì)所采用的數(shù)據(jù)結(jié)構(gòu)：本程序是采用鄰接矩陣、鄰接表、十字鏈表等多種結(jié)構(gòu)存儲(chǔ)來實(shí)現(xiàn)對(duì)圖的存儲(chǔ)。對(duì)圖的遍歷分別采用了廣度優(yōu)先遍歷和深度優(yōu)先遍歷。4.1詳細(xì)設(shè)計(jì)思想這次課程設(shè)計(jì)我們主要是應(yīng)用以前學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)與面向?qū)ο蟪绦蛟O(shè)計(jì)知識(shí)，結(jié)合起來才完成了這個(gè)程序。因?yàn)閳D是一種較線形表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在線形表中，數(shù)據(jù)元素之間僅有線性關(guān)系，每個(gè)元素只有一個(gè)直接前驅(qū)和一個(gè)直接后繼，并且在圖形結(jié)構(gòu)中，節(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意兩個(gè)數(shù)據(jù)元素之間都可能相關(guān)。因此，本程序是采用鄰接矩陣、鄰接表、十字鏈表等多種結(jié)構(gòu)存儲(chǔ)來實(shí)現(xiàn)對(duì)圖的存儲(chǔ)。采用鄰接矩陣即為數(shù)組表示法，鄰接表和十字鏈表都是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。對(duì)圖的遍歷分別采用了廣度優(yōu)先遍歷和深度優(yōu)先遍歷。開始開始創(chuàng)建圖G表存儲(chǔ)圖Ify=’y’NY顯示圖的鄰接矩陣KRUSCAL算法顯示圖的鄰接表深度優(yōu)先遍歷廣度優(yōu)先遍歷最小生成樹PRIM輸入字母Ify=’y’結(jié)束NY圖的連通分量輸入一個(gè)數(shù)20134564.3核心代碼#include<iostream>#include<malloc.h>usingnamespacestd;#defineint_max10000#defineinf9999#definemax20//…………鄰接矩陣定義……typedefstructArcCell22{ intadj;char*info;}ArcCell,AdjMatrix[20][20];typedefstruct{charvexs[20];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)建圖用鄰接矩陣表示{charv1,v2;inti,j,w;cout<<"…………創(chuàng)建無向圖…………"<<endl<<"請(qǐng)輸入圖G頂點(diǎn)和弧的個(gè)數(shù):(46)不包括"<<endl;cin>>G.vexnum>>G.arcnum;for(i=0;i!=G.vexnum;++i){cout<<"輸入頂點(diǎn)"<<i<<endl;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):(ab3)不包括"<<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;}cout<<"圖G鄰接矩陣創(chuàng)建成功！"<<endl;returnG.vexnum;}voidljjzprint(MGraph_LG){inti,j;for(i=0;i!=G.vexnum;++i){for(j=0;j!=G.vexnum;++j)cout<<G.arcs[i][j].adj<<"";cout<<endl;}}intvisited[max];//訪問標(biāo)記intwe;typedefstructarcnode//弧結(jié)點(diǎn){intadjvex;//該弧指向的頂點(diǎn)的位置structarcnode*nextarc;//弧尾相同的下一條弧char*info;//該弧信息}arcnode;typedefstructvnode//鄰接鏈表頂點(diǎn)頭接點(diǎn){chardata;//結(jié)點(diǎn)信息arcnode*firstarc;//指向第一條依附該結(jié)點(diǎn)的弧的指針}vnode,adjlist;typedefstruct//圖的定義{adjlistvertices[max];intvexnum,arcnum;intkind;}algraph;//…………隊(duì)列定義……typedefstructqnode{intdata;structqnode*next;}qnode,*queueptr;typedefstruct{queueptrfront;queueptrrear;}linkqueue;//………………………typedefstructacr{intpre;//弧的一結(jié)點(diǎn)intbak;//弧另一結(jié)點(diǎn)intweight;//弧的權(quán)}edg;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(gra.vertices[i].firstarc==NULL){if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum){arc=(arcnode*)malloc(sizeof(arcnode));arc->adjvex=j;gra.vertices[i].firstarc=arc;arc->nextarc=NULL;p=arc;++j;while(G.arcs[i][j].adj!=int_max&&j!=G.vexnum){tem=(arcnode*)malloc(sizeof(arcnode));tem->adjvex=j;gra.vertices[i].firstarc=tem;tem->nextarc=arc;arc=tem;++j;}--j;}}else{if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum){arc=(arcnode*)malloc(sizeof(arcnode));arc->adjvex=j;p->nextarc=arc;arc->nextarc=NULL;p=arc;}}}}gra.vexnum=G.vexnum;gra.arcnum=G.arcnum;/*for(i=0;i!=gra.vexnum;++i){arcnode*p;cout<<i<<"";p=gra.vertices[i].firstarc;while(p!=NULL){cout<<p->adjvex;p=p->nextarc;}cout<<endl;}*/cout<<"圖G鄰接表創(chuàng)建成功！"<<endl;return1;}voidadjprint(algraphgra){inti;for(i=0;i!=gra.vexnum;++i){arcnode*p;cout<<i<<"";p=gra.vertices[i].firstarc;while(p!=NULL){cout<<p->adjvex;p=p->nextarc;}cout<<endl;}}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;}intinitqueue(linkqueue&q)//初始化隊(duì)列{q.rear=(queueptr)malloc(sizeof(qnode));q.front=q.rear;if(!q.front)return0;q.front->next=NULL;return1;}intenqueue(linkqueue&q,inte)//入隊(duì){queueptrp;p=(queueptr)malloc(sizeof(qnode));if(!p)return0;p->data=e;p->next=NULL;q.rear->next=p;q.rear=p;return1;}intdequeue(linkqueue&q,int&e)//出隊(duì){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;}intqueueempty(linkqueueq)//判斷隊(duì)為空{(diào)if(q.front==q.rear)return1;return0;}voidbfstra(algraphgra)//廣度優(yōu)先遍歷{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);//cout<<""<<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);}}}}}intdfs(algraphgra,inti);//聲明DFSintdfstra(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;}intdfs(algraphgra,inti){visited[i]=1;intwe1;//cout<<i<<visited[i]<<endl;cout<<gra.vertices[i].data;//cout<<endl;for(we=firstadjvex(gra,gra.vertices[i]);we>=0;we=nextadjvex(gra,gra.vertices[i],we)){//cout<<we<<visited[we]<<endl;we1=we;//cout<<nextadjvex(gra,gra.vertices[i],we)<<endl;if(visited[we]==0)//cout<<dfs(gra,we);//<<endl;//cout<<i<<we1<<endl;we=we1;//cout<<nextadjvex(gra,gra.vertices[i],we)<<endl;}return12;}intbfstra_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;}}return0;}typedefstruct{intadjvex;intlowcost;}closedge;/*intminimum(closedge*p);intminispantree(MGraph_LG,charu){intk,j,i;closedgeclosedge_a[20];k=localvex(G,u);//cout<<k<<endl;for(j=0;j!=G.vexnum;++j){if(j!=k){closedge_a[j].adjvex=u;closedge_a[j].lowcost=G.arcs[k][j].adj;}for(i=1;i!=G.vexnum;++i){k=minimum(closedge_a);cout<<k;cout<<closedge_a[k].adjvex<<""<<G.vexs[k]<<endl;closedge_a[k].lowcost=0;for(j=0;j!=G.vexnum;++j)if(G.arcs[k][j].adj<closedge_a[j].lowcost){closedge_a[j].adjvex=G.vexs[k];closedge_a[j].lowcost=G.arcs[k][j].adj;}}}return0;}intminimum(closedge*p){ints=10000;for(;p!=NULL;++p){if(s>p->lowcost)s=p->lowcost;}returns;}*/intprim(intg[][max],intn)//最小生成樹PRIM算法{intlowcost[max],prevex[max];//LOWCOST[]存儲(chǔ)當(dāng)前集合U分別到剩余結(jié)點(diǎn)的最短路徑//prevex[]存儲(chǔ)最短路徑在U中的結(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;}printf("(%d,%d)%d\t",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;}printf("\n");}return0;}intacrvisited[100];//kruscal弧標(biāo)記數(shù)組intfind(intacrvisited[],intf){while(acrvisited[f]>0)f=acrvisited[f];returnf;}voidkruscal_arc(MGraph_LG,algraphgra){edgedgs[20];inti,j,k=0;for(i=0;i!=G.vexnum;++i)for(j=i;j!=G.vexnum;++j){if(G.arcs[i][j].adj!=10000){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=10000;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;}}//cout<<x<<y<<m;//cout<<endl;buf=find(acrvisited,x);edf=find(acrvisited,y);//cout<<buf<<""<<edf<<endl;edgs[n].weight=10000;if(buf!=edf){acrvisited[buf]=edf;cout<<"("<<x<<","<<y<<")"<<m;cout<<endl;}}}voidmain(){algraphgra;MGraph_LG;inti,d,g[20][20];chara='a';d=creatMGraph_L(G);creatadj(gra,G);vnodev;cout<<endl<<"……####注意：若該圖為非強(qiáng)連通圖(含有多個(gè)連通分量)時(shí)"<<endl<<"最小生成樹不存在,則顯示為非法值。"<<endl<<endl;cout<<"…菜單……"<<endl<<endl;cout<<"0、顯示該圖的鄰接矩陣……"<<endl;cout<<"1、顯示該圖的鄰接表……"<<endl;cout<<"2、深度優(yōu)先遍歷…………"<<endl;cout<<"3、廣度優(yōu)先遍歷…………"<<endl;cout<<"4、最小生成樹PRIM算法…"<<endl;cout<<"5、最小生成樹KRUSCAL算法………………"<<endl;cout<<"6、該圖的連通分量………"<<endl<<endl;ints;chary='y';while(y='y'){cout<<"請(qǐng)選擇菜單："<<endl;cin>>s;switch(s){case0:cout<<"鄰接矩陣顯示如下："<<endl;ljjzprint(G);break;case1:cout<<"鄰接表顯示如下："<<endl;adjprint(gra);break;case2:cout<<"廣度優(yōu)先遍歷：";bfstra(gra);cout<<endl;break;case3:for(i=0;i!=