1、一，實驗題目實驗十一：圖實驗采用鄰接表存儲有向圖，設(shè)計算法判斷任意兩個頂點間手否存在路徑。 二，問題分析本程序要求采用鄰接表存儲有向圖，設(shè)計算法判斷任意兩個頂點間手否存在路徑，完成這些操作需要解決的關(guān)鍵問題是：用鄰接表的形式存儲有向圖并輸出該鄰接表。用一個函數(shù)實現(xiàn)判斷任意兩點間是否存在路徑。1， 數(shù)據(jù)的輸入形式和輸入值的范圍：輸入的圖的結(jié)點均為整型。2， 結(jié)果的輸出形式：輸出的是兩結(jié)點間是否存在路徑的情況。3， 測試數(shù)據(jù)：輸入的圖的結(jié)點個數(shù)為：4 輸入的圖的邊得個數(shù)為：3 邊的信息為：1 2， 2 3，3 1 三，概要設(shè)計（1）為了實現(xiàn)上述程序的功能，需要：A，用鄰接表的方式構(gòu)建圖B，深度優(yōu)先

2、遍歷該圖的結(jié)點C，判斷任意兩結(jié)點間是否存在路徑（2）本程序包含6個函數(shù)：a，主函數(shù)main（）b，用鄰接表建立圖函數(shù)create_adjlistgraph()c，深度優(yōu)先搜索遍歷函數(shù) dfs()d，初始化遍歷數(shù)組并判斷有無通路函數(shù) dfs_trave()e，輸出鄰接表函數(shù) print()f，釋放鄰接表結(jié)點空間函數(shù) freealgraph()各函數(shù)間關(guān)系如右圖所示：create_adjlistgraph()dfs()dfs_trave()main（）print()freealgraph()四，詳細設(shè)計（1）鄰接表中的結(jié)點類型定義：typedef struct arcnode int adjvex

3、; arcnode *nextarc; arcnode;（2）鄰接表中頭結(jié)點的類型定義：typedef struct char vexdata; arcnode *firstarc; adjlist;（3）鄰接表類型定義：typedef struct adjlist vexticesmax; int vexnum,arcnum; algraph;（4）深度優(yōu)先搜索遍歷函數(shù)偽代碼：int dfs(algraph *alg,int i,int n) arcnode *p; visitedi=1; p=alg-vexticesi.firstarc; while(p!=NULL) if(visited

4、p-adjvex=0)if(p-adjvex=n) flag=1; dfs(alg,p-adjvex,n); if(flag=1) return 1; p=p-nextarc; return 0; （5）初始化遍歷數(shù)組并判斷有無通路函數(shù)偽代碼：void dfs_trave(algraph *alg,int x,int y)int i; for(i=0;ivexnum;i+) visitedi=0; dfs(alg,x,y); 五，源代碼#include stdio.h #include stdlib.h #include malloc.h #define max 100 typedef str

5、uct arcnode /定義鄰接表中的結(jié)點類型 int adjvex; /定點信息 arcnode *nextarc; /指向下一個結(jié)點的指針nextarcarcnode; typedef struct /定義鄰接表中頭結(jié)點的類型 char vexdata; /頭結(jié)點的序號 arcnode *firstarc; /定義一個arcnode型指針指向頭結(jié)點所對應(yīng)的下一個結(jié)點adjlist; typedef struct /定義鄰接表類型 adjlist vexticesmax; /定義表頭結(jié)點數(shù)組 int vexnum,arcnum; /定點個數(shù)和弧的個數(shù)algraph; algraph *cr

6、eate_adjlistgraph() /建立鄰接表函數(shù) int n,e,i,j,k; arcnode *p; /定義一個鄰接表結(jié)點型指針變量p algraph *al; /定義鄰接表表頭結(jié)點指針al al=(algraph *)malloc(sizeof(algraph); /為鄰接表結(jié)點申請空間 printf(請輸入節(jié)點數(shù)：n); scanf(%d,&n); /輸入結(jié)點數(shù) for(i=0;ivexticesi.vexdata=(char)i; /給頭結(jié)點賦值 al-vexticesi.firstarc=NULL; /初始化頭結(jié)點 printf(請輸入邊數(shù)：n); scanf(%d,&e);

7、 /輸入邊得數(shù)目 printf(請輸入弧的信息：n); for(i=0;iadjvex=k; /將k賦值給新申請的結(jié)點 p-nextarc=al-vexticesj.firstarc; /使新結(jié)點指向該頭結(jié)點所指向的下一個結(jié)點 al-vexticesj.firstarc=p; /使頭結(jié)點指向新結(jié)點 al-vexnum=n; /將頂點數(shù)n給al-vexnum al-arcnum=e; /將邊數(shù)e給al-arcnum return al; /返回該鄰接表 void print(algraph *alg) /輸出鄰接表 int i; arcnode *p; /定義一個鄰接表結(jié)點型指針變量p prin

8、tf(該圖的鄰接表輸出為：n); for(i=1;ivexnum;i+) /當在結(jié)點個數(shù)范圍內(nèi)時 printf(%d-,alg-vexticesi.vexdata); /輸出i頭結(jié)點的值 p=alg-vexticesi.firstarc; /把i頭結(jié)點所指的第一個結(jié)點給p while(p!=NULL) /當p不為空時 printf(%d-,p-adjvex); /輸出給結(jié)點 p=p-nextarc; /p指向下一個結(jié)點 printf(-n); void freealgraph(algraph *alg) /釋放鄰接表結(jié)點空間函數(shù) int i; arcnode *p,*q; /定義兩個鄰接表結(jié)點

9、型指針變量p，q for(i=0;ivexnum;i+) /當結(jié)點個數(shù)不超出范圍時 p=alg-vexticesi.firstarc; /p指向i頭結(jié)點所對應(yīng)的第一個結(jié)點 while(p!=NULL) /當p不為空時 q=p-nextarc; /q指向p的下一個結(jié)點 free(p); /釋放p p=q; /將q賦給p int visitedmax; /定義深度優(yōu)先搜索遍歷數(shù)組 int flag=0; /設(shè)置標志，用來判斷兩點間是否為通路int dfs(algraph *alg,int i,int n) /深度優(yōu)先搜索遍歷函數(shù)arcnode *p; /定義鄰接表結(jié)點類型指針pvisitedi=1

10、; /將頂點i設(shè)置為已訪問p=alg-vexticesi.firstarc; /使p指向i頭結(jié)點所指的第一個結(jié)點 while(p!=NULL) /當p不為空時if(visitedp-adjvex=0) /如果p結(jié)點未被訪問if(p-adjvex=n) /如果n=p結(jié)點的值flag=1; /則將標志位設(shè)置為1 dfs(alg,p-adjvex,n); /遞歸調(diào)用深度優(yōu)先搜索遍歷函數(shù)if(flag=1) /如果已被訪問return 1; /則返回1 p=p-nextarc; /p指向下一個結(jié)點 return 0; void dfs_trave(algraph *alg,int x,int y) /

11、初始化遍歷數(shù)組并判斷有無通路函數(shù)int i; for(i=0;ivexnum;i+) visitedi=0; dfs(alg,x,y); int main() /主函數(shù) int m,n; algraph *alg; alg=create_adjlistgraph(); /創(chuàng)建圖 print(alg); /輸出該圖 printf(請輸入任意要判定有無通路的兩個頂點（輸入（-1 -1）時退出）：); scanf(%d%d,&m,&n); while(m!=-1&n!=-1) dfs_trave(alg,m,n); /調(diào)用初始化遍歷數(shù)組并判斷有無通路函數(shù)if(flag=1) printf(頂點%d和%d之間存在路徑n,m,n); else printf(頂點%d和%d之間不存在路徑n,m,n); flag=0; printf(請輸入任意要判定有無通路的兩個頂點（輸入（-1 -1）時退出）：); scanf(%d%d,&m,&n); freealgr