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

圖的遍歷和生成樹求解摘要：圖是一種比線形表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在圖形結(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)先遍歷。圖的最小生成樹基于圖的兩種存儲(chǔ)結(jié)構(gòu)，采用Prim算法和Kruskal算法對(duì)圖的最小生成樹進(jìn)行求解。關(guān)鍵詞：圖；存儲(chǔ)結(jié)構(gòu)；遍歷 ；最小生成樹目 錄1.設(shè)計(jì)背景11.1課程設(shè)計(jì)目的11.2題目要求12.設(shè)計(jì)方案12.1設(shè)計(jì)方法12.2方法實(shí)現(xiàn)23. 方案實(shí)施33.1采用的數(shù)據(jù)結(jié)構(gòu)說明及類型的定義33.2函數(shù)功能描述及相關(guān)函數(shù)的實(shí)現(xiàn)53.3程序中需說明的地方，如用到的宏及代表的意義164. 結(jié)果與結(jié)論 174.1測(cè)試數(shù)據(jù)及測(cè)試結(jié)果174.2實(shí)驗(yàn)結(jié)論195.收獲與致謝196.參考文獻(xiàn)20圖的遍歷和生成樹求解1. 設(shè)計(jì)背景1.1課程設(shè)計(jì)目的通過本課程設(shè)計(jì)，加深對(duì)面向?qū)ο蟪绦蛟O(shè)計(jì)C+課程所學(xué)知識(shí)的理解，熟練掌握和鞏固C+語言的基本知識(shí)和語法規(guī)范,掌握使用面向?qū)ο蟪绦蛟O(shè)計(jì)語言C+，或面向?qū)ο箝_發(fā)平臺(tái)Visual C+等,培養(yǎng)調(diào)查研究、查閱技術(shù)文獻(xiàn)、資料、手冊(cè)以及編寫技術(shù)文獻(xiàn)的能力。學(xué)會(huì)編制結(jié)構(gòu)清晰、風(fēng)格良好的C+語言程序，從而具備利用計(jì)算機(jī)編程分析解決綜合性實(shí)際問題的初步能力。1.2題目要求課程設(shè)計(jì)是培養(yǎng)學(xué)生綜合運(yùn)用所學(xué)知識(shí),發(fā)現(xiàn),提出,分析和解決實(shí)際問題,鍛煉實(shí)踐能力的重要環(huán)節(jié),是對(duì)學(xué)生實(shí)際工作能力的具體訓(xùn)練和考察過程. 通過課程設(shè)計(jì)，鞏固和加深對(duì)隊(duì)列以及圖等理論知識(shí)的理解；掌握現(xiàn)實(shí)復(fù)雜問題的分析建模和解決方法，掌握包括問題描述、系統(tǒng)分析、設(shè)計(jì)建模、代碼實(shí)現(xiàn)、結(jié)果分析等的方法；提高利用計(jì)算機(jī)分析解決綜合性實(shí)際問題的基本能力；鍛煉個(gè)人動(dòng)手能力，歷練自身素質(zhì)。2.設(shè)計(jì)方案2.1設(shè)計(jì)方法2.1.1問題的分析和結(jié)構(gòu)的設(shè)計(jì)思路1） 圖的遍歷和生成樹求解所有功能：圖的生成、圖的遍歷、最小生成樹求解。2） 需要?jiǎng)?chuàng)建所有圖的存儲(chǔ)結(jié)構(gòu)(鄰接矩陣存儲(chǔ)結(jié)構(gòu)和鄰接表存儲(chǔ)結(jié)構(gòu))。3）程序設(shè)計(jì)的目的是通過屏幕上輸出的提示語句，進(jìn)行相應(yīng)的操作。4）選擇適當(dāng)?shù)乃惴?，?shí)現(xiàn)圖的遍歷和最小生成樹的求解等功能。5）選擇適當(dāng)?shù)淖兞?，來表示圖相應(yīng)的頂點(diǎn)、邊、邊的權(quán)值等信息。6）當(dāng)輸入的信息出錯(cuò)時(shí)，程序應(yīng)給錯(cuò)誤信息提示，使程序設(shè)計(jì)得全面周密。2.1.2圖的遍歷和生成樹求解的算法思想及設(shè)計(jì)1） 由于圖的存儲(chǔ)結(jié)構(gòu)不同，故采用鄰接矩陣和鄰接表兩種存儲(chǔ)結(jié)構(gòu)建立圖。 2）對(duì)圖的深度遍歷基于鄰接矩陣，廣度遍歷基于鄰接表。3）基于鄰接矩陣存儲(chǔ)結(jié)構(gòu)，用prim算法求圖的最小生成樹。 4）基于鄰接表存儲(chǔ)結(jié)構(gòu)，用Kruskal算法求圖的最小生成樹。5）綜合1、2、3三點(diǎn)因素，可以采用隊(duì)列來實(shí)現(xiàn)對(duì)圖的廣度優(yōu)先遍歷的算法，其示意圖如下：Q.frontnext其中：1. Q.front為隊(duì)頭指針,Q.rear為隊(duì)尾指針2. data域存圖的邊權(quán)值和頂點(diǎn)位序等相關(guān)信息。3. next域指向與改結(jié)點(diǎn)同類型的下一個(gè)結(jié)點(diǎn)nextdatadatanextQ.rear 6）圖遍歷和生成樹求解的總體結(jié)構(gòu)框圖如下：圖的遍歷和生成樹的求解建立鄰接矩陣輸出鄰接矩陣BFS遍歷建立鄰接表輸出鄰接表DFS遍歷Prim求最小生成樹Kruskal求最小生成樹2.2方法實(shí)現(xiàn)2.2.1創(chuàng)建結(jié)點(diǎn)1）建立隊(duì)列LinkQueue，以及隊(duì)頭指針front、隊(duì)尾指針rear。2)建立圖的存儲(chǔ)類型MGraph,以及頂點(diǎn)向量vexs。3)建立圖的鄰接矩陣AdjMatrix，以及邊的權(quán)值。4)建立圖的鄰接表ALGraph,以及鄰接表頭結(jié)點(diǎn)的類型AdjList，弧的結(jié)點(diǎn)結(jié)構(gòu)類型ArcNode。2.2.2編寫函數(shù)建立具體的功能實(shí)現(xiàn)函數(shù)，如初始化、錄入、輸出等。1.基于鄰接矩陣創(chuàng)建圖CreateUDN(MGraph &G,AdjMatrix &GA)2.基于鄰接表建立圖CreateALGraph(ALGraph &G) 3.鄰接矩陣的輸出Display(MGraph G,AdjMatrix GA)4.鄰接表的輸出DisplayG(ALGraph G) 5.基于鄰接矩陣圖進(jìn)行深度優(yōu)先遍歷DFS1(MGraph G,int n,int v)6.對(duì)結(jié)點(diǎn)隊(duì)列初始化InitQueue (LinkQueue &Q) 7.判斷隊(duì)列是否為空 QueueEmpty (LinkQueue Q)8.頂點(diǎn)信息入隊(duì)EnQueue (LinkQueue &Q,int e)9.頂點(diǎn)信息出隊(duì)DeQueue (LinkQueue &Q,int &e)10.基于鄰接表對(duì)圖進(jìn)行廣度優(yōu)先遍歷BFS(ALGraph G,int v)11.Prim求生成樹MiniSpanTree_PRIM(MGraph G,AdjMatrix GA,VertexType u) 12.Kruskal求生成樹Kruskal(ALGraph G)13. 求頂點(diǎn)在圖中位置LocateVex(MGraph G,VertexType u)，LocateVexG(ALGraph G,vertexType e)14.主函數(shù)main()3.方案實(shí)施3.1 采用的數(shù)據(jù)結(jié)構(gòu)說明及類型的定義1鄰接矩陣的存儲(chǔ)表示如下typedef struct ArcCellVRType adj; /VRType是頂點(diǎn)關(guān)系類型，對(duì)無權(quán)圖，用0和1；對(duì)有權(quán)圖，則為權(quán)值類型 InfoType *info; /該弧相關(guān)信息的指針(可無)ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM;/頂點(diǎn)向量AdjMatrix arcs;/鄰接矩陣int vexnum,arcnum;/圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)GraphKind kind;/圖的種類標(biāo)志MGraph;2鄰接表的存儲(chǔ)表示如下typedef struct ArcNode /弧的結(jié)點(diǎn)結(jié)構(gòu)類型int adjvex;/該弧所指向的頂點(diǎn)的位置 int weight;/*該弧的權(quán)重*/struct ArcNode *nextarc;/指向下一條弧的指針I(yè)nfoType *info;/該弧相關(guān)信息的指針(可無)ArcNode;typedef struct VNode/鄰接表頭結(jié)點(diǎn)的類型vertexType data;/頂點(diǎn)信息ArcNode *firstarc;/指向第一條依附該頂點(diǎn)的弧的指針VNode,AdjListMAX_VERTEX_NUM;typedef struct/鄰接表AdjList vertices;int vexnum,arcnum;/圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)ALGraph3隊(duì)列的存儲(chǔ)結(jié)構(gòu)typedef struct QNode TElemType data; QNode *next;QNode,*QueuePtr;typedef struct QueuePtr front;/隊(duì)頭指針 QueuePtr rear;/隊(duì)尾指針LinkQueue;4Prim算法輔助數(shù)組存儲(chǔ)結(jié)構(gòu)typedef struct /輔助數(shù)組存儲(chǔ)結(jié)構(gòu) VertexType adjvex;VRType lowcost;Closedge MAX_VERTEX_NUM;3.2函數(shù)功能描述及相關(guān)函數(shù)的實(shí)現(xiàn)1.基于鄰接矩陣創(chuàng)建圖CreateUDN(MGraph &G,AdjMatrix &GA)Status CreateUDN(MGraph &G,AdjMatrix &GA)/用鄰接矩陣表示法，構(gòu)造無向網(wǎng)G，以及表示出其鄰接矩陣GAint i,j,k,w;VertexType v1,v2;printf(請(qǐng)輸入無向網(wǎng)G的頂點(diǎn)數(shù),邊數(shù):n);scanf(%d,%d,&G.vexnum,&G.arcnum,);printf(請(qǐng)輸入%d個(gè)頂點(diǎn)的值:n,G.vexnum); for(i=1;i=G.vexnum;+i) scanf(%s,&G.vexsi); /構(gòu)造頂點(diǎn)向量getchar();for(i=1;i=G.vexnum;i+)for(j=1;j=G.vexnum;j+) /初始化鄰接矩陣GAij.adj=INFINITY;GA=NULL;printf(請(qǐng)輸入%d條邊的頂點(diǎn)1頂點(diǎn)2和權(quán)值(以空格作為間隔):n,G.arcnum);for(k=1;k=G.arcnum;k+)scanf(%s%s%d,&v1,&v2,&w); /輸入一條邊依附的頂點(diǎn)和權(quán)值i=LocateVex(G,v1);j=LocateVex(G,v2); /確定v1和v2在G中的位置GAij.adj=GAji.adj=w; /弧的權(quán)值 和的對(duì)稱弧return OK;2.基于鄰接表建立圖CreateALGraph(ALGraph &G) Status CreateALGraph(ALGraph &G) /用鄰接表表示法，構(gòu)建無向網(wǎng)Gint i,j,k,w; ArcNode *s,*p; printf(請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)(輸入格式為:頂點(diǎn)數(shù),邊數(shù))：n); scanf(%d,%d,&(G.vexnum),&(G.arcnum); vertexType v1,v2; printf(請(qǐng)輸入頂點(diǎn)信息：n); for ( i=1;i=G.vexnum;i+) scanf(n%c,&(G.verticesi.data); /初始化鄰接表的頭結(jié)點(diǎn) G.verticesi.firstarc=NULL; printf(請(qǐng)輸入邊的信息(輸入格式為:v1,v2,w)：n); for (k=1;kadjvex=j; s-weight=w; s-nextarc=G.verticesi.firstarc; G.verticesi.firstarc=s;/將下標(biāo)為j的結(jié)點(diǎn)連接在下標(biāo)為i的結(jié)點(diǎn)后面 p=(ArcNode*)malloc(sizeof(ArcNode); p-adjvex=i; p-weight=w; p-nextarc=G.verticesj.firstarc; G.verticesj.firstarc=p; /將下標(biāo)為i的結(jié)點(diǎn)連接在下標(biāo)為j的結(jié)點(diǎn)后面 return OK; 3.鄰接矩陣的輸出Display(MGraph G,AdjMatrix GA)void Display(MGraph G,AdjMatrix GA) /鄰接矩陣的輸出int i,j;for(i=1;i=G.vexnum;i+) printf(G.vexs%d=%cn,i,G.vexsi); /輸出頂點(diǎn)向量printf(鄰接矩陣GA.adj:n); for(i=1;i=G.vexnum;i+)for(j=1;j=G.vexnum;j+)printf(%5d,GAij.adj);printf(n); 4.鄰接表的輸出DisplayG(ALGraph G) void DisplayG(ALGraph G) /鄰接表的輸出int i;ArcNode *p;for(i=1; i ,i,G.verticesi.data); while(p) if(p-nextarc) printf(%d,%c,%d-,p-adjvex,G.verticesp-adjvex.data,p-weight); else printf(%d,%c,%d-/,p-adjvex,G.verticesp-adjvex.data,p-weight); p=p-nextarc; printf(n);5.基于鄰接矩陣圖進(jìn)行深度優(yōu)先遍歷DFS1(MGraph G,int n,int v)int visitedMAX_VERTEX_NUM; /初始化標(biāo)志數(shù)組Status DFS1(MGraph G,int n,int v)/基于鄰接矩陣，對(duì)圖G進(jìn)行深度優(yōu)先搜索int j;AdjMatrix A;printf(%3d,v);printf(%c,G.vexsv);visitedv=1;for(j=1;jnext=NULL;return OK;7.判斷隊(duì)列是否為空 QueueEmpty (LinkQueue Q)int QueueEmpty (LinkQueue Q)/判斷隊(duì)列是否為空 if(Q.front=Q.rear) return 1; return 0;8.頂點(diǎn)信息入隊(duì)EnQueue (LinkQueue &Q,int e)Status EnQueue (LinkQueue &Q,int e)/結(jié)點(diǎn)進(jìn)隊(duì) QNode *p; p=(QNode*)malloc(sizeof(QNode); if(!p) return ERROR; p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; return OK;9.頂點(diǎn)信息出隊(duì)DeQueue (LinkQueue &Q,int &e)int DeQueue (LinkQueue &Q,int &e)/結(jié)點(diǎn)出隊(duì) if(Q.front=Q.rear) printf(隊(duì)列為空！n); QNode *p; p=(QNode*)malloc(sizeof(QNode); if(!p) return ERROR; p=Q.front-next; e=p-data; Q.front-next=p-next; if(Q.rear=p) Q.rear=Q.front; free(p); return OK;10.基于鄰接表對(duì)圖進(jìn)行廣度優(yōu)先遍歷BFS(ALGraph G,int v)int visited1MAX_VERTEX_NUM;/初始化標(biāo)志數(shù)組Status BFS(ALGraph G,int v)/基于鄰接表，對(duì)無向圖G進(jìn)行廣度優(yōu)先搜索 int u, w; LinkQueue Q; InitQueue(Q); if(!visited1v) visited1v=1; printf(%ct,G.verticesv.data); EnQueue(Q,v); while(!QueueEmpty(Q) DeQueue(Q,u); for(w=FirstAdjVex(G,u);w=0;w=NextAdjVex(G,u,w) if(!visited1w) visited1w=1; printf(%ct,G.verticesw.data); EnQueue(Q,w); return OK;11.Prim求生成樹MiniSpanTree_PRIM(MGraph G,AdjMatrix GA,VertexType u) Status MiniSpanTree_PRIM(MGraph G,AdjMatrix GA,VertexType u)/用Prim算法從第u個(gè)頂點(diǎn)出發(fā)構(gòu)造網(wǎng)G的最小生成樹T，輸出T的各邊 int k,j,i; Closedge closedge; k=LocateVex(G,u);for(j=1;j=G.vexnum;j+)if(j!=k) closedgej.adjvex=u; closedgej.lowcost=GAkj.adj;/ 輔助數(shù)組初始化closedgej.adjvex = 0;closedgej.lowcost = 88;closedgek.adjvex = u;closedgek.lowcost=0;/初始U=uprintf(最小生成樹的各條邊為:n);for(i=2;i=G.vexnum;+i)/選擇其余的G.vexnum-1個(gè)頂點(diǎn)k=minimum(closedge); /求出T的下一個(gè)結(jié)點(diǎn)；第k個(gè)頂點(diǎn)printf(%c-%cn,closedgek.adjvex,G.vexsk);/輸出生成樹的邊closedgek.lowcost=0;/第k頂點(diǎn)并入U(xiǎn)集for(j=1;j=G.vexnum;+j)if(GAkj.adjclosedgej.lowcost)/新頂點(diǎn)并入U(xiǎn)集后，重新選擇最小邊closedgej.adjvex=G.vexsk; closedgej.lowcost=GAkj.adj;return OK;12.Kruskal求生成樹Kruskal(ALGraph G)Status Kruskal(ALGraph G)int i,j,min = INFINITY,k = 1;/min用于記錄最小權(quán)值，k表示當(dāng)前構(gòu)造的第幾條邊int setMAX_VERTEX_NUM;/用于判斷兩個(gè)點(diǎn)是否在同一集合里ArcNode *p,*q,*s;for(i = 1; i = G.vexnum; +i) seti = i;/初始化，將每個(gè)點(diǎn)自身作為一個(gè)集合 while(kG.vexnum&k=G.arcnum )for(i = 1; i nextarc)/查找最小權(quán)值的邊if(p-weight weight;q = p;j = i;if(G.verticesj.firstarc = q) G.verticesj.firstarc = q-nextarc; /if-else用于刪除最小權(quán)值的邊elsefor(p = G.verticesj.firstarc; p != q; p = p-nextarc) s = p;s-nextarc = q-nextarc;if(setj!=setq-adjvex)/判斷兩點(diǎn)是否在同一集合,若不在，則輸出這條邊printf(%c,%c) %dn,G.verticesj.data,G.verticesq-adjvex.data,q-weight);k+;/*int s2=setj;*/for(i=1;iadjvex;min = INFINITY; /將min置為最大值return OK;13.求頂點(diǎn)在圖中位置LocateVex(MGraph G,VertexType u)，LocateVexG(ALGraph G,vertexType e)Status LocateVex(MGraph G,VertexType u) int i;for(i=1;i=G.vexnum;+i)if(G.vexsi=u)return i;return -1;Status LocateVexG(ALGraph G,vertexType e) for(int i=1;i=G.vexnum;i+) if(G.verticesi.data=e) return i; return -1;14.主函數(shù)main()int main() ALGraph A;MGraph G;AdjMatrix S;int n,v; VertexType u;printf(用圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)建無向網(wǎng):n); CreateUDN(G,S);printf(輸出鄰接矩陣：n);Display(G,S);printf(用圖的鄰接表存儲(chǔ)結(jié)構(gòu)建無向網(wǎng)：n); CreateALGraph(A); printf(輸出鄰接表：n); DisplayG(A);printf(n); printf(輸入圖的結(jié)點(diǎn)個(gè)數(shù)以及訪問的起始結(jié)點(diǎn)的位序(格式如：2,1)：n); scanf(%d,%d,&n,&v); printf(對(duì)圖進(jìn)行深度優(yōu)先遍歷（鄰接矩陣）：n); DFS1(G,n,v);printf(n); printf(對(duì)圖進(jìn)行深度優(yōu)先遍歷（鄰接表）：n);DFS2(A,v); printf(n); printf(對(duì)圖進(jìn)行廣度優(yōu)先遍歷（鄰接表）：n); BFS(A,v);printf(n);printf(利用PRIM算法求最小生成樹n);u=G.vexs1; MiniSpanTree_PRIM(G,S,u);printf(利用Kruskal算法求最小生成樹n); Kruskal(A);printf(n); return OK;3.3 程序中需說明的地方，如用到的宏及代表的意義#define OK 1#define ERROR 0#define INFINITY 88 /最大值（表示無窮大）#define MAX_VERTEX_NUM 20 /最大頂點(diǎn)個(gè)數(shù)#define MAX_INFO 20#define MAX_NAME 5typedef int Status; typedef char VertexType;typedef int VRType;typedef char vertexType;typedef char InfoType;typedef enumDG,DN,UDG,UDNGraphKind; /有向圖,有向網(wǎng),無向圖,無向網(wǎng)typedef int TElemType;4. 結(jié)果與結(jié)論4.1測(cè)試數(shù)據(jù)及測(cè)試結(jié)果1.程序運(yùn)行開始界面：2.測(cè)試錄入頂點(diǎn)信息以及邊的信息，錄入數(shù)據(jù)及錄入結(jié)果如下：3.測(cè)試輸出鄰接矩陣的函數(shù)4測(cè)試基于鄰接表構(gòu)造圖函數(shù)5. 測(cè)試輸出鄰接表的函數(shù)6. 測(cè)試基于鄰接矩陣對(duì)圖進(jìn)行深度優(yōu)先遍歷的函數(shù)7.測(cè)試基于鄰接表對(duì)圖進(jìn)行廣度優(yōu)先遍歷的函數(shù)8.測(cè)試Prim算法求最小生成樹的函數(shù)9