《大數(shù)據(jù)結構圖》由會員分享，可在線閱讀，更多相關《大數(shù)據(jù)結構圖（16頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、word常熟理工學院數(shù)據(jù)結構與算法實驗指導與報告書_2017-2018_學年 第_1_ 學期專 業(yè)：物聯(lián)網(wǎng)工程 實驗名稱： 實驗七圖實驗地點： N6-210指導教師： 聶盼紅 計算機科學與工程學院2017實驗七圖【實驗目的】1、掌握圖的鄰接矩陣和鄰接表表示。2、掌握圖的深度優(yōu)先和廣度優(yōu)先搜索方法。3、掌握圖的最小生成樹Prim算法。4、掌握圖的拓撲排序算法。5、掌握圖的單源最短路徑dijkstra算法?！緦嶒瀸W時】4-6學時【實驗預習】回答以下問題：1、寫出圖7-1無向圖的鄰接矩陣表示。2、寫出圖7-2有向圖的鄰接表表示。3、寫出圖7-1的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列。深度優(yōu)先搜索序列：

2、A,C,B,D,E,F,G,H廣度優(yōu)先搜索序列：A,B,C,D,E,F,G,H,4、寫出圖7-2的拓撲序列，說明該有向圖是否有環(huán)？拓撲序列:EABCD該有向圖沒有環(huán)5、根據(jù)圖7-3，寫出其最小生成樹。圖7-3 無向帶權圖G36、根據(jù)圖7-4，求從頂點A到其他頂點的單源最短路徑。X圖7-4有向帶權圖G4單源最短路徑：=10:AC=50:AED=30:AE=60:AEDF【實驗容和要求】1、 編寫程序exp7_1.c，實現(xiàn)圖的鄰接矩陣存儲及圖的深度優(yōu)先搜索和廣度優(yōu)先搜索。以圖7-1的無向圖為例，補充完整程序，調(diào)試運行并寫出運行結果。運行結果：（包括輸入數(shù)據(jù)）exp7_1.c參考程序如下：#incl

3、ude#define N 20#define TRUE 1#define FALSE 0#define MAX 100int visitedN;/*訪問標志數(shù)組*/typedef struct /*輔助隊列的定義*/ int dataN; int front,rear;queue;typedef struct /*圖的鄰接矩陣表示*/ int vexnum,arum; char vexsN; int arcsNN;MGraph;void createGraph(MGraph *g); /*建立一個無向圖的鄰接矩陣*/void dfs(int i, MGraph *g); /*從第i個頂點出發(fā)深

4、度優(yōu)先搜索*/void tdfs(MGraph *g); /*深度優(yōu)先搜索整個圖*/void bfs(int k, MGraph *g); /*從第k個頂點廣度優(yōu)先搜索*/void tbfs(MGraph *g); /*廣度優(yōu)先搜索整個圖*/void init_visit(); /*初始化訪問標識數(shù)組*/void createGraph(MGraph *g) /*建立一個無向圖的鄰接矩陣*/ int i=0,j,e=0; char v; g-vexnum=0; g-arum=0; printf(n輸入頂點序列(以#結束)：n); while (v=getchar()!=#) g-vexsi=v

5、; /*讀入頂點信息*/ i+; g-vexnum=i; /*頂點數(shù)目*/ for (i=0;ivexnum;i+) /*鄰接矩陣初始化*/ for (j=0;jvexnum;j+) g-arcsij=0;/*（1）-鄰接矩陣元素初始化為0*/ printf(n輸入邊的信息(頂點序號,頂點序號)，以(-1,-1)結束：n); scanf(%d,%d,&i,&j); /*讀入邊(i,j)*/ while (i!=-1) /*讀入i為1時結束*/ g-arcsij=1;/*（2）-i,j對應邊等于1*/ e+; scanf(%d,%d,&i,&j); g-arum=e; /*邊數(shù)目*/* crea

6、teGraph */*（3）-從第i個頂點出發(fā)深度優(yōu)先搜索，補充完整算法*/void dfs(int i, MGraph *g) int j; printf(%c,g-vexsi); visitedi=1; for(j=0;jvexnum;j+) if(g-arcsij=1)&(!visitedj) dfs(j,g);/* dfs */void tdfs(MGraph *g) /*深度優(yōu)先搜索整個圖*/ int i; printf(n從頂點%C開始深度優(yōu)先搜索序列：,g-vexs0); for (i=0;ivexnum;i+) if (visitedi!=1) /*（4）-對尚未訪問過的頂點進

7、行深度優(yōu)先搜索*/ dfs(i,g); printf(n);/*tdfs*/void bfs(int k, MGraph *g) /*從第k個頂點廣度優(yōu)先搜索*/ int i,j; queue qlist,*q; q=&qlist; q-rear=0; q-front=0; printf(%c,g-vexsk); visitedk=TRUE; q-dataq-rear=k; q-rear=(q-rear+1)%N; while (q-rear!=q-front) /*當隊列不為空，進行搜索*/ i=q-dataq-front; q-front=(q-front+1)%N; for (j=0;j

8、vexnum;j+) if (g-arcsij=1)&(!visitedj) printf(%c,g-vexsj); visitedj=TRUE; q-dataq-rear=j; /*（5）-剛訪問過的結點入隊*/ q-rear=(q-rear+1)%MAX; /*（6）-修改隊尾指針*/ /*bfs*/void tbfs(MGraph *g) /*廣度優(yōu)先搜索整個圖*/ int i; printf(n從頂點%C開始廣度優(yōu)先搜索序列：,g-vexs0); for (i=0;ivexnum;i+) if (visitedi!=TRUE) bfs(i,g);/*從頂點i開始廣度優(yōu)先搜索*/ pri

9、ntf(n);/*tbfs*/void init_visit() /*初始化訪問標識數(shù)組*/ int i; for (i=0;iN;i+) visitedi=FALSE;int main() MGraph ga; int i,j; printf(*圖鄰接矩陣存儲和圖的遍歷*n); printf(n1-輸入圖的基本信息：n); createGraph(&ga); printf(n2-無向圖的鄰接矩陣：n); for (i=0;iga.vexnum;i+) for (j=0;jga.vexnum;j+) printf(%3d,ga.arcsij); printf(n); printf(n3-圖的遍

10、歷：n); init_visit(); /*初始化訪問數(shù)組*/ tdfs(&ga); /*深度優(yōu)先搜索圖*/ init_visit(); tbfs(&ga); /*廣度優(yōu)先搜索圖*/ return 0;2、 編寫程序exp7_2.c，實現(xiàn)圖的鄰接表存儲和拓撲排序算法。以圖7-2的有向圖為例，補充完整程序，調(diào)試運行并寫出運行結果。運行結果：（包括輸入數(shù)據(jù)）exp7_2.c程序代碼參考如下：#include#include#define N 20/*圖的鄰接表：鄰接鏈表結點*/typedef struct EdgeNode int adjvex; /*頂點序號*/ struct EdgeNode

11、*next; /*下一個結點的指針*/ EdgeNode;/*圖的鄰接表：鄰接表*/typedef struct VNode char data; /*頂點信息*/ int ind; /*頂點入度*/ struct EdgeNode *link; /*指向鄰接鏈表指針*/ VNode;typedef struct ALgraph /*圖的鄰接表*/ int vexnum,arum; /*頂點數(shù)、弧數(shù)*/ VNode adjlistN;ALGraph;void createGraph_list(ALGraph *g); /*建立有向圖的鄰接表*/void topSort(ALGraph *g);

12、 /*拓撲排序*/*建立有向圖的鄰接表*/void createGraph_list(ALGraph *g) int i,j,e; char v; EdgeNode *s; i=0; e=0; printf(n輸入頂點序列(以#結束)：n); while(v=getchar()!=#) g-adjlisti.data=v; /*讀入頂點信息*/ g-adjlisti.link=NULL; g-adjlisti.ind=0; i+; g-vexnum=i; /*建立鄰接鏈表*/ printf(n請輸入弧的信息(頂點序號,頂點序號)，以(-1,-1)結束:n); scanf(%d,%d,&i,&j

13、); while(i!=-1) s=(struct EdgeNode*)malloc(sizeof(EdgeNode); s-adjvex=j; s-next=g-adjlisti.link; ; /*（1）s插入鏈表*/ g-adjlisti.link=s; g-adjlistj.ind+; /*（2）頂點j的入度加1*/ e+; scanf(%d,%d,&i,&j); g-arum=e;/*createGraph_list*/void topSort(ALGraph *g) /*拓撲排序*/ int i,j,k,top=0,m=0,sN; /*m為拓撲排序輸出的結點數(shù)*/ EdgeNode

14、 *p; for(i=0; ivexnum; i+) if(!g-adjlisti.ind) /*（3）入度為0的頂點入棧*/ stop+=i; printf(n輸出拓撲序列：); while(top0) j=s-top; printf(%c,g-adjlistj.data); m+; p=g-adjlistj.link; while(p!=NULL) k=p-adjvex; g-adjlistk.ind-; /*頂點k入度減1*/ if(g-adjlistk.ind=0) /*頂點k入度為0，進棧*/ stop+=k; p=p-next; printf(n共輸出%d個頂點n,m); if(m

15、vexnum) /*（4）當輸出頂點數(shù)小于圖的頂點數(shù)，表示有環(huán)*/ printf(圖中有環(huán)！); else printf(圖中無環(huán)！);/*topSort*/int main() ALGraph g; int i; EdgeNode *s; printf(*圖的鄰接表存儲結構和拓撲排序*n); printf(n1-輸入圖的基本信息：n); createGraph_list(&g); /*創(chuàng)建圖的鄰接表存儲結構*/ printf(n2-圖的鄰接表:); for(i=0; i%d,s-adjvex); s=s-next; printf(n); printf(n3-根據(jù)圖的鄰接表實現(xiàn)拓撲排序：n);

16、 topSort(&g); /*進行拓撲排序*/ return 0;（3）調(diào)試下面給出的圖的信息，寫出運行結果，畫出該有向圖。ABCDEF#1,01,32,12,53,23,43,54,05,05,15,4-1,-13、編寫程序exp7_3.c，實現(xiàn)帶權圖的存儲、圖的最小生成樹及單源最短路徑算法。以圖7-3（求該圖最小生成樹）和圖7-4（求該圖的單源最短路徑）為例，補充完整程序，調(diào)試運行并寫出運行結果。運行結果：（包括輸入數(shù)據(jù)）exp7_3.c程序代碼參考如下：#include #define N 20#define TRUE 1#define INF 10002766 /*鄰接矩陣中的無窮大

17、元素*/#define INFIN 10002767 /*比無窮大元素大的數(shù)*/typedef struct/*圖的鄰接矩陣表示*/ int vexnum,arum; char vexsN; int arcsNN;MGraph;void printPath(MGraph g, int startVex, int EndVex, int pathN); /*打印最短路徑*/void createMGraph_w(MGraph *g, int flag); /*建帶權圖的鄰接矩陣*/void prim(MGraph *g, int u); /*求最小生成樹Prim算法，u為出發(fā)頂點*/void d

18、ijkstra(MGraph g, int v); /*dijkstra算法求單源最短路徑*/void createMGraph_w(MGraph *g, int flag)/*建帶權圖的鄰接矩陣,若flag為1則為無向圖，flag為0為有向圖*/ int i,j,w; char v; g-vexnum=0; g-arum=0; i=0; printf(n輸入頂點序列(以#結束)：n); while(v=getchar()!=#) g-vexsi=v; /*讀入頂點信息*/ i+; g-vexnum=i; for(i=0; i6; i+) /*鄰接矩陣初始化*/ for(j=0; jarcsi

19、j=INF; printf(n輸入邊的信息：(頂點，頂點，權值)，以(-1,-1,-1)結束n); scanf(%d,%d,%d,&i,&j,&w); /*讀入邊(i,j,w)*/ while(i!=-1) /*讀入i為1時結束*/ g-arcsij=w; if(flag=1) g-arcsji=w; scanf(%d,%d,%d,&i,&j,&w); /*createMGraph_w*/void prim(MGraph *g, int u)/*求最小生成樹Prim算法，u為出發(fā)頂點*/ int lowcostN,closestN,i,j,k,min; for(i=0; ivexnum; i+

20、) /*求其他頂點到出發(fā)頂點u的權*/ lowcosti=g-arcsuj;/*（1）-頂點i到u的代價最小的邊權值*/ closesti=u; lowcostu=0; printf(n最小生成樹：n); for(i=1; ivexnum; i+) /*循環(huán)求最小生成樹中的各條邊*/ min=INFIN; for(j=0; jvexnum; j+) /*選擇得到一條代價最小的邊*/ if(lowcostj!=0&lowcostjvexsclosestk,g-vexsk,lowcostk); /*輸出該邊*/ lowcostk=0; /*頂點k納入最小生成樹 */ for(j=0; jvexnu

21、m; j+) /*求其他頂點到頂點k 的權*/ if(g-arcskj!=0&g-arcskjarcskj; /*（3）-其他頂點到k的代價最小的邊權值*/ closestj=k; /*prim*/void printPath(MGraph g, int startVex, int EndVex, int pathN) int stackN,top=0; /堆棧 int i,k,j; int flagN; /輸出路徑頂點標志 k=EndVex; for (i=0;i0) /找j到k的路徑 for (i=0;i %c(%d) ,g.vexsi,g.arcsji); /輸出j到k路徑頂點i fla

22、gi=1; j=i; k=stack-top; break; else if (i!=k) stacktop+=i; if (flagk=0) printf(- %c(%d),g.vexsk,g.arcsjk);void dijkstra(MGraph g, int v)/*dijkstra算法求單源最短路徑*/ int sN, pathNN,distN; int mindis,i,j,u,k; for(i=0; ig.vexnum; i+) disti=g.arcsvi; si=0; for(j=0; jg.vexnum; j+) pathij=0; if(distiINF) pathiv=

23、1; pathii=1; distv=0; sv=1; for(i=0,u=1; ig.vexnum; i+) mindis=INFIN; for(j=0; jg.vexnum; j+) if(sj=0) if(distjmindis) u=j; mindis=distj; su=1; for(j=0; jg.vexnum; j+) if(sj=0)&distu+g.arcsujdistj) distj=distu+g.arcsuj; for(k=0; k到各頂點的最短路徑n,g.vexsv); for (i=0;i頂點%c：,g.vexsv,g.vexsi); if (disti=INF|d

24、isti=0) printf(無路徑); else printf(%d ,disti); printf(經(jīng)過頂點：); printPath(g,v,i,path); /輸出v到i的路徑 /*dijkstra*/int main() int select; MGraph ga; do printf(n*MENU*n); printf( 1. 圖的最小生成樹-Prim算法n); printf( 2. 圖的單源最短路徑-dijstra算法n); printf( 0. EXIT); printf(n*MENU*n); printf(ninput choice:); scanf(%d,&select);

25、 getchar(); switch(select) case 1: printf(n1-圖的最小生成樹-Prim算法n); printf(n輸入帶權圖的基本信息：n); createMGraph_w(&ga,1); prim(&ga,0); break; case 2: printf(n2-圖的單源最短路徑-dijstra算法n); printf(n輸入帶權圖的基本信息：n); createMGraph_w(&ga,0); dijkstra(ga,0); break; default: break; while(select); return 0;【拓展實驗】4、編寫算法，實現(xiàn)最小生成樹的K

26、ruskal算法。提示：Kruskal算法實現(xiàn)的基本步驟：（1）需要對圖中所有的邊進行排序，因此需要借助一個輔助數(shù)組edge來存儲按權值由小到大排序的邊。包括邊的權值、邊的起點和終點。（2）每加入一條邊，需要判斷該邊的兩個頂點是否處在同一連通分量上，可以利用數(shù)組parents來表示各頂點的狀況，parentsi=i；初始值設置為各自的頂點值，表示各頂點自成一連通分量。當加入該邊，需要對該邊的邊頭頂點和邊尾頂點的parents值相等。5、編寫算法，實現(xiàn)圖的最短路徑Floyd算法。提示：弗洛伊德算法的基本步驟：對有向圖采用帶權鄰接矩陣存儲，同時定義一個二維數(shù)組ANN存放頂點i到j的最短路徑。（1）

27、初始化Aij=arcsij;（2）考慮vi和vj之間的路徑，是否存在途經(jīng)vk的路徑（vi,vk,vj),若存在，比較Aik+AKj和Aij的距離，較小送Aij； 重復上步，取vk為圖中所有頂點，直到比較完畢。同時還必須定義一個矩陣記錄最短路徑經(jīng)過的頂點。void Floyd()Int i,j,k; for(k=1;k=n;k+) for(i=1;i=n;i+) for(j=1;jDi,k+Dk,j) Di,j=Di,k+Dk,j;6、編寫算法，實現(xiàn)圖的關鍵路徑算法。提示：基于鄰接矩陣的關鍵路徑的求解步驟：(1)對AOE網(wǎng)進行拓撲排序，同時按拓撲序列的次序求出各頂點事件的最早發(fā)生時間ve，若網(wǎng)中存在回路，則算法終止，否則執(zhí)行步驟(2)；(2)按拓撲序列的逆序求出各頂點事件的最遲發(fā)生時間vl；(3)根據(jù)各頂點事件的ve和vl值，求出各頂點活動ai的最早發(fā)生時間e(i)和最遲發(fā)生時間l(i)。若e(i)l(i)，則ai為關鍵活動?！緦嶒炐〗Y】通過實驗七圖，我學會了的鄰接矩陣和鄰接表表示,學會了圖的深度優(yōu)先和廣度優(yōu)先搜索方法以及圖的最小生成樹Prim算法、圖的拓撲排序算法。16 / 16