大數(shù)據(jù)結(jié)構(gòu)圖

《大數(shù)據(jù)結(jié)構(gòu)圖》由會(huì)員分享，可在線閱讀，更多相關(guān)《大數(shù)據(jù)結(jié)構(gòu)圖（16頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、word 常熟理工學(xué)院 《數(shù)據(jù)結(jié)構(gòu)與算法》實(shí)驗(yàn)指導(dǎo)與報(bào)告書 _2017-2018_____學(xué)年 第__1__ 學(xué)期 專 業(yè)：物聯(lián)網(wǎng)工程 實(shí)驗(yàn)名稱： 實(shí)驗(yàn)七圖 實(shí)驗(yàn)地點(diǎn)： N6-210 指導(dǎo)教師： 聶盼紅 計(jì)算機(jī)科學(xué)與工程學(xué)院 2017 實(shí)驗(yàn)七圖 【實(shí)驗(yàn)?zāi)康摹? 1、掌握?qǐng)D的鄰接矩陣和鄰接表表示。 2、掌握?qǐng)D的深度優(yōu)先和廣度優(yōu)先搜索方法。 3、掌握?qǐng)D的最小生成樹Prim算法。 4、掌握?qǐng)D

2、的拓?fù)渑判蛩惴ā? 5、掌握?qǐng)D的單源最短路徑dijkstra算法。 【實(shí)驗(yàn)學(xué)時(shí)】 4-6學(xué)時(shí) 【實(shí)驗(yàn)預(yù)習(xí)】 回答以下問題： 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的拓?fù)湫蛄?，說明該有向圖是否有環(huán)？ 拓?fù)湫蛄?EABCD 該有向圖沒有環(huán) 5、根據(jù)圖7-3，寫出其最小生成樹。 圖7-3 無向帶權(quán)圖G3 6、根據(jù)圖7-4，求從頂點(diǎn)A到其他頂

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

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

5、度優(yōu)先搜索*/ void tdfs(MGraph *g); /*深度優(yōu)先搜索整個(gè)圖*/ void bfs(int k, MGraph *g); /*從第k個(gè)頂點(diǎn)廣度優(yōu)先搜索*/ void tbfs(MGraph *g); /*廣度優(yōu)先搜索整個(gè)圖*/ void init_visit(); /*初始化訪問標(biāo)識(shí)數(shù)組*/ void createGraph(MGraph *g) { /*建立一個(gè)無向圖的鄰接矩陣*/ int i=0,j,e=0; char v; g->vexnum=0;

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

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

8、搜索，補(bǔ)充完整算法*/ 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)先搜索整個(gè)圖*/ int i; printf("\n從頂點(diǎn)%C開始深

9、度優(yōu)先搜索序列：",g->vexs[0]); for (i=0;ivexnum;i++) if (visited[i]!=1) /*（4）---對(duì)尚未訪問過的頂點(diǎn)進(jìn)行深度優(yōu)先搜索*/ dfs(i,g); printf("\n"); }/*tdfs*/ void bfs(int k, MGraph *g) { /*從第k個(gè)頂點(diǎn)廣度優(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) { /*當(dāng)隊(duì)列不為空，進(jìn)行搜索*/ 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）---剛訪問過的結(jié)點(diǎn)入隊(duì)*/ q->rear=(q->rear+1)%MAX; /*（6）---修改隊(duì)尾指針*/ } } }/*bfs*/ void tbfs(MGraph *g) { /*廣度優(yōu)先搜索整個(gè)圖*/ int i; prin

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

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

14、 printf("\n3-圖的遍歷：\n"); init_visit(); /*初始化訪問數(shù)組*/ tdfs(&ga); /*深度優(yōu)先搜索圖*/ init_visit(); tbfs(&ga); /*廣度優(yōu)先搜索圖*/ return 0; } 2、 編寫程序exp7_2.c，實(shí)現(xiàn)圖的鄰接表存儲(chǔ)和拓?fù)渑判蛩惴ā? 以圖7-2的有向圖為例，補(bǔ)充完整程序，調(diào)試運(yùn)行并寫出運(yùn)行結(jié)果。 運(yùn)行結(jié)果：（包括輸入數(shù)據(jù)） exp7_2.c程序代碼參考如下： #include #include

15、 #define N 20 /*圖的鄰接表：鄰接鏈表結(jié)點(diǎn)*/ typedef struct EdgeNode{ int adjvex; /*頂點(diǎn)序號(hào)*/ struct EdgeNode *next; /*下一個(gè)結(jié)點(diǎn)的指針*/ } EdgeNode; /*圖的鄰接表：鄰接表*/ typedef struct VNode{ char data; /*頂點(diǎn)信息*/ int ind; /*頂點(diǎn)入度*/ struct EdgeNode *link; /*指向鄰

16、接鏈表指針*/ } VNode; typedef struct ALgraph{ /*圖的鄰接表*/ int vexnum,arum; /*頂點(diǎn)數(shù)、弧數(shù)*/ VNode adjlist[N]; }ALGraph; void createGraph_list(ALGraph *g); /*建立有向圖的鄰接表*/ void topSort(ALGraph *g); /*拓?fù)渑判?/ /*建立有向圖的鄰接表*/ void createGraph_list(ALGraph *g){ int i,j,e;

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

18、"\n請(qǐng)輸入弧的信息(頂點(diǎn)序號(hào),頂點(diǎn)序號(hào))，以(-1,-1)結(jié)束:\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、）頂點(diǎn)j的入度加1*/ e++; scanf("%d,%d",&i,&j); } g->arum=e; }/*createGraph_list*/ void topSort(ALGraph *g) { /*拓?fù)渑判?/ int i,j,k,top=0,m=0,s[N]; /*m為拓?fù)渑判蜉敵龅慕Y(jié)點(diǎn)數(shù)*/ EdgeNode *p; for(i=0; ivexnum; i++) if(!g->adjlist[i].ind) {

20、 /*（3）入度為0的頂點(diǎn)入棧*/ s[top++]=i; } printf("\n輸出拓?fù)湫蛄校?); 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--; /*頂點(diǎn)k入度減1*/ if(g->adjlist[k].ind==0) /*頂點(diǎn)k入度為0，進(jìn)棧*/ s[top++]=k; p=p->next; } } printf("\n共輸出%d個(gè)頂點(diǎn)\n",m); if(mvexnum) /*（4）當(dāng)輸出頂點(diǎn)數(shù)小于圖的頂點(diǎn)數(shù)，表示有環(huán)*/ printf("圖中有環(huán)！"); else

22、 printf("圖中無環(huán)！"); }/*topSort*/ int main(){ ALGraph g; int i; EdgeNode *s; printf("***********圖的鄰接表存儲(chǔ)結(jié)構(gòu)和拓?fù)渑判?**********\n"); printf("\n1-輸入圖的基本信息：\n"); createGraph_list(&g); /*創(chuàng)建圖的鄰接表存儲(chǔ)結(jié)構(gòu)*/ printf("\n2-圖的鄰接表:"); for(i=0; i

23、出圖的鄰接表存儲(chǔ)結(jié)構(gòu)*/ 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-根據(jù)圖的鄰接表實(shí)現(xiàn)拓?fù)渑判颍篭n"); topSort(&g); /*進(jìn)行拓?fù)渑判?

24、/ return 0; } （3）調(diào)試下面給出的圖的信息，寫出運(yùn)行結(jié)果，畫出該有向圖。 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，實(shí)現(xiàn)帶權(quán)圖的存儲(chǔ)、圖的最小生成樹及單源最短路徑算法。 以圖7-3（求該圖最小生成樹）和圖7-4（求該圖的單源最短路徑）為例，補(bǔ)充完整程序，調(diào)試運(yùn)行并寫出運(yùn)行結(jié)果。 運(yùn)行結(jié)果：（包括輸入數(shù)據(jù)） exp7_3.c程序代碼參考如下： #include #define N

25、20 #define TRUE 1 #define INF 10002766 /*鄰接矩陣中的無窮大元素*/ #define INFIN 10002767 /*比無窮大元素大的數(shù)*/ 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); /*建帶權(quán)圖的鄰接矩陣*/ void prim(MGraph *g, int u); /*求最小生成樹Prim算法，u為出發(fā)頂點(diǎn)*/ void dijkstra(MGraph g, int v); /*dijkstra算法求單源最短路徑*/ void createMGraph_w(MGraph *g, int flag){ /*建帶權(quán)圖的鄰接矩陣,若flag為1則為無向圖，flag為0為有向圖*/

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

28、g->arcs[i][j]=INF; printf("\n輸入邊的信息：(頂點(diǎn)，頂點(diǎn)，權(quán)值)，以(-1,-1,-1)結(jié)束\n"); scanf("%d,%d,%d",&i,&j,&w); /*讀入邊(i,j,w)*/ while(i!=-1){ /*讀入i為－1時(shí)結(jié)束*/ 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ā)頂點(diǎn)*/ int lowcost[N],closest[N],i,j,k,min; for(i=0; ivexnum; i++){ /*求其他頂點(diǎn)到出發(fā)頂點(diǎn)u的權(quán)*/ lowcost[i]=g->arcs[u][j];/*（1）-頂點(diǎn)i到u的代價(jià)最小的邊權(quán)值*/ closest[i]=u; } lowcost[u]=0; printf("\n最小生成樹：\n"); for(i=1;

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

31、exs[k],lowcost[k]); /*輸出該邊*/ lowcost[k]=0; /*頂點(diǎn)k納入最小生成樹 */ for(j=0; jvexnum; j++) /*求其他頂點(diǎn)到頂點(diǎn)k 的權(quán)*/ if(g->arcs[k][j]!=0&&g->arcs[k][j]arcs[k][j]; /*（3）-其他頂點(diǎn)到k的代價(jià)最小的邊權(quán)值*/ 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]; //輸出路徑頂點(diǎn)標(biāo)志 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路徑頂點(diǎn)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頂點(diǎn)%c->到各頂點(diǎn)的最短路徑\n",g.vexs[v]); for (i=0;i頂點(diǎn)%c：",g.vexs[v],g.vexs[i]); if (dist[i]==INF||dist[i]==0) printf("無路徑"); else { printf("%d ",dist[i]); printf

39、("經(jīng)過頂點(diǎn)："); 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、權(quán)圖的基本信息：\n"); createMGraph_w(&ga,1); prim(&ga,0); break; case 2: printf("\n2-圖的單源最短路徑-dijstra算法\n"); printf("\n輸入帶權(quán)圖的基本信息：\n"); createMGraph_w(&ga,0); dijkstra(ga,0);

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

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

44、 同時(shí)還必須定義一個(gè)矩陣記錄最短路徑經(jīng)過的頂點(diǎn)。 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、編寫算法，實(shí)現(xiàn)圖的關(guān)鍵路徑算法。 提示： 基于鄰接矩陣的關(guān)鍵路徑的求解步驟： (1)對(duì)AOE網(wǎng)進(jìn)行拓?fù)渑判?，同時(shí)按拓?fù)湫蛄械拇涡蚯蟪龈黜旤c(diǎn)事件的最早發(fā)生時(shí)間ve，若網(wǎng)中存在回路，則算法終止，否則執(zhí)行步驟(2)； (2)按拓?fù)湫蛄械哪嫘蚯蟪龈黜旤c(diǎn)事件的最遲發(fā)生時(shí)間vl； (3)根據(jù)各頂點(diǎn)事件的ve和vl值，求出各頂點(diǎn)活動(dòng)ai的最早發(fā)生時(shí)間e(i)和最遲發(fā)生時(shí)間l(i)。若e(i)＝l(i)，則ai為關(guān)鍵活動(dòng)。 【實(shí)驗(yàn)小結(jié)】 通過實(shí)驗(yàn)七——圖，我學(xué)會(huì)了的鄰接矩陣和鄰接表表示,學(xué)會(huì)了圖的深度優(yōu)先和廣度優(yōu)先搜索方法以及圖的最小生成樹Prim算法、圖的拓?fù)渑判蛩惴ā? 16 / 16