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

1、精品文檔 圖的遍歷和生成樹求解摘要：圖是一種比線形表和樹更為復(fù)雜的數(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)說明及類型

2、的定義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+?課程所學(xué)知識的理解，熟練掌握和穩(wěn)固C+語言的根本知識和語法標準,掌握使用面向?qū)ο蟪绦蛟O(shè)計語言C+，或面向?qū)ο箝_發(fā)平臺Visual C+等,培養(yǎng)調(diào)查研究、查閱技術(shù)文獻、資料、手冊以及編寫技術(shù)文獻的能力。學(xué)會編制結(jié)構(gòu)清晰、風格良好的C+語言程序，從而具備利用計算機編程分析解決綜合性實際問題的初步能力。1.2題目

3、要求課程設(shè)計是培養(yǎng)學(xué)生綜合運用所學(xué)知識,發(fā)現(xiàn),提出,分析和解決實際問題,鍛煉實踐能力的重要環(huán)節(jié),是對學(xué)生實際工作能力的具體訓(xùn)練和考察過程. 通過課程設(shè)計，穩(wěn)固和加深對隊列以及圖等理論知識的理解；掌握現(xiàn)實復(fù)雜問題的分析建模和解決方法，掌握包括問題描述、系統(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、幕上輸出的提示語句，進行相應(yīng)的操作。4選擇適當?shù)乃惴ǎ瑢崿F(xiàn)圖的遍歷和最小生成樹的求解等功能。5選擇適當?shù)淖兞浚瑏肀硎緢D相應(yīng)的頂點、邊、邊的權(quán)值等信息。6當輸入的信息出錯時，程序應(yīng)給錯誤信息提示，使程序設(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.frontn

5、ext其中：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)建

6、立圖的鄰接表ALGraph,以及鄰接表頭結(jié)點的類型AdjList，弧的結(jié)點結(jié)構(gòu)類型ArcNode。編寫函數(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

7、(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(MGra

8、ph 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;/頂點向量

9、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 *firs

10、tarc;/指向第一條依附該頂點的弧的指針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) Ve

11、rtexType 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.

12、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);fo

13、r(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; /弧<v1,v2>的權(quán)值 和<v2,v1>的對稱弧return OK;2.基于鄰接表建立圖CreateALGraph(ALGraph &G) Status CreateALGraph(ALGraph &G) /用鄰接表表示法，構(gòu)建無向網(wǎng)Gi

14、nt 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; print

15、f("請輸入邊的信息(輸入格式為:v1,v2,w)：n"); for (k=1;k<=G.arcnum;k+) scanf("n%c,%c,%d",&v1,&v2,&w); /輸入一條邊依附的頂點和權(quán)值 j= LocateVexG(G,v2); i= LocateVexG(G,v1); /確定v1和v2在G中的位置s=(ArcNode*)malloc(sizeof(ArcNode); s->adjvex=j; s->weight=w; s->nextarc=G.verticesi.firstarc; G.v

16、erticesi.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=

17、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;

18、i<=G.vexnum; i+) p=G.verticesi.firstarc; printf("(%d | %c)-> ",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-&g

19、t;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;j<=n;j+)if(Avj.adj!=0&a

20、mp;&!visitedj)DFS1(G,n,j); return OK;6.對結(jié)點隊列初始化InitQueue (LinkQueue &Q) Status InitQueue (LinkQueue &Q)/建立一個空隊列 Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode); if(!Q.front) return ERROR; Q.front->next=NULL;return OK;7.判斷隊列是否為空 QueueEmpty (LinkQueue Q)int QueueEmpty (LinkQueue Q)/判斷隊列是否

21、為空 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 &am

22、p;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(ALGrap

23、h 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)

24、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)

25、;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é)

26、點；第k個頂點printf("%c-%cn",closedgek.adjvex,G.vexsk);/輸出生成樹的邊closedgek.lowcost=0;/第k頂點并入U集for(j=1;j<=G.vexnum;+j)if(GAkj.adj<closedgej.lowcost)/新頂點并入U集后，重新選擇最小邊closedgej.adjvex=G.vexsk; closedgej.lowcost=GAkj.adj;return OK;12.Kruskal求生成樹Kruskal(ALGraph G)Status Kruskal(ALGraph G)int i,j,

27、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(k<G.vexnum&&k<=G.arcnum )for(i = 1; i <= G.vexnum; +i)if(G.verticesi.firstarc!=NULL)/假設(shè)第i+1個點沒有鄰邊，那么下一循環(huán) for(p=G.ver

28、ticesi.firstarc;p!=NULL;p=p->nextarc)/查找最小權(quán)值的邊if(p->weight < min)min = p->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

29、->adjvex)/判斷兩點是否在同一集合,假設(shè)不在，那么輸出這條邊printf("(%c,%c) %dn",G.verticesj.data,G.verticesq->adjvex.data,q->weight);k+;/*int s2=setj;*/for(i=1;i<=G.vexnum;i+)if(seti=setj/*s2*/)seti=setq->adjvex;min = INFINITY; /將min置為最大值return OK;13.求頂點在圖中位置LocateVex(MGraph G,VertexType u)，LocateVe

30、xG(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;

31、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(&qu

32、ot;%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; MiniSpanTre

33、e_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