無向圖的存儲及深度和廣度優(yōu)先遍歷

1、數據結構實驗報告實驗題目:無序圖的存儲并分別實現深度和廣度優(yōu)先遍歷實驗目的：理解并掌握以鄰接表的方式存儲圖，以及圖的非遞歸的深度和廣度優(yōu)先遍歷實驗內容：首先將圖的元素輸入并以鄰接表的方式存儲，然后分別進行遞歸和非遞歸遍歷。 一、需求分析1、輸入的形式和輸入值的范圍：輸入圖的頂點元素和邊；輸入數字選擇要進行的操作：深度遍歷，廣度遍歷或結束操作。2、輸出的形式:按深度或者廣度優(yōu)先順序輸出各節(jié)點的編號3、程序所能達到的功能：（1）以鄰接表的方式存儲圖（2）對圖進行深度優(yōu)先的非遞歸遍歷（3）對圖進行廣度優(yōu)先的非遞歸遍歷4、測試數據：輸入各結點元素：a,b,c,d,e,f,g,h；輸入圖中的各邊：1,2

2、 1,3 2,4 2,5 3,6 3,7 4,8 5,8操作選項 輸入1進行深度優(yōu)先遍歷；遍歷結果為：1 3 7 6 2 5 8 4操作選項 輸入2進行廣度優(yōu)先遍歷；遍歷結果為：1 3 2 7 6 5 4二 概要設計（1）抽象數據類型定義：#define MaxVerNum 100/邊表結點typedef struct nodeint adjvex;struct node *next;EdgeNode,*ENode;頂點表結點；typedef struct vnodechar vertex;EdgeNode *firstedge;VertexNode;typedef VertexNode Ad

3、jListMaxVerNum;定義圖；typedef structAdjList adjlist;int n,e;AlGraph;AlGraph G;（2）主程序的流程：1. 根據提示輸入頂點個數和邊的個數；2. 輸入圖的各邊； 3. 輸入數字執(zhí)行相關操作（3）其函數之間調用關系如下：main()模塊 （開始創(chuàng)建鏈表）Create（）創(chuàng)建圖輸入1輸入2按廣度優(yōu)先遍歷按深度優(yōu)先遍歷 輸入0結束操作 執(zhí)行結束后，重新執(zhí)行判定操作和循環(huán)。三 詳細設計1.元素類型#define MaxVerNum 100typedef struct nodeint adjvex;struct node *next;E

4、dgeNode,*ENode;typedef struct vnodechar vertex;EdgeNode *firstedge;VertexNode;typedef VertexNode AdjListMaxVerNum;typedef structAdjList adjlist;int n,e;AlGraph;AlGraph G;2每個模塊的分析：（1）主程序模塊：int main() int a,v; /創(chuàng)建圖Create(G); printf("請選擇要進行的操作：n 選擇深度優(yōu)先請輸入1；n 選擇廣度優(yōu)先請輸入2；n結束操作請輸入0n"); scanf(&qu

5、ot;%d",&a); while(a!=0) printf("請輸入開始遍歷頂點的坐標n"); scanf("%d",&v); if(a=1) /深度優(yōu)先遍歷 DfsTravel(G,v); else if(a=2) /廣度優(yōu)先遍歷 BfsTravel(G,v); printf("請選擇要進行的操作：n 選擇深度優(yōu)先請輸入1；n 選擇廣度優(yōu)先請輸入2；n結束操作請輸入0n"); scanf("%d",&a); return 0;（2）深度優(yōu)先遍歷void DfsTravel(Al

6、Graph &G,int v)ENode stackMaxVerNum;ENode p;int visitedMaxVerNum,top=-1,i;for(i=0;i<G.n;i+)visitedi=0; printf("深度優(yōu)先遍歷的結果為：n"); printf("%d ",v);visitedv=1;p=G.adjlistv.firstedge;while(top!=-1|p!=NULL)while(p!=NULL)if(visitedp->adjvex=1)p=p->next;elseprintf("%d &q

7、uot;,p->adjvex);visitedp->adjvex=1;top+;stacktop=p;p=G.adjlistp->adjvex.firstedge;if(top!=-1) p=stacktop; top-; p=p->next;printf("n");（3）廣度優(yōu)先遍歷void BfsTravel(AlGraph &G,int v)int visitedMaxVerNum;int queueMaxVerNum;int front=-1,rear=-1; EdgeNode *p; int i; for(i=0;i<G.n;

8、i+)visitedi=0; printf("廣度優(yōu)先遍歷的結果為：n");printf("%d ",v);visitedv=1;rear=rear+1;queuerear=v;while(front!=rear) front+;v=queuefront;p=G.adjlistv.firstedge;while(p!=NULL)if(visitedp->adjvex=0)printf("%d ",p->adjvex); visitedp->adjvex=1;rear=rear+1;queuerear=p->ad

9、jvex;p=p->next;printf("n");(4)創(chuàng)建圖void Create(AlGraph &G)int i,j,k;EdgeNode *s,*r;printf("請依次輸入無向圖頂點個數和邊的個數n");scanf("%d,%d",&(G.n),&(G.e);getchar();printf("請輸入各頂點信息n");for(i=0;i<G.n;i+)scanf("%c",&(G.adjlisti.vertex);getchar();

10、G.adjlisti.firstedge=NULL;printf("請輸入各邊的信息，輸入格式為i,jn"); for(k=0;k<G.e;k+)scanf("%d,%d",&i,&j);s=(EdgeNode*)malloc(sizeof(EdgeNode);s->adjvex=j;s->next= G.adjlisti.firstedge;G.adjlisti.firstedge=s; r=(EdgeNode*)malloc(sizeof(EdgeNode);r->adjvex=i;r->next= G.adjlistj.firstedge;G.adjlistj.firstedge=r;四 使用說明、測試分析及結果輸入各結點元素：a,b,c,d,e,f,g,h；輸入圖中的各邊：1,2 1,3 2,4 2,5 3,6 3,7 4,8 5,8操作選項 輸入1進行深度優(yōu)先遍歷；遍歷結果為：1 3 7 6 2 5 8 4操作選項 輸入2進行廣度優(yōu)先遍歷；遍歷結果為：1 3 2 7 6 5 41.程序使用說明；（1）本程序的運行環(huán)境為VC6.0。（2）進入演示程序后即顯示提示信息：請輸入頂點個數和邊的個數：2、測試結果與分