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

1、福建江夏學(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)先遍歷編寫一個(gè)算法，判別以鄰接表方式存儲(chǔ)的有向圖中是否存在由 頂點(diǎn)vi到頂點(diǎn)vj的路徑（i工j）。2、代碼：#in elude #in elude #define MaxVertexNum 100 /* 最大頂點(diǎn)數(shù)為 100*/typedef char Ver

2、texType;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 AdjListMaxVertexNum; /*AdjList是鄰接表類型 */typedef

3、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),&(G-e); /* 讀入頂點(diǎn)數(shù)和邊數(shù) */ printf( 請(qǐng)輸入頂點(diǎn)信息 (輸入格式為 :頂點(diǎn)號(hào) ) ：n);f

4、or (i=0;in;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;ke;k+) /* 建立邊表 */scanf(n%d,%d,&i,&j); /* 讀入邊 的頂點(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

5、-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ì)鄰接表存儲(chǔ)的圖 G 進(jìn)行 DFS 搜索 */EdgeNode *p;printf(visit vertex:V%cn,G-adjlisti.vertex);/* 訪問頂點(diǎn) Vi*/visitedi=true; /* 標(biāo)記 Vi 已訪問 */p=G-adjlisti.firstedge; /* 取 Vi 邊表的頭指針 *

6、/while(p) /* 依次搜索 Vi 的鄰接點(diǎn) Vj ， j=p-adjva*/if (!visitedp-adjvex) /* 若 Vj 尚未訪問，則以 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;in;i+)visitedi=false; /* 標(biāo)志向量初始化 */for (i=0;in;i+)if (!visitedi) DFSAL(G,i); /*vi未訪

7、問過，從 vi 開始 DFS 搜索*/*DFSTraveseAL*/void mai n()ALGraph *G;G=(ALGraph *)malloc(sizeof(ALGraph);CreateALGraph(G);printf(深度優(yōu)先搜索結(jié)果：n);DFSTraverseAL(G);3、測(cè)試數(shù)據(jù)與實(shí)驗(yàn)結(jié)果分析（可以用組合鍵Alt+Print Screen截圖）:“電路分析I數(shù)據(jù)Debugl. eze-請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)（輸入格式為:頂點(diǎn)數(shù)邊救: g 乎喬輸入頂點(diǎn)信息t輸入格式為二頂點(diǎn)號(hào)CR：1 2 3 4 5 6 7 8請(qǐng)輸入邊的信息t輸入格式為:j：3r2 0fl 1,4 3,7 4r7 22r51,3尊厚優(yōu)先搜索結(jié)果；vi?it vertex：U1u i