深度優(yōu)先遍歷以鄰接表存儲(chǔ)的圖實(shí)驗(yàn)報(bào)告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上福建江夏學(xué)院數(shù)據(jù)結(jié)構(gòu)與關(guān)系數(shù)據(jù)庫(kù)（本科）實(shí)驗(yàn)報(bào)告姓名 班級(jí) 學(xué)號(hào) 實(shí)驗(yàn)日期 課程名稱 數(shù)據(jù)結(jié)構(gòu)與關(guān)系數(shù)據(jù)庫(kù)（本科） 指導(dǎo)教師 成績(jī)實(shí)驗(yàn)名稱：深度優(yōu)先遍歷以鄰接表存儲(chǔ)的圖一、 實(shí)驗(yàn)?zāi)康?、掌握以鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法；二、 實(shí)驗(yàn)環(huán)境1、 硬件環(huán)境：微機(jī)2、 軟件環(huán)境： Windows XP，VC6.0三、實(shí)驗(yàn)內(nèi)容、步驟及結(jié)果1、實(shí)驗(yàn)內(nèi)容：基于圖的深度優(yōu)先遍歷編寫(xiě)一個(gè)算法，判別以鄰接表方式存儲(chǔ)的有向圖中是否存在由頂點(diǎn)vi到頂點(diǎn)vj的路徑（ij）。 2、代碼：#include <stdio.h>#include <stdlib.h>#def

2、ine MaxVertexNum 100 /*最大頂點(diǎn)數(shù)為100*/typedef char VertexType;typedef struct node /*邊表結(jié)點(diǎn)*/int adjvex; /*鄰接點(diǎn)域*/struct node * next; /*指向下一個(gè)鄰接點(diǎn)的指針域*/*若要表示邊上信息，則應(yīng)增加一個(gè)數(shù)據(jù)域info*/EdgeNode;typedef struct vnode /*頂點(diǎn)表結(jié)點(diǎn)*/VertexType vertex; /*頂點(diǎn)域*/EdgeNode * firstedge; /*邊表頭指針*/VertexNode;typedef VertexNode AdjList

3、MaxVertexNum; /*AdjList 是鄰接表類型*/typedef structAdjList adjlist; /*鄰接表*/int n,e; /*頂點(diǎn)數(shù)和邊數(shù)*/ALGraph; /*ALGraph 是以鄰接表方式存儲(chǔ)的圖類型*/bool visitedMaxVertexNum;void CreateALGraph(ALGraph *G)/*建立有向圖的鄰接表存儲(chǔ)*/int i,j,k;EdgeNode * s;printf("請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)(輸入格式為:頂點(diǎn)數(shù),邊數(shù))：n");scanf("%d,%d",&(G->n)

4、,&(G->e); /*讀入頂點(diǎn)數(shù)和邊數(shù)*/printf("請(qǐng)輸入頂點(diǎn)信息(輸入格式為:頂點(diǎn)號(hào)<CR>)：n");for (i=0;i<G->n;i+) /*建立有n 個(gè)頂點(diǎn)的頂點(diǎn)表*/ scanf("n%c",&(G->adjlisti.vertex); /*讀入頂點(diǎn)信息*/G->adjlisti.firstedge=NULL; /*頂點(diǎn)的邊表頭指針設(shè)為空*/printf("請(qǐng)輸入邊的信息(輸入格式為:i,j)：n");for (k=0;k<G->e;k+) /*

5、建立邊表*/ scanf("n%d,%d",&i,&j); /*讀入邊<Vi,Vj>的頂點(diǎn)對(duì)應(yīng)序號(hào)*/s=(EdgeNode*)malloc(sizeof(EdgeNode); /*生成新邊表結(jié)點(diǎn)s*/s->adjvex=j; /*鄰接點(diǎn)序號(hào)為j*/s->next=G->adjlisti.firstedge; /*將新邊表結(jié)點(diǎn)s 插入到頂點(diǎn)Vi 的邊表頭部*/G->adjlisti.firstedge=s;/*CreateALGraph*/void DFSAL(ALGraph *G,int i)/*以Vi 為出發(fā)點(diǎn)對(duì)鄰接表

6、存儲(chǔ)的圖G 進(jìn)行DFS 搜索*/EdgeNode *p;printf("visit vertex:V%cn",G->adjlisti.vertex);/*訪問(wèn)頂點(diǎn)Vi*/visitedi=true; /*標(biāo)記Vi 已訪問(wèn)*/p=G->adjlisti.firstedge; /*取Vi 邊表的頭指針*/while(p) /*依次搜索Vi 的鄰接點(diǎn)Vj，j=p->adjva*/if (!visitedp->adjvex) /*若Vj 尚未訪問(wèn)，則以Vj 為出發(fā)點(diǎn)向縱深搜索*/DFSAL(G,p->adjvex);p=p->next; /*找Vi 的下一個(gè)鄰接點(diǎn)*/*DFSAL*/void DFSTraverseAL(ALGraph *G)/*深度優(yōu)先遍歷以鄰接表存儲(chǔ)的圖G*/int i;for (i=0;i<G->n;i+)visitedi=false; /*標(biāo)志向量初始化*/for (i=0;i<G->n;i+)if (!visitedi) DFSAL(G,i); /*vi 未訪問(wèn)過(guò)，從vi 開(kāi)始DFS 搜索*/*DFSTraveseAL*/void main() ALGraph *G;G=(ALGraph *)malloc(sizeof(ALGraph); CreateALGrap