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

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