圖的遍歷算法

1、昌吉學(xué)院計(jì)算機(jī)計(jì)算機(jī)工程系學(xué)生實(shí)驗(yàn)報(bào)告班級(jí)： B1103班 姓名 乃比江塔依爾 學(xué)號(hào)1125929073 日期 2013年12月06號(hào) 課程名稱(chēng)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)室名稱(chēng)1324實(shí)驗(yàn)名稱(chēng)圖的遍歷算法指導(dǎo)教師香麗蕓成績(jī)一、實(shí)驗(yàn)?zāi)康?1、使學(xué)生可以鞏固所學(xué)的有關(guān)圖的基本知識(shí)。 2、熟練掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu)。 3、熟練掌握?qǐng)D的兩種遍歷算法。二、實(shí)驗(yàn)原理和內(nèi)容 實(shí)驗(yàn)原理：深度優(yōu)先搜索遍歷是樹(shù)的先根遍歷的推廣。假設(shè)初始狀態(tài)時(shí)圖中所有頂點(diǎn)未曾訪問(wèn)，則深度優(yōu)先搜索可從圖中某個(gè)頂點(diǎn)a出發(fā)，訪問(wèn)此頂點(diǎn)，然后依次從a的未被訪問(wèn)的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直至圖中所有與a有路徑相通的頂點(diǎn)都被訪問(wèn)到；若此時(shí)圖

2、中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未曾訪問(wèn)的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)到為止。實(shí)驗(yàn)內(nèi)容：編寫(xiě)函數(shù)實(shí)現(xiàn)隊(duì)列的刪除功能，編寫(xiě)函數(shù)實(shí)現(xiàn)隊(duì)列的插入功能，編寫(xiě)程序?qū)崿F(xiàn)以下功能。三、實(shí)驗(yàn)步驟 深度優(yōu)先算法：計(jì)算機(jī)程序的一種編制原理，就是在一個(gè)問(wèn)題出現(xiàn)多種可以實(shí)現(xiàn)的方法和技術(shù)的時(shí)候，應(yīng)該優(yōu)先選擇哪個(gè)更合適的，也是一種普遍的邏輯思想，此種思想在運(yùn)算的過(guò)程中，用到計(jì)算機(jī)程序的一種遞歸的思想。    度優(yōu)先搜索算法：又稱(chēng)廣度優(yōu)先搜索，是最簡(jiǎn)便的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。Dijkstra單源最短路徑算法和Prim 最小生

3、成樹(shù)算法都采用了和寬度優(yōu)先搜索類(lèi)似的思想。其別名又叫BFS，屬于一種盲目搜尋法，目的是系統(tǒng)地展開(kāi)并檢查圖中的所有節(jié)點(diǎn)，以找尋結(jié)果。換句話 說(shuō)，它并不考慮結(jié)果的可能位址，徹底地搜索整張圖，直到找到結(jié)果為止。代碼如下：#include<stdio.h> #include<malloc.h> typedef struct linknodeint adjvecx; struct linknode *next; linknode; typedef struct vnode char data; linknode *first; vnode,adjlist100; typ

4、edef struct int n; adjlist vertices; graph; int visited10; struct queue int rear,front; int node100; ; /隊(duì)的初始化 void initqueue(queue &Q) Q.rear=-1; Q.front=-1; for(int i=0;i<100;i+) Q.nodei=0; /判斷隊(duì)是否為空 int isEmpty(queue &Q) if(Q.rear=Q.front) return 0; else return 1; /入隊(duì) void enqueue(queue

5、&Q,int e) Q.rear=(Q.rear+1)%100; Q.nodeQ.rear=e; / Q.rear=(Q.rear+1)%100; /出隊(duì) int dequeue(queue &Q) int v; if(isEmpty(Q)=0) printf("該隊(duì)列為空n"); Q.front=(Q.front+1)%100; v=Q.nodeQ.front; return v; / for(int i=0;i<100;i+) / Q.noden+1=Q.noden; / /構(gòu)建鏈表 void creatlinknode(graph *g,int

6、k) linknode *p,*q;int a,b,j; / p=G.verticesk.first; printf("請(qǐng)輸入第%d個(gè)頂點(diǎn)所指向的頂點(diǎn)的個(gè)數(shù)：",k+1); scanf("%d",&a); if(a!=0) printf("輸入其所指向的第1個(gè)定點(diǎn)的位置:"); scanf("%d",&b); q=(struct linknode*)malloc(sizeof(struct linknode); q->adjvecx=b;q->next=NULL; g->verti

7、cesk.first=q; p=q; for( j=0;j<a-1;j+) printf("輸入其所指向的第%d個(gè)定點(diǎn)的位置:",j+2); scanf("%d",&b); q=(struct linknode*)malloc(sizeof(struct linknode); q->adjvecx=b;q->next=NULL; p->next=q;p=p->next; else g->verticesk.first=NULL; /構(gòu)建 void creatgraph(graph *g) /int a; /in

8、t A10; printf("請(qǐng)輸入頂點(diǎn)的個(gè)數(shù):"); scanf("%d",&g->n); printf("請(qǐng)輸入頂點(diǎn)的值："); for(int i=0;i<g->n;i+) getchar(); scanf("%c",&g->verticesi.data); for(int k=0;k<g->n;k+) creatlinknode(g, k); /深度遍歷 void dfsal(graph *g,int i) int w;/linknode *p; / p=

9、(struct linknode*)malloc(sizeof(struct linknode) / for(int j=0;j<g->n;j+) visitedj=0; printf("%5c",g->verticesi.data); visitedi=1; for(linknode *p=g->verticesi.first;p;p=p->next) w=p->adjvecx; if(visitedw=0) dfsal(g,w); /廣度遍歷 void bfsal(graph *g,int i) queue Q;int w,e; in

10、t v; linknode *p; for(int j=0;j<g->n;j+) visitedj=0; visitedi=1; printf("%5c",g->verticesi.data); e=i; initqueue(Q);enqueue(Q,e); / n=isEmpty(Q); while(isEmpty(Q)=1) v=dequeue(Q); p=g->verticesv.first; / if(p!=NULL) / for( linknode *p=g->verticesv.first;p=NULL;p=p->next)

11、/此上面的循環(huán)此處不可用否則只輸出第一個(gè)數(shù) while(p!=NULL) w=p->adjvecx; if(visitedw=0) /printf("%c",p->adjvecx); printf("%5c",g->verticesw.data); visitedw=1; enqueue(Q,w); p=p->next; / int main(void) int A=1,choice; graph G,*g;g=&G; / for(i=0;i<10;i+) / / visitedi=0; / for(int j=0;j<g->n;j+) visitedj=0; while(A=1) printf("ntt*有向圖*");printf("ntt*"); printf("ntt* 1-建 立 *"); printf("ntt* 2-深度優(yōu)先遍歷 *"); printf("ntt* 3-廣度優(yōu)先遍歷 *"); printf("ntt* 0-退出*"); printf("ntt*"); printf("ntt"); printf("