大數據結構圖

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

1、word 常熟理工學院 《數據結構與算法》實驗指導與報告書 _2017-2018_____學年 第__1__ 學期 專 業(yè)：物聯(lián)網工程 實驗名稱： 實驗七圖 實驗地點： N6-210 指導教師： 聶盼紅 計算機科學與工程學院 2017 實驗七圖 【實驗目的】 1、掌握圖的鄰接矩陣和鄰接表表示。 2、掌握圖的深度優(yōu)先和廣度優(yōu)先搜索方法。 3、掌握圖的最小生成樹Prim算法。 4、掌握圖

2、的拓撲排序算法。 5、掌握圖的單源最短路徑dijkstra算法。 【實驗學時】 4-6學時 【實驗預習】 回答以下問題： 1、寫出圖7-1無向圖的鄰接矩陣表示。 2、寫出圖7-2有向圖的鄰接表表示。 3、寫出圖7-1的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列。 深度優(yōu)先搜索序列：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、根據圖7-3，寫出其最小生成樹。 圖7-3 無向帶權圖G3 6、根據圖7-4，求從頂點A到其他頂

3、點的單源最短路徑。 X`圖7-4有向帶權圖G4 單源最短路徑：=10:AC=50:AED=30:AE=60:AEDF 【實驗容和要求】 1、 編寫程序exp7_1.c，實現圖的鄰接矩陣存儲及圖的深度優(yōu)先搜索和廣度優(yōu)先搜索。 以圖7-1的無向圖為例，補充完整程序，調試運行并寫出運行結果。 運行結果：（包括輸入數據） exp7_1.c參考程序如下： #include #define N 20 #define TRUE 1 #define FALSE 0 #define MAX 100 int vis

4、ited[N];/*訪問標志數組*/ typedef struct { /*輔助隊列的定義*/ int data[N]; int front,rear; }queue; typedef struct { /*圖的鄰接矩陣表示*/ int vexnum,arum; char vexs[N]; int arcs[N][N]; }MGraph; void createGraph(MGraph *g); /*建立一個無向圖的鄰接矩陣*/ void dfs(int i, MGraph *g); /*從第i個頂點出發(fā)深

5、度優(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(); /*初始化訪問標識數組*/ void createGraph(MGraph *g) { /*建立一個無向圖的鄰接矩陣*/ int i=0,j,e=0; char v; g->vexnum=0;

6、 g->arum=0; printf("\n輸入頂點序列(以#結束)：\n"); while ((v=getchar())!='#') { g->vexs[i]=v; /*讀入頂點信息*/ i++; } g->vexnum=i; /*頂點數目*/ for (i=0;ivexnum;i++) /*鄰接矩陣初始化*/ for (j=0;jvexnum;j++) g->arcs[i][j]=0;/*（1）-鄰接矩陣元素

7、初始化為0*/ printf("\n輸入邊的信息(頂點序號,頂點序號)，以(-1,-1)結束：\n"); scanf("%d,%d",&i,&j); /*讀入邊(i,j)*/ while (i!=-1) { /*讀入i為－1時結束*/ g->arcs[i][j]=1;/*（2）-i,j對應邊等于1*/ e++; scanf("%d,%d",&i,&j); } g->arum=e; /*邊數目*/ }/* createGraph */ /*（3）---從第i個頂點出發(fā)深度優(yōu)先

8、搜索，補充完整算法*/ void dfs(int i, MGraph *g) { int j; printf("%c",g->vexs[i]); visited[i]=1; for(j=0;jvexnum;j++) if((g->arcs[i][j]==1)&&(!visited[j])) dfs(j,g); } /* dfs */ void tdfs(MGraph *g) { /*深度優(yōu)先搜索整個圖*/ int i; printf("\n從頂點%C開始深

9、度優(yōu)先搜索序列：",g->vexs[0]); for (i=0;ivexnum;i++) if (visited[i]!=1) /*（4）---對尚未訪問過的頂點進行深度優(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;

10、 printf("%c",g->vexs[k]); visited[k]=TRUE; q->data[q->rear]=k; q->rear=(q->rear+1)%N; while (q->rear!=q->front) { /*當隊列不為空，進行搜索*/ i=q->data[q->front]; q->front=(q->front+1)%N; for (j=0;jvexnum;j++) if ((g->arcs[i][j]==1)&&(!visited[j]

11、)) { printf("%c",g->vexs[j]); visited[j]=TRUE; q->data[q->rear]=j; /*（5）---剛訪問過的結點入隊*/ q->rear=(q->rear+1)%MAX; /*（6）---修改隊尾指針*/ } } }/*bfs*/ void tbfs(MGraph *g) { /*廣度優(yōu)先搜索整個圖*/ int i; prin

12、tf("\n從頂點%C開始廣度優(yōu)先搜索序列：",g->vexs[0]); for (i=0;ivexnum;i++) if (visited[i]!=TRUE) bfs(i,g);/*從頂點i開始廣度優(yōu)先搜索*/ printf("\n"); }/*tbfs*/ void init_visit(){ /*初始化訪問標識數組*/ int i; for (i=0;i

13、; int i,j; printf("***********圖鄰接矩陣存儲和圖的遍歷***********\n"); printf("\n1-輸入圖的基本信息：\n"); createGraph(&ga); printf("\n2-無向圖的鄰接矩陣：\n"); for (i=0;i

14、 printf("\n3-圖的遍歷：\n"); init_visit(); /*初始化訪問數組*/ tdfs(&ga); /*深度優(yōu)先搜索圖*/ init_visit(); tbfs(&ga); /*廣度優(yōu)先搜索圖*/ return 0; } 2、 編寫程序exp7_2.c，實現圖的鄰接表存儲和拓撲排序算法。 以圖7-2的有向圖為例，補充完整程序，調試運行并寫出運行結果。 運行結果：（包括輸入數據） exp7_2.c程序代碼參考如下： #include #include

15、 #define N 20 /*圖的鄰接表：鄰接鏈表結點*/ typedef struct EdgeNode{ int adjvex; /*頂點序號*/ struct EdgeNode *next; /*下一個結點的指針*/ } EdgeNode; /*圖的鄰接表：鄰接表*/ typedef struct VNode{ char data; /*頂點信息*/ int ind; /*頂點入度*/ struct EdgeNode *link; /*指向鄰

16、接鏈表指針*/ } VNode; typedef struct ALgraph{ /*圖的鄰接表*/ int vexnum,arum; /*頂點數、弧數*/ VNode adjlist[N]; }ALGraph; void createGraph_list(ALGraph *g); /*建立有向圖的鄰接表*/ void topSort(ALGraph *g); /*拓撲排序*/ /*建立有向圖的鄰接表*/ void createGraph_list(ALGraph *g){ int i,j,e;

17、 char v; EdgeNode *s; i=0; e=0; printf("\n輸入頂點序列(以#結束)：\n"); while((v=getchar())!='#') { g->adjlist[i].data=v; /*讀入頂點信息*/ g->adjlist[i].link=NULL; g->adjlist[i].ind=0; i++; } g->vexnum=i; /*建立鄰接鏈表*/ printf(

18、"\n請輸入弧的信息(頂點序號,頂點序號)，以(-1,-1)結束:\n"); scanf("%d,%d",&i,&j); while(i!=-1) { s=(struct EdgeNode*)malloc(sizeof(EdgeNode)); s->adjvex=j; s->next=g->adjlist[i].link; ; /*（1）s插入鏈表*/ g->adjlist[i].link=s; g->adjlist[j].ind++; /*（2

19、）頂點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,s[N]; /*m為拓撲排序輸出的結點數*/ EdgeNode *p; for(i=0; ivexnum; i++) if(!g->adjlist[i].ind) {

20、 /*（3）入度為0的頂點入棧*/ s[top++]=i; } printf("\n輸出拓撲序列："); while(top>0) { j=s[--top]; printf("%c",g->adjlist[j].data); m++; p=g->adjlist[j].link; while(p!=NULL) { k=p->adjvex

21、; g->adjlist[k].ind--; /*頂點k入度減1*/ if(g->adjlist[k].ind==0) /*頂點k入度為0，進棧*/ s[top++]=k; p=p->next; } } printf("\n共輸出%d個頂點\n",m); if(mvexnum) /*（4）當輸出頂點數小于圖的頂點數，表示有環(huán)*/ printf("圖中有環(huán)！"); else

22、 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

23、出圖的鄰接表存儲結構*/ printf("\n%c,%d:",g.adjlist[i].data,g.adjlist[i].ind); s=g.adjlist[i].link; while(s!=NULL) { printf("->%d",s->adjvex); s=s->next; } } printf("\n"); printf("\n3-根據圖的鄰接表實現拓撲排序：\n"); topSort(&g); /*進行拓撲排序*

24、/ return 0; } （3）調試下面給出的圖的信息，寫出運行結果，畫出該有向圖。 ABCDEF# 1,0 1,3 2,1 2,5 3,2 3,4 3,5 4,0 5,0 5,1 5,4 -1,-1 3、編寫程序exp7_3.c，實現帶權圖的存儲、圖的最小生成樹及單源最短路徑算法。 以圖7-3（求該圖最小生成樹）和圖7-4（求該圖的單源最短路徑）為例，補充完整程序，調試運行并寫出運行結果。 運行結果：（包括輸入數據） exp7_3.c程序代碼參考如下： #include #define N

25、20 #define TRUE 1 #define INF 10002766 /*鄰接矩陣中的無窮大元素*/ #define INFIN 10002767 /*比無窮大元素大的數*/ typedef struct{/*圖的鄰接矩陣表示*/ int vexnum,arum; char vexs[N]; int arcs[N][N]; }MGraph; void printPath(MGraph g, int startVex, int EndVex, int path[][N

26、]); /*打印最短路徑*/ void createMGraph_w(MGraph *g, int flag); /*建帶權圖的鄰接矩陣*/ void prim(MGraph *g, int u); /*求最小生成樹Prim算法，u為出發(fā)頂點*/ void dijkstra(MGraph g, int v); /*dijkstra算法求單源最短路徑*/ void createMGraph_w(MGraph *g, int flag){ /*建帶權圖的鄰接矩陣,若flag為1則為無向圖，flag為0為有向圖*/

27、 int i,j,w; char v; g->vexnum=0; g->arum=0; i=0; printf("\n輸入頂點序列(以#結束)：\n"); while((v=getchar())!='#'){ g->vexs[i]=v; /*讀入頂點信息*/ i++; } g->vexnum=i; for(i=0; i<6; i++) /*鄰接矩陣初始化*/ for(j=0; j<6; j++)

28、g->arcs[i][j]=INF; printf("\n輸入邊的信息：(頂點，頂點，權值)，以(-1,-1,-1)結束\n"); scanf("%d,%d,%d",&i,&j,&w); /*讀入邊(i,j,w)*/ while(i!=-1){ /*讀入i為－1時結束*/ g->arcs[i][j]=w; if(flag==1) g->arcs[j][i]=w; scanf("%d,%d,%d",&i,&j,&w); } }/*createMGraph

29、_w*/ void prim(MGraph *g, int u){/*求最小生成樹Prim算法，u為出發(fā)頂點*/ int lowcost[N],closest[N],i,j,k,min; for(i=0; ivexnum; i++){ /*求其他頂點到出發(fā)頂點u的權*/ lowcost[i]=g->arcs[u][j];/*（1）-頂點i到u的代價最小的邊權值*/ closest[i]=u; } lowcost[u]=0; printf("\n最小生成樹：\n"); for(i=1;

30、ivexnum; i++){ /*循環(huán)求最小生成樹中的各條邊*/ min=INFIN; for(j=0; jvexnum; j++) /*選擇得到一條代價最小的邊*/ if(lowcost[j]!=0&&lowcost[j]vexs[closest[k]],g->v

31、exs[k],lowcost[k]); /*輸出該邊*/ lowcost[k]=0; /*頂點k納入最小生成樹 */ for(j=0; jvexnum; j++) /*求其他頂點到頂點k 的權*/ if(g->arcs[k][j]!=0&&g->arcs[k][j]arcs[k][j]; /*（3）-其他頂點到k的代價最小的邊權值*/ closest[j]=k; }

32、 } }/*prim*/ void printPath(MGraph g, int startVex, int EndVex, int path[][N]){ int stack[N],top=0; //堆棧 int i,k,j; int flag[N]; //輸出路徑頂點標志 k=EndVex; for (i=0;i

33、+]=k; while(top>0){ //找j到k的路徑 for (i=0;i %c(%d) ",g.vexs[i],g.arcs[j][i]); //輸出j到k路徑頂點i flag[i]=

34、1; j=i; k=stack[--top]; break; } else if (i!=k) stack[top++]=i; } } } if (flag[k]==0) printf("-> %c(%d)",g.vexs[k],g.arcs[j][k]); } void dijkstra(

35、MGraph g, int v){/*dijkstra算法求單源最短路徑*/ int s[N], path[N][N],dist[N]; int mindis,i,j,u,k; for(i=0; i

36、 path[i][i]=1; } } dist[v]=0; s[v]=1; for(i=0,u=1; i

37、 } s[u]=1; for(j=0; j

38、 } printf("\n頂點%c->到各頂點的最短路徑\n",g.vexs[v]); for (i=0;i頂點%c：",g.vexs[v],g.vexs[i]); if (dist[i]==INF||dist[i]==0) printf("無路徑"); else { printf("%d ",dist[i]); printf

39、("經過頂點："); 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");

40、 printf(" 0. EXIT"); printf("\n***************MENU******************\n"); printf("\ninput choice:"); scanf("%d",&select); getchar(); switch(select){ case 1: printf("\n1-圖的最小生成樹-Prim算法\n"); printf("\n輸入帶

41、權圖的基本信息：\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);

42、 break; default: break; } }while(select); return 0; } 【拓展實驗】 4、編寫算法，實現最小生成樹的Kruskal算法。 提示： Kruskal算法實現的基本步驟： （1）需要對圖中所有的邊進行排序，因此需要借助一個輔助數組edge來存儲按權值由小到大排序的邊。包括邊的權值、邊的起點和終點。 （2）每加入一條邊，需要判斷該邊的兩個頂點是否處在同一連通分量上，可以利用數組parents來表示各頂點的狀況，

43、parents[i]=i；初始值設置為各自的頂點值，表示各頂點自成一連通分量。當加入該邊，需要對該邊的邊頭頂點和邊尾頂點的parents值相等。 5、編寫算法，實現圖的最短路徑Floyd算法。 提示： 弗洛伊德算法的基本步驟：對有向圖采用帶權鄰接矩陣存儲，同時定義一個二維數組A[N][N]存放頂點i到j的最短路徑。 （1）初始化A[i][j]=arcs[i][j]; （2）考慮vi和vj之間的路徑，是否存在途經vk的路徑（vi,vk,vj),若存在，比較A[i][k]+A[K][j]和A[i][j]的距離，較小送A[i][j]； 重復上步，取vk為圖中所有頂點，直到比較完畢。

44、 同時還必須定義一個矩陣記錄最短路徑經過的頂點。 void Floyd() { Int i,j,k; for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(D[i,j]>D[i,k]+D[k,j]) D[i,j]=D[i,k]+D[k,j]; } 6、編寫算法，實現圖的關鍵路徑算法。 提示： 基于鄰接矩陣的關鍵路徑的求解步驟： (1)對AOE網進行拓撲排序，同時按拓撲序列的次序求出各頂點事件的最早發(fā)生時間ve，若網中存在回路，則算法終止，否則執(zhí)行步驟(2)； (2)按拓撲序列的逆序求出各頂點事件的最遲發(fā)生時間vl； (3)根據各頂點事件的ve和vl值，求出各頂點活動ai的最早發(fā)生時間e(i)和最遲發(fā)生時間l(i)。若e(i)＝l(i)，則ai為關鍵活動。 【實驗小結】 通過實驗七——圖，我學會了的鄰接矩陣和鄰接表表示,學會了圖的深度優(yōu)先和廣度優(yōu)先搜索方法以及圖的最小生成樹Prim算法、圖的拓撲排序算法。 16 / 16