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

第1頁(yè)共2頁(yè)《數(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)境硬件環(huán)境：微機(jī)軟件環(huán)境：WindowsXP，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的路徑（i≠j）。2、代碼：#include<stdio.h>#include<stdlib.h>#defineMaxVertexNum100/*最大頂點(diǎn)數(shù)為100*/typedefcharVertexType;typedefstructnode{/*邊表結(jié)點(diǎn)*/ intadjvex;/*鄰接點(diǎn)域*/ structnode*next;/*指向下一個(gè)鄰接點(diǎn)的指針域*/ /*若要表示邊上信息，則應(yīng)增加一個(gè)數(shù)據(jù)域info*/}EdgeNode;typedefstructvnode{/*頂點(diǎn)表結(jié)點(diǎn)*/ VertexTypevertex;/*頂點(diǎn)域*/ EdgeNode*firstedge;/*邊表頭指針*/}VertexNode;typedefVertexNodeAdjList[MaxVertexNum];/*AdjList是鄰接表類型*/typedefstruct{ AdjListadjlist;/*鄰接表*/ intn,e;/*頂點(diǎn)數(shù)和邊數(shù)*/}ALGraph;/*ALGraph是以鄰接表方式存儲(chǔ)的圖類型*/boolvisited[MaxVertexNum];voidCreateTestALGraph(ALGraph*G){/*建立有向圖的鄰接表存儲(chǔ)*/ inti,j; EdgeNode*s; G->n=8;G->e=9; for(i=0;i<G->n;i++)/*建立有n個(gè)頂點(diǎn)的頂點(diǎn)表*/ { G->adjlist[i].vertex='1'+i;//轉(zhuǎn)換為字符型 G->adjlist[i].firstedge=NULL;/*頂點(diǎn)的邊表頭指針設(shè)為空*/ } { i=0,j=1; s=(EdgeNode*)malloc(sizeof(EdgeNode));/*生成新邊表結(jié)點(diǎn)s*/ s->adjvex=j;/*鄰接點(diǎn)序號(hào)為j*/ s->next=G->adjlist[i].firstedge;/*將新邊表結(jié)點(diǎn)s插入到頂點(diǎn)Vi的邊表頭部*/ G->adjlist[i].firstedge=s; i=0,j=2; s=(EdgeNode*)malloc(sizeof(EdgeNode));//*生成新邊表結(jié)點(diǎn)s s->adjvex=j;//*鄰接點(diǎn)序號(hào)為j s->next=G->adjlist[i].firstedge;///*將新邊表結(jié)點(diǎn)s插入到頂點(diǎn)Vi的邊表頭部 G->adjlist[i].firstedge=s; i=1,j=3; s=(EdgeNode*)malloc(sizeof(EdgeNode));//*生成新邊表結(jié)點(diǎn)s s->adjvex=j;//*鄰接點(diǎn)序號(hào)為j s->next=G->adjlist[i].firstedge;//*將新邊表結(jié)點(diǎn)s插入到頂點(diǎn)Vi的邊表頭部 G->adjlist[i].firstedge=s; i=1,j=4; s=(EdgeNode*)malloc(sizeof(EdgeNode));//*生成新邊表結(jié)點(diǎn)s s->adjvex=j;//*鄰接點(diǎn)序號(hào)為j s->next=G->adjlist[i].firstedge;//*將新邊表結(jié)點(diǎn)s插入到頂點(diǎn)Vi的邊表頭部 G->adjlist[i].firstedge=s; i=2,j=0; s=(EdgeNode*)malloc(sizeof(EdgeNode));//*生成新邊表結(jié)點(diǎn)s s->adjvex=j;//*鄰接點(diǎn)序號(hào)為j s->next=G->adjlist[i].firstedge;//*將新邊表結(jié)點(diǎn)s插入到頂點(diǎn)Vi的邊表頭部 G->adjlist[i].firstedge=s; i=2,j=6; s=(EdgeNode*)malloc(sizeof(EdgeNode));//*生成新邊表結(jié)點(diǎn)s s->adjvex=j;//*鄰接點(diǎn)序號(hào)為j s->next=G->adjlist[i].firstedge;//*將新邊表結(jié)點(diǎn)s插入到頂點(diǎn)Vi的邊表頭部 G->adjlist[i].firstedge=s; i=3,j=4; s=(EdgeNode*)malloc(sizeof(EdgeNode));//*生成新邊表結(jié)點(diǎn)s s->adjvex=j;//*鄰接點(diǎn)序號(hào)為j s->next=G->adjlist[i].firstedge;//*將新邊表結(jié)點(diǎn)s插入到頂點(diǎn)Vi的邊表頭部 G->adjlist[i].firstedge=s; i=4,j=3; s=(EdgeNode*)malloc(sizeof(EdgeNode));//*生成新邊表結(jié)點(diǎn)s s->adjvex=j;//*鄰接點(diǎn)序號(hào)為j s->next=G->adjlist[i].firstedge;//*將新邊表結(jié)點(diǎn)s插入到頂點(diǎn)Vi的邊表頭部 G->adjlist[i].firstedge=s; }///*CreateALGraph}voidDFSTraverseAL(ALGraph*G){/*深度優(yōu)先遍歷以鄰接表存儲(chǔ)的圖G*/ inti; for(i=0;i<G->n;i++) visited[i]=false;/*標(biāo)志向量初始化*/ for(i=0;i<G->n;i++) if(!visited[i])DFSAL(G,i);/*vi未訪問(wèn)過(guò)，從vi開(kāi)始DFS搜索*/}/*DFSTraveseAL*///intlevel=1;//遞歸進(jìn)行的層數(shù)intexist_path_DFS(ALGraph*G,inti,intj)//深度優(yōu)先判斷有向圖G中頂點(diǎn)i到頂點(diǎn)j是否有路徑,是則返回1,否則返回0{EdgeNode*p;intk;if(i==j)return1;//i就是jelse{visited[i]=true;//for(p=G->adjlist[i].firstedge;p;p=p->next,level--) for(p=G->adjlist[i].firstedge;p;p=p->next){ //level++;k=p->adjvex;if(!visited[k]&&exist_path_DFS(G,k,j)) {printf("V%d",k+1); return1;//i下游的頂點(diǎn)到j(luò)有路徑 } }//for return0;}//else//if(level==1)return0;}//exist_path_DFSvoidmain(){ ALGraph*G; G=(ALGraph*)malloc(sizeof(ALGraph));CreateTestALGraph(G); inti,j;printf("請(qǐng)輸入i和j的值格式：i,j\n"); scanf("%d,%d",&i,&j); i=i-1; j=j-1; if(i==j) { printf("i不能等于j\n"); } else { if(exist_path_DFS(G,i,j)) { printf("該路徑存在。\n"); }else { printf("該路徑不存在。\n"); } } }3、測(cè)試數(shù)據(jù)與實(shí)驗(yàn)結(jié)果分析（可以用組合鍵Alt+PrintScreen截圖）：上述例子中建立的有向圖2121543543該有向圖的鄰接鏈表如下序號(hào)標(biāo)號(hào)0V11V22V3