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

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

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

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

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

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

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