圖的深廣遍歷算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

1、圖的操作一、問題描述 圖是一種較線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在圖形結(jié)構(gòu)中，節(jié)點間的關(guān)系可以是任意的，圖中任意兩個數(shù)據(jù)元素之間都可以相關(guān)。由此，圖的應(yīng)用極為廣泛?，F(xiàn)在鄰接矩陣和鄰接表的存儲結(jié)構(gòu)下，完成圖的深度、廣度遍歷。二、基本要求 1、選擇合適的存儲結(jié)構(gòu)完成圖的建立； 2、建立圖的鄰接矩陣，能按矩陣方式輸出圖，并在此基礎(chǔ)上，完成圖的深度和廣度遍歷，輸出遍歷序列； 3、建立圖的鄰接表，并在此基礎(chǔ)上，完成圖的深度和廣度遍歷，輸出遍歷序列；三、測試數(shù)據(jù)四、算法思想1、鄰接矩陣 頂點向量的存儲。用兩個數(shù)組分別存儲數(shù)據(jù)（定點）的信息和數(shù)據(jù)元素之間的關(guān)系（邊或?。┑男畔?。2、鄰接表 鄰接表是圖的一種鏈?zhǔn)?/p>

2、存儲結(jié)構(gòu)。在鄰接表中，對圖中每個定點建立一個單鏈表，第i個單鏈表中的節(jié)點表示依附于定點vi的邊。每個節(jié)點由3個域組成，其中鄰接點域（adjvex）指示與定點vi鄰接的點在圖中的位置，鏈域（nextarc）指示下一條邊或弧的節(jié)點；數(shù)據(jù)域（info）存儲和邊或弧相關(guān)的信息，如權(quán)值等。每個鏈表上附設(shè)一個頭節(jié)點。在表頭節(jié)點中，除了設(shè)有鏈域（firstarc）指向鏈表中第一個節(jié)點之外，還設(shè)有存儲定點vi的名或其他有關(guān)信息的數(shù)據(jù)域（data）。3、圖的深度遍歷 深度優(yōu)先搜索遍歷類似于樹的先根遍歷，是樹的先跟遍歷的推廣。假設(shè)初始狀態(tài)是圖中所有頂點未曾被訪問，則深度優(yōu)先搜索可從圖中某個頂點v出發(fā)， 訪問此頂點

3、，然后依次從v的未被訪問的鄰接點出發(fā)深度優(yōu)先遍歷圖，甚至圖中所有和v相通的頂點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復(fù)上述過程，直至圖中所有頂點都被訪問到為止。4、圖的廣度遍歷 廣度優(yōu)先遍歷類似于樹的按層次遍歷過程。假設(shè)從圖中某頂點v出發(fā)，在訪問了v之后依次訪問v的各個未曾訪問過的鄰接點，然后分別從這些鄰接點出發(fā)依次訪問它們的鄰接點，并使“先被訪問的頂點的鄰接點”先與“后被訪問的頂點的鄰接點”被訪問，直至圖中所有已被訪問的頂點的鄰接點都被訪問到。若此時圖中尚有頂點未被訪問，則另選圖中一個曾被訪問的頂點作起始點，重復(fù)上述過程，直至圖中所有頂點都被訪問到

4、為止。五、模塊劃分一、基于鄰接矩陣的深廣度遍歷 1Status InitQueue(LinkQueue *Q)根據(jù)已知Q初始化隊列2Status QueueEmpty (LinkQueue Q)判斷隊列是否為空3Status EnQueue(LinkQueue *Q, QElemType e)將e壓入隊尾4Status DeQueue(LinkQueue *Q, QElemType *e)取隊頭元素e5int LocateVex(MGraph G,VertexType v)定位定點v6void CreateGraph(MGraph *G)建立無向圖的鄰接矩陣7void PrintGraph(M

5、Graph G)輸出鄰接矩陣的無向圖8int FirstAdjVex(MGraph G,int v)第一個鄰接點的定位9int NextAdjVex(MGraph G,int v,int w)查找下一個鄰接點10void Dfs(MGraph G, int v)實現(xiàn)圖的一次遍歷11void DfsTraverse(MGraph G)實現(xiàn)圖的深度遍歷12void BfsTraverse(MGraph G)實現(xiàn)圖的廣度遍歷13Main主函數(shù) 二、基于鄰接表實現(xiàn)圖的深廣度遍歷1Status InitQueue(LinkQueue *Q)根據(jù)已知Q初始化隊列2Status QueueEmpty (Li

6、nkQueue Q)判斷隊列是否為空3Status EnQueue(LinkQueue *Q, QElemType e)將e壓入隊尾4Status DeQueue(LinkQueue *Q, QElemType *e)取隊頭元素e5void createALGraph(ALGraph *G)建立無向圖的鄰接矩陣6void PrintGraph(MGraph G)輸出鄰接矩陣的無向圖7int FirstAdjVex(MGraph G,int v)第一個鄰接點的定位8int NextAdjVex(MGraph G,int v,int w)查找下一個鄰接點9void Dfs(MGraph G, in

7、t v)實現(xiàn)圖的一次深度遍歷10void DfsTraverse(MGraph G)實現(xiàn)圖的深度遍歷11void BFS(ALGraph G, int v)實現(xiàn)圖的一次廣度遍歷12void BfsTraverse(MGraph G)實現(xiàn)圖的廣度遍歷13Void Main主函數(shù) 六、數(shù)據(jù)結(jié)構(gòu)/(ADT)1、基于鄰接矩陣的圖的類型定義typedef struct ArcCell VRType adj; /*圖中有1/0表示是否有邊，網(wǎng)中表示邊上的權(quán)值*/ /* InfoType *info; 與邊相關(guān)的信息*/ ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_

8、NUM;typedef struct VertexType vexsMAX_VERTEX_NUM; /*頂點向量*/ AdjMatrix arcs; /*鄰接矩陣*/ int vexnum,arcnum; /*圖中當(dāng)前頂點數(shù)和邊數(shù)*/ MGraph;2、基于鄰接表的圖的類型定義typedef struct ArcNode int adjvex; struct ArcNode *nextarc; ArcNode; /*表節(jié)點*/ typedef struct TElemType data; ArcNode *firstarc;VNode,AdjListMAXVER; /*表節(jié)點*/typedef

9、 struct AdjList vertices; int vexnum,arcnum; /*圖中當(dāng)前頂點數(shù)和邊數(shù)*/ ALGraph;七、源程序一、基于鄰接矩陣的圖的深度、廣度遍歷#include "stdlib.h"#include "stdio.h"#include "string.h"#define TRUE 1#define FALSE 0#define OVERFLOW -2#define OK 1#define ERROR 0typedef int Status;#define INFINITY INT_MAX /*最大

10、值“無窮”*/#define MAX_VERTEX_NUM 20 /*最大頂點個數(shù)*/typedef int Boolean;typedef char VertexType20;typedef int VRType;/*以下為隊列的操作*/*隊列的類型定義*/typedef int QElemType;typedef struct QNode QElemType data; struct QNode *next; QNode, *QueuePtr;typedef struct QueuePtr front; QueuePtr rear; LinkQueue;/*初始化隊列*/Status In

11、itQueue(LinkQueue *Q) (*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode);if(!(*Q).front) exit(OVERFLOW); (*Q).front->next=NULL; return OK; /*判斷隊列是否為空*/Status QueueEmpty (LinkQueue Q) if (Q.front=Q.rear) return TRUE; else return FALSE; /*入隊列*/Status EnQueue(LinkQueue *Q, QElemType e) QueuePtr p;

12、p=(QueuePtr)malloc(sizeof(QNode); if (!p) exit(OVERFLOW); p->data=e; p->next=NULL; (*Q).rear->next=p; (*Q).rear=p; return OK; /*出隊列*/Status DeQueue(LinkQueue *Q, QElemType *e) QueuePtr p; if (*Q).front=(*Q).rear) return ERROR; p=(*Q).front->next; *e=p->data; (*Q).front->next=p->

13、next; if (*Q).rear=p) (*Q).rear=(*Q).front; free(p); return OK; /*以下為圖的操作*/*圖的類型定義*/typedef struct ArcCell VRType adj; /*圖中有1/0表示是否有邊，網(wǎng)中表示邊上的權(quán)值*/ /* InfoType *info; 與邊相關(guān)的信息*/ ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM; /*頂點向量*/ AdjMatrix arcs; /*鄰接矩陣*

14、/ int vexnum,arcnum; /*圖中當(dāng)前頂點數(shù)和邊數(shù)*/ MGraph;/* 頂點在頂點向量中的定位*/int LocateVex(MGraph G,VertexType v) int i; for(i=0;i<G.vexnum;i+) if (strcmp(v,G.vexsi)=0) break; return i;/*建立無向圖的鄰接矩陣*/void CreateGraph(MGraph *G) int i,j,k; VertexType v1,v2; printf("nInput MG vexnum,arcnum:"); scanf("%

15、d,%d",&(*G).vexnum,&(*G).arcnum); printf("Input %d vexs:",(*G).vexnum); for(i=0;i<(*G).vexnum;i+) /*輸入頂點向量*/ scanf("%s",(*G).vexsi); printf("vexs listn"); for(i=0;i<G->vexnum;i+) /*輸出頂點向量*/ puts(G->vexsi); for(i=0;i<(*G).vexnum;i+) /*鄰接矩陣初始化*

16、/ for(j=0;j<(*G).vexnum;j+)(*G).arcsij.adj=0; printf("nInput %d arcs(vi vj):n",(*G).arcnum); for(k=0;k<(*G).arcnum;k+) /*輸入無權(quán)圖的邊*/ scanf("%s%s",v1,v2); i=LocateVex(*G,v1); j=LocateVex(*G,v2); (*G).arcsij.adj=1; (*G).arcsji=(*G).arcsij; /*按鄰接矩陣方式輸出無向圖*/void PrintGraph(MGraph

17、 G) int i,j; printf("nMGraph:n"); for(i=0; i<G.vexnum; i+) printf("%10s",G.vexsi); for(j=0; j<G.vexnum; j+) printf("%4d",G.arcsij.adj); printf("n"); /* 查找第1個鄰接點 */int FirstAdjVex(MGraph G,int v) int j,p=-1; for(j=0;j<G.vexnum;j+) if (G.arcsvj.adj=1) p

18、=j; break; return p;/* 查找下一個鄰接點 */int NextAdjVex(MGraph G,int v,int w) int j,p=-1; for(j=w+1;j<G.vexnum;j+) if (G.arcsvj.adj=1) p=j; break; return p;/*深度遍歷*/Boolean visitedMAX_VERTEX_NUM; /* 設(shè)置全局的訪問標(biāo)志數(shù)組 */void Dfs(MGraph G, int v) int w; visitedv=TRUE; printf("%s",G.vexsv); for(w=FirstA

19、djVex(G,v); w>=0; w=NextAdjVex(G,v,w) if(!visitedw) Dfs(G,w);void DfsTraverse(MGraph G) int v; for (v=0; v<G.vexnum; v+) visitedv=FALSE; for(v=0; v<G.vexnum; v+) if (!visitedv) Dfs(G,v);/* 廣度遍歷 */void BfsTraverse(MGraph G) int v,u,w; LinkQueue Q; for(v=0; v<G.vexnum; v+) visitedv=FALSE;

20、InitQueue(&Q); for(v=0; v<G.vexnum; v+) if (!visitedv) visitedv=TRUE; printf("%s",G.vexsv); EnQueue(&Q,v); while(!QueueEmpty(Q) DeQueue(&Q,&u); for(w=FirstAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w) if (!visitedw) visitedw=TRUE; printf("%s",G.vexsw); EnQueue(&

21、;Q,w); /*主函數(shù)*/main() int w; MGraph G; CreateGraph(&G); PrintGraph(G); printf("nDfs:"); DfsTraverse(G); /* 深度遍歷 */ printf("nBfs:"); BfsTraverse(G); /* 廣度遍歷 */二：基于鄰接表的圖的深度、廣度遍歷#include "stdlib.h"#include "stdio.h"#include "string.h"#define MAXVER 2

22、1#define N 100typedef char TElemType10;/*循環(huán)隊列的操作*/*隊列的類型定義*/typedef int ElemType;typedef struct ElemType *base;int front,rear;SqQueue;/*初始化隊列*/void InitQueue(SqQueue *Q) Q->base=(ElemType *)malloc(N*sizeof(ElemType); Q->front=Q->rear=0; /*判斷隊列是否為空*/int QueueEmpty(SqQueue Q)if(Q.front=Q.rear

23、) return 1; else return 0;/*入隊列*/int EnQueue(SqQueue *Q,ElemType e)if(Q->rear+1)%N=Q->front) return 0;Q->baseQ->rear=e;Q->rear=(Q->rear+1)%N;return 1;/*出隊列*/int DeQueue(SqQueue *Q,ElemType *e)if(Q->rear=Q->front) return 0;*e=Q->baseQ->front;Q->front=(Q->front+1)%N

24、;return 1;/*圖的操作*/*圖的類型定義*/typedef struct ArcNode int adjvex; struct ArcNode *nextarc; ArcNode; typedef struct TElemType data; ArcNode *firstarc;VNode,AdjListMAXVER;typedef struct AdjList vertices; int vexnum,arcnum; ALGraph;/*建立無向圖的鄰接矩陣*/void createALGraph(ALGraph *G) int i, s, d; ArcNode *p,*q; pr

25、intf("nInput MG vexnum,arcnum:"); scanf("%d,%d",&(*G).vexnum,&(*G).arcnum); for(i=1;i<=G->vexnum;i+) printf("n輸入第%d個頂點信息：",i); scanf("%s",G->verticesi.data); G->verticesi.firstarc=NULL; /輸入第i個結(jié)點值并初始化第i個單鏈表為空 for(i=1; i<=G->arcnum; i+)

26、 printf("n輸入第%d條邊的始點和終點：",i); scanf("%d,%d",&s,&d); p=(ArcNode*)malloc(sizeof(ArcNode); p->adjvex=d; p->nextarc=G->verticess.firstarc; G->verticess.firstarc=p; /將新建的以d為信息的表結(jié)點p插入s單鏈表的頭結(jié)點后 q=(ArcNode*)malloc(sizeof(ArcNode); q->adjvex=s; q->nextarc=G->v

27、erticesd.firstarc; G->verticesd.firstarc=q; /將新建的以s為信息的表結(jié)點q插入d單鏈表的頭結(jié)點后 /*深度遍歷*/int visitedMAXVER;/定義全局?jǐn)?shù)組遍歷visitedvoid dfs(ALGraph G, int v)/被遍歷的圖G采用鄰接表作為存儲結(jié)構(gòu)，v為出發(fā)頂點編號 ArcNode *p;printf("%s",G.verticesv.data); visitedv=1; p=G.verticesv.firstarc; while(p!=NULL) if(visitedp->adjvex=0) d

28、fs(G,p->adjvex); /若p所指表結(jié)點對應(yīng)的鄰接頂點未訪問則遞歸地從該頂點出發(fā)調(diào)用dfs p=p->nextarc; void dfsTraverse(ALGraph G) int v; /遍歷圖之前初始化各未訪問的頂點 for(v=1; v<=G.vexnum; v+) visitedv=0; /從各個未被訪問過的頂點開始進(jìn)行深度遍歷 for(v=1;v<=G.vexnum;v+) if(visitedv=0) dfs(G,v);/*廣度遍歷*/void BFS(ALGraph G, int v)/從頂點編號v出發(fā)，廣度遍歷鄰接表存儲的圖G SqQueue

29、 Q; ArcNode *p; InitQueue(&Q); printf("%s",G. verticesv.data); visitedv=1; EnQueue(&Q,v); while(!QueueEmpty(Q) v=DeQueue(&Q,&v); p=G.verticesv.firstarc; while(p!=NULL) if(visitedp->adjvex=0) v=p->adjvex; printf("%s",G.verticesv.data); visitedv=1; EnQueue(&am

30、p;Q,v); p=p->nextarc; void BFSTraverse(ALGraph G) int v; /遍歷G以前，初始化visited數(shù)組為0 for(v=1;v<=G.vexnum;v+) visitedv=0; for(v=1;v<=G.vexnum;v+) if(visitedv=0) BFS(G,v);void main() ALGraph G; createALGraph(&G); printf("深度遍歷結(jié)果為：n"); dfsTraverse(G); printf("n廣度遍歷結(jié)果為：n"); BFS

31、Traverse(G); system("pause"); 八、測試情況程序的測試結(jié)果如下：1、基于鄰接矩陣的圖的深度、廣度遍歷結(jié)果正確2、基于鄰接表的圖的深度、廣度遍歷結(jié)果正確九、參考文獻(xiàn) 1、嚴(yán)蔚敏，數(shù)據(jù)結(jié)構(gòu) C語言，清華大學(xué)出版社。 2、譚浩強(qiáng)，c語言程序設(shè)計，清華大學(xué)出版社。小結(jié) 圖的遍歷是有關(guān)于圖的算法中最常見、最典型的算法。與樹的遍歷相類似，圖的遍歷是從圖中任意一個頂點出發(fā)，訪問遍圖中所有的頂點，且使每個頂點僅被訪問一次。圖的遍歷算法是求解圖的連通性、拓?fù)渑判?、和求關(guān)鍵路徑等算法的基礎(chǔ)。由于圖本身結(jié)構(gòu)的復(fù)雜性，因而使得圖的遍歷要比樹的遍歷復(fù)雜得多。首先，圖中所有頂點沒有主次之分，因此也就沒有一個 “自然”的起始點；其次，圖中任意頂點均有可能與其它頂點相鄰，在沿著某一路徑依次搜索訪問頂點時完全有可能又回到該頂點上；此外，圖中某一頂點可能與多個頂點相鄰，當(dāng)訪問過該結(jié)點后，如何選擇下一個要訪問的頂點，就成為一個決策問題。鑒于圖的遍歷的復(fù)雜性，遍歷算法的設(shè)計就必須考慮圖的結(jié)構(gòu)特征。圖的遍歷算法通常有兩條遍歷路徑：深度優(yōu)先遍歷和廣度優(yōu)先遍歷。通過學(xué)習(xí)了圖的深度遍歷和廣度遍歷，我們對鄰接表和鄰接矩陣進(jìn)行深度遍歷和廣度遍歷。圖的深度遍歷類似于樹的先根遍歷，廣度遍歷類似于樹的層次遍歷。在實際中，由于在圖中各個結(jié)點的度數(shù)各個不同，最大度數(shù)和最