數(shù)據(jù)結(jié)構(gòu)圖的遍歷實驗報告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上實驗報告課程名：數(shù)據(jù)結(jié)構(gòu)（C語言版）實驗名：圖的遍歷姓 名： 班 級： 學 號： 時 間：2014.11.15一 實驗目的與要求1. 掌握圖的遍歷的方法2. 利用 C 語言實現(xiàn)圖的遍歷二 實驗內(nèi)容 將一個圖存儲起來 對該圖分別進行先深和先廣遍歷三 實驗結(jié)果與分析程序：#include <stdlib.h>#include <stdio.h>#define INFINITY 32767#define MAX_VEX 20 /最大頂點個數(shù)#define QUEUE_SIZE (MAX_VEX+1) /隊列長度/using namespace std

2、;bool *visited; /訪問標志數(shù)組,避免同一頂點多次訪問/*圖的鄰接矩陣存儲結(jié)構(gòu)*/typedef struct char *vexs; /頂點向量 int arcsMAX_VEXMAX_VEX; /鄰接矩陣 int vexnum,arcnum; /圖的當前頂點數(shù)和弧數(shù)Graph;/*隊列類*/class Queue public: void InitQueue() base=(int *)malloc(QUEUE_SIZE*sizeof(int); front=rear=0; void EnQueue(int e) baserear=e; rear=(rear+1)%QUEUE_

3、SIZE; void DeQueue(int &e) e=basefront; front=(front+1)%QUEUE_SIZE; public: int *base; int front; int rear;/*圖G中查找元素c的位置*/int Locate(Graph G,char c) for(int i=0;i<G.vexnum;i+) if(G.vexsi=c) return i; return -1;/*創(chuàng)建無向網(wǎng)*/void CreateUDN(Graph &G) int i,j,w,s1,s2; char a,b,temp; printf("

4、輸入頂點數(shù)和弧數(shù):"); scanf("%d%d",&G.vexnum,&G.arcnum); temp=getchar(); /接收回車 G.vexs=(char *)malloc(G.vexnum*sizeof(char); /分配頂點數(shù)目 printf("輸入%d個頂點.n",G.vexnum); for(i=0;i<G.vexnum;i+) /初始化頂點 printf("輸入頂點%d:",i); scanf("%c",&G.vexsi); temp=getchar()

5、; /接收回車 for(i=0;i<G.vexnum;i+) /初始化鄰接矩陣 for(j=0;j<G.vexnum;j+) G.arcsij=INFINITY; printf("輸入%d條弧.n",G.arcnum); for(i=0;i<G.arcnum;i+) /初始化弧 printf("輸入弧%d:",i); scanf("%c %c %d",&a,&b,&w); /輸入一條邊依附的頂點和權(quán)值 temp=getchar(); /接收回車 s1=Locate(G,a); s2=Locat

6、e(G,b); G.arcss1s2=G.arcss2s1=w; /*圖G中頂點k的第一個鄰接頂點*/int FirstVex(Graph G,int k) if(k>=0 && k<G.vexnum) /k合理 for(int i=0;i<G.vexnum;i+) if(G.arcski!=INFINITY) return i; return -1;/*圖G中頂點i的第j個鄰接頂點的下一個鄰接頂點*/int NextVex(Graph G,int i,int j) if(i>=0 && i<G.vexnum &&

7、j>=0 && j<G.vexnum) /i,j合理 for(int k=j+1;k<G.vexnum;k+) if(G.arcsik!=INFINITY) return k; return -1;/*深度優(yōu)先遍歷*/void DFS(Graph G,int k) int i; if(k=-1) /第一次執(zhí)行DFS時,k為-1 for(i=0;i<G.vexnum;i+) if(!visitedi) DFS(G,i); /對尚未訪問的頂點調(diào)用DFS else visitedk=true; printf("%c ",G.vexsk);

8、/訪問第k個頂點 for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i) if(!visitedi) DFS(G,i); /對k的尚未訪問的鄰接頂點i遞歸調(diào)用DFS /*廣度優(yōu)先遍歷*/void BFS(Graph G) int k; Queue Q; /輔助隊列Q Q.InitQueue(); for(int i=0;i<G.vexnum;i+) if(!visitedi) /i尚未訪問 visitedi=true; printf("%c ",G.vexsi); Q.EnQueue(i); /i入列 while(Q.front!=Q

9、.rear) Q.DeQueue(k); /隊頭元素出列并置為k for(int w=FirstVex(G,k);w>=0;w=NextVex(G,k,w) if(!visitedw) /w為k的尚未訪問的鄰接頂點 visitedw=true; printf("%c ",G.vexsw); Q.EnQueue(w); /*主函數(shù)*/void main() int i; Graph G; CreateUDN(G); visited=(bool *)malloc(G.vexnum*sizeof(bool); printf("n廣度優(yōu)先遍歷: "); for(i=0;i<