2-深度優(yōu)先遍歷以鄰接表存儲的圖-實驗報告

第1頁共2頁《數(shù)據(jù)結構與關系數(shù)據(jù)庫（本科）》實驗報告姓名班級學號實驗日期課程名稱數(shù)據(jù)結構與關系數(shù)據(jù)庫（本科）指導教師成績實驗名稱：深度優(yōu)先遍歷以鄰接表存儲的圖實驗目的1、掌握以鄰接表存儲的圖的深度優(yōu)先遍歷算法；實驗環(huán)境硬件環(huán)境：微機軟件環(huán)境：WindowsXP，VC6.0三、實驗內容、步驟及結果1、實驗內容：基于圖的深度優(yōu)先遍歷編寫一個算法，判別以鄰接表方式存儲的有向圖中是否存在由頂點vi到頂點vj的路徑（i≠j）。2、代碼：#include<stdio.h>#include<stdlib.h>#defineMaxVertexNum100/*最大頂點數(shù)為100*/typedefcharVertexType;typedefstructnode{/*邊表結點*/ intadjvex;/*鄰接點域*/ structnode*next;/*指向下一個鄰接點的指針域*/ /*若要表示邊上信息，則應增加一個數(shù)據(jù)域info*/}EdgeNode;typedefstructvnode{/*頂點表結點*/ VertexTypevertex;/*頂點域*/ EdgeNode*firstedge;/*邊表頭指針*/}VertexNode;typedefVertexNodeAdjList[MaxVertexNum];/*AdjList是鄰接表類型*/typedefstruct{ AdjListadjlist;/*鄰接表*/ intn,e;/*頂點數(shù)和邊數(shù)*/}ALGraph;/*ALGraph是以鄰接表方式存儲的圖類型*/boolvisited[MaxVertexNum];voidCreateTestALGraph(ALGraph*G){/*建立有向圖的鄰接表存儲*/ inti,j; EdgeNode*s; G->n=8;G->e=9; for(i=0;i<G->n;i++)/*建立有n個頂點的頂點表*/ { G->adjlist[i].vertex='1'+i;//轉換為字符型 G->adjlist[i].firstedge=NULL;/*頂點的邊表頭指針設為空*/ } { i=0,j=1; s=(EdgeNode*)malloc(sizeof(EdgeNode));/*生成新邊表結點s*/ s->adjvex=j;/*鄰接點序號為j*/ s->next=G->adjlist[i].firstedge;/*將新邊表結點s插入到頂點Vi的邊表頭部*/ G->adjlist[i].firstedge=s; i=0,j=2; s=(EdgeNode*)malloc(sizeof(EdgeNode));//*生成新邊表結點s s->adjvex=j;//*鄰接點序號為j s->next=G->adjlist[i].firstedge;///*將新邊表結點s插入到頂點Vi的邊表頭部 G->adjlist[i].firstedge=s; i=1,j=3; s=(EdgeNode*)malloc(sizeof(EdgeNode));//*生成新邊表結點s s->adjvex=j;//*鄰接點序號為j s->next=G->adjlist[i].firstedge;//*將新邊表結點s插入到頂點Vi的邊表頭部 G->adjlist[i].firstedge=s; i=1,j=4; s=(EdgeNode*)malloc(sizeof(EdgeNode));//*生成新邊表結點s s->adjvex=j;//*鄰接點序號為j s->next=G->adjlist[i].firstedge;//*將新邊表結點s插入到頂點Vi的邊表頭部 G->adjlist[i].firstedge=s; i=2,j=0; s=(EdgeNode*)malloc(sizeof(EdgeNode));//*生成新邊表結點s s->adjvex=j;//*鄰接點序號為j s->next=G->adjlist[i].firstedge;//*將新邊表結點s插入到頂點Vi的邊表頭部 G->adjlist[i].firstedge=s; i=2,j=6; s=(EdgeNode*)malloc(sizeof(EdgeNode));//*生成新邊表結點s s->adjvex=j;//*鄰接點序號為j s->next=G->adjlist[i].firstedge;//*將新邊表結點s插入到頂點Vi的邊表頭部 G->adjlist[i].firstedge=s; i=3,j=4; s=(EdgeNode*)malloc(sizeof(EdgeNode));//*生成新邊表結點s s->adjvex=j;//*鄰接點序號為j s->next=G->adjlist[i].firstedge;//*將新邊表結點s插入到頂點Vi的邊表頭部 G->adjlist[i].firstedge=s; i=4,j=3; s=(EdgeNode*)malloc(sizeof(EdgeNode));//*生成新邊表結點s s->adjvex=j;//*鄰接點序號為j s->next=G->adjlist[i].firstedge;//*將新邊表結點s插入到頂點Vi的邊表頭部 G->adjlist[i].firstedge=s; }///*CreateALGraph}voidDFSTraverseAL(ALGraph*G){/*深度優(yōu)先遍歷以鄰接表存儲的圖G*/ inti; for(i=0;i<G->n;i++) visited[i]=false;/*標志向量初始化*/ for(i=0;i<G->n;i++) if(!visited[i])DFSAL(G,i);/*vi未訪問過，從vi開始DFS搜索*/}/*DFSTraveseAL*///intlevel=1;//遞歸進行的層數(shù)intexist_path_DFS(ALGraph*G,inti,intj)//深度優(yōu)先判斷有向圖G中頂點i到頂點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下游的頂點到j有路徑 } }//for return0;}//else//if(level==1)return0;}//exist_path_DFSvoidmain(){ ALGraph*G; G=(ALGraph*)malloc(sizeof(ALGraph));CreateTestALGraph(G); inti,j;printf("請輸入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、測試數(shù)據(jù)與實驗結果分析（可以用組合鍵Alt+PrintScreen截圖）：上述例子中建立的有向圖2121543543該有向圖的鄰接鏈表如下序號標號0V11V22V3