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

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)康摹?、掌握圖的鄰接矩陣和鄰接表表示。2、掌握圖的深度優(yōu)先和廣度優(yōu)先搜索方法。3、掌握圖的最小生成樹Prim算法。4、掌握圖的拓?fù)渑判蛩惴ā?、掌握圖的單源最短路徑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ù)湫蛄校f明該有向圖是否有環(huán)？拓?fù)湫蛄?EABCD該有向圖沒有環(huán)5、根據(jù)圖7-3，寫出其最小生成樹。圖7-3 無向帶權(quán)圖G36、根據(jù)圖7-4，求從頂點(diǎn)A到其他頂點(diǎn)的單源最短路徑。X圖7-4有向帶權(quán)圖G4單源最短路徑：<A,C>=10:AC<A,D>=50:AED<A,E>=30:AE<A,F>=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<stdio.h>#define N 20#define TRUE 1#define FALSE 0#define MAX 100int visitedN;/*訪問標(biāo)志數(shù)組*/typedef struct /*輔助隊(duì)列的定義*/ int dataN; int front,rear;queue;typedef struct /*圖的鄰接矩陣表示*/ int vexnum,arum; char vexsN; int arcsNN;MGraph;void createGraph(MGraph *g); /*建立一個(gè)無向圖的鄰接矩陣*/void dfs(int i, MGraph *g); /*從第i個(gè)頂點(diǎn)出發(fā)深度優(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; g->arum=0; printf("n輸入頂點(diǎn)序列(以#結(jié)束)：n"); while (v=getchar()!='#') g->vexsi=v; /*讀入頂點(diǎn)信息*/ i+; g->vexnum=i; /*頂點(diǎn)數(shù)目*/ for (i=0;i<g->vexnum;i+) /*鄰接矩陣初始化*/ for (j=0;j<g->vexnum;j+) g->arcsij=0;/*（1）-鄰接矩陣元素初始化為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->arcsij=1;/*（2）-i,j對應(yīng)邊等于1*/ e+; scanf("%d,%d",&i,&j); g->arum=e; /*邊數(shù)目*/* createGraph */*（3）-從第i個(gè)頂點(diǎn)出發(fā)深度優(yōu)先搜索，補(bǔ)充完整算法*/void dfs(int i, MGraph *g) int j; printf("%c",g->vexsi); visitedi=1; for(j=0;j<g->vexnum;j+) if(g->arcsij=1)&&(!visitedj) dfs(j,g);/* dfs */void tdfs(MGraph *g) /*深度優(yōu)先搜索整個(gè)圖*/ int i; printf("n從頂點(diǎn)%C開始深度優(yōu)先搜索序列：",g->vexs0); for (i=0;i<g->vexnum;i+) if (visitedi!=1) /*（4）-對尚未訪問過的頂點(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; printf("%c",g->vexsk); visitedk=TRUE; q->dataq->rear=k; q->rear=(q->rear+1)%N; while (q->rear!=q->front) /*當(dāng)隊(duì)列不為空，進(jìn)行搜索*/ i=q->dataq->front; q->front=(q->front+1)%N; for (j=0;j<g->vexnum;j+) if (g->arcsij=1)&&(!visitedj) printf("%c",g->vexsj); visitedj=TRUE; q->dataq->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; printf("n從頂點(diǎn)%C開始廣度優(yōu)先搜索序列：",g->vexs0); for (i=0;i<g->vexnum;i+) if (visitedi!=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<N;i+) visitedi=FALSE;int main() MGraph ga; int i,j; printf("*圖鄰接矩陣存儲(chǔ)和圖的遍歷*n"); printf("n1-輸入圖的基本信息：n"); createGraph(&ga); printf("n2-無向圖的鄰接矩陣：n"); for (i=0;i<ga.vexnum;i+) for (j=0;j<ga.vexnum;j+) printf("%3d",ga.arcsij); printf("n"); 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<stdio.h>#include<malloc.h>#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; /*指向鄰接鏈表指針*/ VNode;typedef struct ALgraph /*圖的鄰接表*/ int vexnum,arum; /*頂點(diǎn)數(shù)、弧數(shù)*/ VNode adjlistN;ALGraph;void createGraph_list(ALGraph *g); /*建立有向圖的鄰接表*/void topSort(ALGraph *g); /*拓?fù)渑判?/*建立有向圖的鄰接表*/void createGraph_list(ALGraph *g) int i,j,e; char v; EdgeNode *s; i=0; e=0; printf("n輸入頂點(diǎn)序列(以#結(jié)束)：n"); while(v=getchar()!='#') g->adjlisti.data=v; /*讀入頂點(diǎn)信息*/ g->adjlisti.link=NULL; g->adjlisti.ind=0; i+; g->vexnum=i; /*建立鄰接鏈表*/ printf("n請輸入弧的信息(頂點(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->adjlisti.link; ; /*（1）s插入鏈表*/ g->adjlisti.link=s; g->adjlistj.ind+; /*（2）頂點(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,sN; /*m為拓?fù)渑判蜉敵龅慕Y(jié)點(diǎn)數(shù)*/ EdgeNode *p; for(i=0; i<g->vexnum; i+) if(!g->adjlisti.ind) /*（3）入度為0的頂點(diǎn)入棧*/ stop+=i; printf("n輸出拓?fù)湫蛄校?quot;); while(top>0) j=s-top; printf("%c",g->adjlistj.data); m+; p=g->adjlistj.link; while(p!=NULL) k=p->adjvex; g->adjlistk.ind-; /*頂點(diǎn)k入度減1*/ if(g->adjlistk.ind=0) /*頂點(diǎn)k入度為0，進(jìn)棧*/ stop+=k; p=p->next; printf("n共輸出%d個(gè)頂點(diǎn)n",m); if(m<g->vexnum) /*（4）當(dāng)輸出頂點(diǎn)數(shù)小于圖的頂點(diǎn)數(shù)，表示有環(huán)*/ printf("圖中有環(huán)！"); else 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<g.vexnum; i+) /*輸出圖的鄰接表存儲(chǔ)結(jié)構(gòu)*/ printf("n%c,%d:",g.adjlisti.data,g.adjlisti.ind); s=g.adjlisti.link; while(s!=NULL) printf("->%d",s->adjvex); s=s->next; printf("n"); printf("n3-根據(jù)圖的鄰接表實(shí)現(xiàn)拓?fù)渑判颍簄"); topSort(&g); /*進(jìn)行拓?fù)渑判?/ return 0;（3）調(diào)試下面給出的圖的信息，寫出運(yùn)行結(jié)果，畫出該有向圖。ABCDEF#1,01,32,12,53,23,43,54,05,05,15,4-1,-13、編寫程序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 <stdio.h>#define N 20#define TRUE 1#define INF 10002766 /*鄰接矩陣中的無窮大元素*/#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); /*建帶權(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為有向圖*/ int i,j,w; char v; g->vexnum=0; g->arum=0; i=0; printf("n輸入頂點(diǎn)序列(以#結(jié)束)：n"); while(v=getchar()!='#') g->vexsi=v; /*讀入頂點(diǎn)信息*/ i+; g->vexnum=i; for(i=0; i<6; i+) /*鄰接矩陣初始化*/ for(j=0; j<6; j+) g->arcsij=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->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ā)頂點(diǎn)*/ int lowcostN,closestN,i,j,k,min; for(i=0; i<g->vexnum; i+) /*求其他頂點(diǎn)到出發(fā)頂點(diǎn)u的權(quán)*/ lowcosti=g->arcsuj;/*（1）-頂點(diǎn)i到u的代價(jià)最小的邊權(quán)值*/ closesti=u; lowcostu=0; printf("n最小生成樹：n"); for(i=1; i<g->vexnum; i+) /*循環(huán)求最小生成樹中的各條邊*/ min=INFIN; for(j=0; j<g->vexnum; j+) /*選擇得到一條代價(jià)最小的邊*/ if(lowcostj!=0&&lowcostj<min) min=lowcostj;/*（2）-修改當(dāng)前最小邊*/ k=j; printf("(%c,%c)-%dn",g->vexsclosestk,g->vexsk,lowcostk); /*輸出該邊*/ lowcostk=0; /*頂點(diǎn)k納入最小生成樹 */ for(j=0; j<g->vexnum; j+) /*求其他頂點(diǎn)到頂點(diǎn)k 的權(quán)*/ if(g->arcskj!=0&&g->arcskj<lowcostj) lowcostj=g->arcskj; /*（3）-其他頂點(diǎn)到k的代價(jià)最小的邊權(quán)值*/ closestj=k; /*prim*/void printPath(MGraph g, int startVex, int EndVex, int pathN) int stackN,top=0; /堆棧 int i,k,j; int flagN; /輸出路徑頂點(diǎn)標(biāo)志 k=EndVex; for (i=0;i<g.vexnum;i+) flagi=0; j=startVex; printf("%c",g.vexsj); flagj=1; stacktop+=k; while(top>0) /找j到k的路徑 for (i=0;i<g.vexnum;i+) if (pathki=1 && flagi=0 ) /j到k的路徑含有i頂點(diǎn) if (g.arcsji!=INF ) /j到i的路徑含有中間頂點(diǎn) printf("-> %c(%d) ",g.vexsi,g.arcsji); /輸出j到k路徑頂點(diǎn)i flagi=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; i<g.vexnum; i+) disti=g.arcsvi; si=0; for(j=0; j<g.vexnum; j+) pathij=0; if(disti<INF) pathiv=1; pathii=1; distv=0; sv=1; for(i=0,u=1; i<g.vexnum; i+) mindis=INFIN; for(j=0; j<g.vexnum; j+) if(sj=0) if(distj<mindis) u=j; mindis=distj; su=1; for(j=0; j<g.vexnum; j+) if(sj=0)&&distu+g.arcsuj<distj) distj=distu+g.arcsuj; for(k=0; k<g.vexnum; k+) pathjk=pathuk; pathjj=1; printf("n頂點(diǎn)%c->到各頂點(diǎn)的最短路徑n",g.vexsv); for (i=0;i<g.vexnum;i+) if(i=v)continue; printf("n頂點(diǎn)%c->頂點(diǎn)%c：",g.vexsv,g.vexsi); if (disti=INF|disti=0) printf("無路徑"); else printf("%d ",disti); printf("經(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"); printf(" 0. EXIT"); printf("n*MENU*n"); printf("ninput choice:"); scanf("%d",&select); getchar(); switch(select) case 1: printf("n1-圖的最小生成樹-Prim算法n"); printf("n輸入帶權(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); break; default: break; while(select); return 0;【拓展實(shí)驗(yàn)】4、編寫算法，實(shí)現(xiàn)最小生成樹的Kruskal算法。提示：Kruskal算法實(shí)現(xiàn)的基本步驟：（1）需要對圖中所有的邊進(jìn)行排序，因此需要借助一個(gè)輔助數(shù)組edge來存儲(chǔ)按權(quán)值由小到大排序的邊。包括邊的權(quán)值、邊的起點(diǎn)和終點(diǎn)。（2）每加入一條邊，需要判斷該邊的兩個(gè)頂點(diǎn)是否處在同一連通分量上，可以利用數(shù)組parents來表示各頂點(diǎn)的狀況，parentsi=i；初始值設(shè)置為各自的頂點(diǎn)值，表示各頂點(diǎn)自成一連通分量。當(dāng)加入該邊，需要對該邊的邊頭頂點(diǎn)和邊尾頂點(diǎn)的parents值相等。5、編寫算法，實(shí)現(xiàn)圖的最短路徑Floyd算法。提示：弗洛伊德算法的基本步驟：對有向圖采用帶權(quán)鄰接矩陣存儲(chǔ)，同時(shí)定義一個(gè)二維數(shù)組ANN存放頂點(diǎn)i到j(luò)的最短路徑。（1）初始化Aij=arcsij;（2）考慮vi和vj之間的路徑，是否存在途經(jīng)vk的路徑（vi,vk,vj),若存在，比較Aik+AKj和Aij的距離，較小送Aij； 重復(fù)上步，取vk為圖中所有頂點(diǎn)，直到比較完畢。同時(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(Di,j>Di,k+Dk,j) Di,j=Di,k+Dk,j;6、編寫算法，實(shí)現(xiàn)圖的關(guān)鍵路徑算法。提示：基于鄰接矩陣的關(guān)鍵路徑的求解步驟：(1)對AOE網(wǎng)進(jìn)行拓?fù)渑判颍瑫r(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ù)渑判蛩惴ā?6 / 16