1、浙江大學(xué)城市學(xué)院實(shí)驗(yàn)報(bào)告課程名稱 數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)項(xiàng)目名稱 實(shí)驗(yàn)六 圖的基本操作與應(yīng)用 實(shí)驗(yàn)成績(jī) 指導(dǎo)老師（簽名 ） 日期 一. 實(shí)驗(yàn)?zāi)康暮鸵?、 掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu)：鄰接矩陣、鄰接表。2、 掌握?qǐng)D的深度優(yōu)先與廣度優(yōu)先兩個(gè)搜素算法。3、學(xué)會(huì)對(duì)圖的存儲(chǔ)結(jié)構(gòu)進(jìn)行基本操作。4、加強(qiáng)綜合程序的分析、設(shè)計(jì)能力。二. 實(shí)驗(yàn)內(nèi)容1、 現(xiàn)有14個(gè)人（分別用字母A、B、. N表示），他們相互之間的朋友關(guān)系如圖所示（有線相連表示是朋友關(guān)系），請(qǐng)分別用鄰接矩陣與鄰接表表示該關(guān)系圖，并完成以下功能。 以鄰接矩陣表示，在此結(jié)構(gòu)上完成：l 創(chuàng)建此圖；l 輸出此圖的鄰接矩陣；l 輸出從A出發(fā)的深度優(yōu)先搜索序列；l 輸出從A出

2、發(fā)的廣度優(yōu)先搜索序列；l 輸入兩個(gè)人p1、p2，判斷此兩人是否為朋友關(guān)系，若不是，給出一種從p1能找到p2的路徑；（如輸入p1=A、p2=N，則A與N不是直接朋友關(guān)系，但可以（不唯一）通過(guò)A-B-F-K-N方式聯(lián)系到N。） 以鄰接表表示，在此結(jié)構(gòu)上完成：l 創(chuàng)建此圖；l 輸出此圖的鄰接表；l 輸出從A出發(fā)的深度優(yōu)先搜索序列；l 輸出從A出發(fā)的廣度優(yōu)先搜索序列；l 輸入兩個(gè)人p1、p2，判斷此兩人是否為朋友關(guān)系，若不是，給出一種從p1能找到p2的路徑；（如輸入p1=A、p2=N，則A與N不是直接朋友關(guān)系，但可以（不唯一）通過(guò)A-B-F-K-N方式聯(lián)系到N。） 建立頭文件AdjMatrix.h和A

3、djLink.h，分別包含鄰接矩陣結(jié)構(gòu)和鄰接表結(jié)構(gòu)的操作實(shí)現(xiàn)函數(shù)，建立主程序文件test6.cpp，在主函數(shù)中通過(guò)調(diào)用來(lái)實(shí)現(xiàn)上述功能。 自行增加合適的功能，可作為額外的實(shí)驗(yàn)成績(jī)進(jìn)行加分（例如考慮添加或刪除一對(duì)朋友關(guān)系；找出朋友最多的那個(gè)人；上面找到A到N的聯(lián)系路徑，若要求找到一條最短的路線怎么找等等）。2、以小組為單位認(rèn)真填寫(xiě)實(shí)驗(yàn)報(bào)告，實(shí)驗(yàn)報(bào)告必須包括各類數(shù)據(jù)類型的結(jié)構(gòu)定義說(shuō)明，各類數(shù)據(jù)的組織方式，系統(tǒng)的功能結(jié)構(gòu)，各個(gè)操作的定義以及實(shí)現(xiàn)方法，運(yùn)行結(jié)果與分析，難點(diǎn)如何解決，存在問(wèn)題以及可改進(jìn)之處等。同時(shí)，在實(shí)驗(yàn)報(bào)告中需寫(xiě)明小組每位同學(xué)的分工，得分（小組總分不超過(guò)12分）等。實(shí)驗(yàn)報(bào)告文件取名為re

4、port6.doc。每組還必須制作一個(gè)答辯PPT以備答辯。3、由組長(zhǎng)上傳實(shí)驗(yàn)報(bào)告文件report6.doc 、源程序文件test6.cpp及AdjMatrix.h和AdjLink.h到BB平臺(tái)上。功能模塊圖：主菜單創(chuàng)建此圖輸出此圖的鄰接表或鄰接矩陣查找朋友最多的人判斷兩人是否為朋友輸出從A出發(fā)的廣度優(yōu)先搜索序列輸出從A出發(fā)的深度優(yōu)先搜索序列鄰接表鄰接矩陣函數(shù)調(diào)用結(jié)構(gòu)圖：mainInitMGraphShowMGraphmenuInitALGraphFindALGraphDFSTraverseMGraphShowALGraphBFSTraverseMGraphDFSTraverseALGraphF

5、indMGraphJudgeALGraphJudgeMGraphBFSTraverseALGraph左側(cè)為鄰接矩陣的相關(guān)函數(shù)，右側(cè)為鄰接表的相關(guān)函數(shù)結(jié)構(gòu)體定義typedef struct MGraphstatus vexsMAXMAX; int arcsMAXMAXMAXMAX;int vernum,arcnum;MGraph; /鄰接矩陣 /鄰接表 typedef struct ArcNodeint adjvex; /下標(biāo) struct ArcNode *nextarc;ArcNode;typedef struct VNodestatus data;ArcNode *firstarc; VN

6、ode,AdjListMAXMAX;typedef structAdjList vertices;int vexnum,arcnum;ALGraph; /隊(duì)列 typedef structint *data;int rear;int front;sqQueue; 實(shí)現(xiàn)思路深度優(yōu)先搜索序列利用一個(gè)數(shù)組來(lái)記錄頂點(diǎn)是否被訪問(wèn)，對(duì)未訪問(wèn)的鄰接頂點(diǎn)進(jìn)行遞歸，直至所有頂點(diǎn)均被訪問(wèn)。廣度優(yōu)先搜索序列利用一個(gè)數(shù)組來(lái)記錄頂點(diǎn)是否被訪問(wèn)，未被訪問(wèn)的頂點(diǎn)及其鄰接點(diǎn)進(jìn)隊(duì)列，并且“先被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)”被訪問(wèn)，直至所有頂點(diǎn)均被訪問(wèn)，訪問(wèn)完后出隊(duì)列至隊(duì)空。運(yùn)行結(jié)果與分析輸入數(shù)字，進(jìn)行對(duì)應(yīng)的

7、操作輸入1創(chuàng)建此圖，輸入1或2建立鄰接矩陣或鄰接表可改進(jìn)之處可以增加查找兩人的最短路徑；可以增加對(duì)錯(cuò)誤信息的處理；源代碼test6.cpp#include#include#include#include #include #define OK 1#define FALSE 0#define TRUE 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2 #define MAXMAX 100int MAX=14; typedef structchar name;status; typedef struct MGraphstatus ve

8、xsMAXMAX; int arcsMAXMAXMAXMAX;int vernum,arcnum;MGraph; /鄰接矩陣 /鄰接表 typedef struct ArcNodeint adjvex; /下標(biāo) struct ArcNode *nextarc;ArcNode;typedef struct VNodestatus data;ArcNode *firstarc; VNode,AdjListMAXMAX;typedef structAdjList vertices;int vexnum,arcnum;ALGraph; /隊(duì)列 typedef structint *data;int r

9、ear;int front;sqQueue; int visitMAXMAX; /訪問(wèn)標(biāo)志數(shù)組 int v;#includeQueue.h#includeAdjMatrix.h#includeAdjLink.hvoid menu()printf(1.創(chuàng)建此圖n);printf(2.輸出此圖的鄰接表或鄰接矩陣n);printf(3.輸出從A出發(fā)的深度優(yōu)先搜索序列n); printf(4.輸出從A出發(fā)的廣度優(yōu)先搜索序列n);printf(5.輸入兩個(gè)人p1、p2，判斷此兩人是否為朋友關(guān)系，若不是，給出一種從p1能找到p2的路徑n);printf(6.查找朋友最多的那個(gè)人n);printf(0.退出

10、n);printf(輸入您想進(jìn)行的操作n); int main()MGraph M;ALGraph A;int n,a;menu();while(1)scanf(%d,&n);getchar();if(n=1)system(CLS);MAX=14;printf(輸入1建立鄰接矩陣；輸入2建立鄰接表n);scanf(%d,&a);getchar();if(a=1)InitMGraph(M);if(a=2)InitALGraph(A);printf(輸入9返回，輸入0退出n); if(n=2)system(CLS);if(a=1)ShowMGraph(M);if(a=2)ShowALGraph(A

11、);printf(輸入9返回，輸入0退出n);if(n=3)system(CLS);if(a=1)v=0;DFSTraverseMGraph(M,v);if(a=2)v=0;DFSTraverseALGraph(A,v);printf(輸入9返回，輸入0退出n);if(n=4)system(CLS);if(a=1)BFSTraverseMGraph(M,v);if(a=2)BFSTraverseALGraph(A,v);printf(輸入9返回，輸入0退出n);if(n=5)system(CLS);if(a=1)JudgeMGraph(M,v);if(a=2)JudgeALGraph(A,v)

12、;printf(輸入9返回，輸入0退出n);if(n=6)system(CLS);if(a=1)FindMGraph(M);if(a=2)FindALGraph(A);printf(輸入9返回，輸入0退出n);if(n=9)system(CLS);menu();if(n=0)break;Queue.hint InitQueue(sqQueue &L) /創(chuàng)建隊(duì)列 L.data=(int *)malloc(MAXMAX*sizeof(int);L.rear=0;L.front=0;int EnQueue(sqQueue &L,int v) /進(jìn)隊(duì)列 L.dataL.rear=v;L.rear=(

13、L.rear+1)%MAXMAX;int DeQueue(sqQueue &L,int &u) /出隊(duì)列 u=L.dataL.front;L.front=(L.front+1)%MAXMAX;int QueueEmpty(sqQueue &L)if(L.front=L.rear)return 1;return 0;AdjMatrix.hint InitMGraph(MGraph &M)/創(chuàng)建此圖 int i,j; M.=A;M.=B;M.=C;M.=D;M.=E;M.=F;M

14、.=G;M.=H;M.=I;M.=J;M.=K;M.=L;M.=M;M.=N;for(i=0;iMAX;i+)for(j=0;jMAX;j+)M.arcsij=0; /將鄰接矩陣清空 M.arcs01=1;M.arcs02=1;M.arcs10=1;M.arcs15=1;M.arcs20=1;M.arcs27=1;M.arcs34=1;M.arcs35=1;M.arcs43=1;M.arcs48=1;M.arcs47=1;M.a

15、rcs51=1;M.arcs56=1;M.arcs510=1;M.arcs59=1;M.arcs53=1;M.arcs65=1;M.arcs72=1;M.arcs74=1;M.arcs711=1;M.arcs712=1;M.arcs84=1;M.arcs89=1;M.arcs812=1;M.arcs95=1;M.arcs910=1;M.arcs98=1;M.arcs105=1;M.arcs1013=1;M.arcs109=1;M.arcs117=1;M.arcs128=1;M.arcs1213=1;M.arcs127=1;M.arcs1310=1;M.arcs1312=1;M.arcnum=1

16、8;M.vernum=14; int ShowMGraph(MGraph &M)/輸出此圖的鄰接矩陣 int i,j;for(i=0;iMAX;i+)for(j=0;jMAX;j+)printf(%d ,M.arcsij);printf(n);int DFSMGraph(MGraph &M,int v) /深度優(yōu)先int i;visitv=TRUE;printf(姓名:%c n,M.);for(i=0;iMAX;i+) /遍歷當(dāng)前頂點(diǎn)的各個(gè)直接后繼 if(!visitv)&(M.arcsvi=1)DFSMGraph(M,i); /對(duì)未訪問(wèn)過(guò)的且是鄰接的點(diǎn)i進(jìn)行遞歸 int

17、DFSTraverseMGraph(MGraph &M,int v) /深度優(yōu)先 for(v=0;vMAX;v+)visitv=FALSE; /對(duì)訪問(wèn)標(biāo)志數(shù)組初始化 for(v=0;vMAX;v+) if(!visitv) DFSMGraph(M,v);int BFSTraverseMGraph(MGraph &M,int v) /廣度優(yōu)先算法sqQueue L;int i,u,j;for(v=0;vMAX;v+)visitv=FALSE;InitQueue(L);for(v=0;vMAX;v+) if(!visitv)visitv=TRUE; printf(姓名：%c n,M.vexsv.n

18、ame);EnQueue(L,v); while(!QueueEmpty(L)DeQueue(L,u);for(i=0;iMAX;i+)if(M.arcsui=1)if(visiti=0) visiti=TRUE;printf(姓名：%c n,M.);EnQueue(L,i); /將u的各個(gè)后繼依次進(jìn)隊(duì)列 int JudgeDFS(MGraph &M,int &v,int *c,int b,int &o)/判斷是否為朋友的函數(shù)中要用到的深度優(yōu)先算法int n,i,j;visitv=TRUE;co=v; /用co來(lái)保存路徑 o+;if(v=b) /當(dāng)聯(lián)通時(shí)，輸出路徑 for(

19、j=0;j,M.);for(i=0;iMAX;i+)if(visiti=FALSE) if(M.arcsvi=1)v=i; JudgeDFS(M,v,c,b,o); o-; /消除無(wú)法連通的路徑co=0; v=co-1; int JudgeMGraph(MGraph &M,int v)/判斷是否為朋友 char n,p1,p2;int a,b,o=0,i;int cMAX;printf(請(qǐng)輸入兩個(gè)人的名字n);scanf(%c %c,&p1,&p2);for(i=0;iMAX;i+)if(M.=p1)a=i;if(M.=p2)b=i

20、; /得出下標(biāo) if(M.arcsab=1)printf(他們是朋友n);return 0; printf(他們不是朋友，以下是連通兩人的路徑n);for(v=0;vMAX;v+)visitv=FALSE;v=a;JudgeDFS(M,v,c,b,o); /深度優(yōu)先算法 int FindMGraph(MGraph &M) /尋找朋友最多的人 int countMAX,i,j,max;for(i=0;iMAX;i+)counti=0; /將計(jì)數(shù)歸零 for(i=0;iMAX;i+)for(j=0;jMAX;j+)if(M.arcsij=1)counti+; /用count計(jì)數(shù)，來(lái)計(jì)算每個(gè)人的朋友

21、個(gè)數(shù) max=count0;for(i=0;imax)max=counti;printf(朋友最多的人是);for(i=0;iadjvex=1;A.vertices0.firstarc-nextarc=(ArcNode *)malloc(sizeof(ArcNode);A.vertices0.firstarc-nextarc-adjvex=2;A.vertices0.firstarc-nextarc-nextarc=NULL; A.vertices1.firstarc=(ArcNode *)malloc(sizeof(ArcNode);A.vertices1.firstarc-adjvex=0

22、;A.vertices1.firstarc-nextarc= (ArcNode *)malloc(sizeof(ArcNode);A.vertices1.firstarc-nextarc-adjvex=5;A.vertices1.firstarc-nextarc-nextarc=NULL;A.vertices2.firstarc=(ArcNode *)malloc(sizeof(ArcNode);A.vertices2.firstarc-adjvex=0;A.vertices2.firstarc-nextarc= (ArcNode *)malloc(sizeof(ArcNode);A.vert

23、ices2.firstarc-nextarc-adjvex=7;A.vertices2.firstarc-nextarc-nextarc=NULL;A.vertices3.firstarc=(ArcNode *)malloc(sizeof(ArcNode);A.vertices3.firstarc-adjvex=4;A.vertices3.firstarc-nextarc= (ArcNode *)malloc(sizeof(ArcNode);A.vertices3.firstarc-nextarc-adjvex=5;A.vertices3.firstarc-nextarc-nextarc=NU

24、LL;A.vertices4.firstarc=(ArcNode *)malloc(sizeof(ArcNode);A.vertices4.firstarc-adjvex=3;A.vertices4.firstarc-nextarc= (ArcNode *)malloc(sizeof(ArcNode);A.vertices4.firstarc-nextarc-adjvex=8; A.vertices4.firstarc-nextarc-nextarc= (ArcNode *)malloc(sizeof(ArcNode);A.vertices4.firstarc-nextarc-nextarc-

25、adjvex=7;A.vertices4.firstarc-nextarc-nextarc-nextarc=NULL;A.vertices5.firstarc=(ArcNode *)malloc(sizeof(ArcNode);A.vertices5.firstarc-adjvex=1;A.vertices5.firstarc-nextarc=(ArcNode *)malloc(sizeof(ArcNode);A.vertices5.firstarc-nextarc-adjvex=6; A.vertices5.firstarc-nextarc-nextarc=(ArcNode *)malloc

26、(sizeof(ArcNode);A.vertices5.firstarc-nextarc-nextarc-adjvex=10;A.vertices5.firstarc-nextarc-nextarc-nextarc=(ArcNode *)malloc(sizeof(ArcNode);A.vertices5.firstarc-nextarc-nextarc-nextarc-adjvex=9;A.vertices5.firstarc-nextarc-nextarc-nextarc-nextarc=(ArcNode *)malloc(sizeof(ArcNode);A.vertices5.firs

27、tarc-nextarc-nextarc-nextarc-nextarc-adjvex=3;A.vertices5.firstarc-nextarc-nextarc-nextarc-nextarc-nextarc=NULL;A.vertices6.firstarc=(ArcNode *)malloc(sizeof(ArcNode);A.vertices6.firstarc-adjvex=5;A.vertices6.firstarc-nextarc=NULL;A.vertices7.firstarc=(ArcNode *)malloc(sizeof(ArcNode);A.vertices7.fi

28、rstarc-adjvex=2;A.vertices7.firstarc-nextarc=(ArcNode *)malloc(sizeof(ArcNode);A.vertices7.firstarc-nextarc-adjvex=4; A.vertices7.firstarc-nextarc-nextarc=(ArcNode *)malloc(sizeof(ArcNode);A.vertices7.firstarc-nextarc-nextarc-adjvex=11;A.vertices7.firstarc-nextarc-nextarc-nextarc=(ArcNode *)malloc(s

29、izeof(ArcNode);A.vertices7.firstarc-nextarc-nextarc-nextarc-adjvex=12;A.vertices7.firstarc-nextarc-nextarc-nextarc-nextarc=(ArcNode *)malloc(sizeof(ArcNode);A.vertices7.firstarc-nextarc-nextarc-nextarc-nextarc=NULL;A.vertices8.firstarc=(ArcNode *)malloc(sizeof(ArcNode);A.vertices8.firstarc-adjvex=4;

30、A.vertices8.firstarc-nextarc= (ArcNode *)malloc(sizeof(ArcNode);A.vertices8.firstarc-nextarc-adjvex=9;A.vertices8.firstarc-nextarc-nextarc= (ArcNode *)malloc(sizeof(ArcNode);A.vertices8.firstarc-nextarc-nextarc-adjvex=12;A.vertices8.firstarc-nextarc-nextarc-nextarc=NULL;A.vertices9.firstarc=(ArcNode

31、 *)malloc(sizeof(ArcNode);A.vertices9.firstarc-adjvex=5;A.vertices9.firstarc-nextarc= (ArcNode *)malloc(sizeof(ArcNode);A.vertices9.firstarc-nextarc-adjvex=10;A.vertices9.firstarc-nextarc-nextarc= (ArcNode *)malloc(sizeof(ArcNode);A.vertices9.firstarc-nextarc-nextarc-adjvex=8;A.vertices9.firstarc-ne

32、xtarc-nextarc-nextarc=NULL;A.vertices10.firstarc=(ArcNode *)malloc(sizeof(ArcNode);A.vertices10.firstarc-adjvex=5;A.vertices10.firstarc-nextarc= (ArcNode *)malloc(sizeof(ArcNode);A.vertices10.firstarc-nextarc-adjvex=13;A.vertices10.firstarc-nextarc-nextarc= (ArcNode *)malloc(sizeof(ArcNode);A.vertic

33、es10.firstarc-nextarc-nextarc-adjvex=9;A.vertices10.firstarc-nextarc-nextarc-nextarc=NULL;A.vertices11.firstarc= (ArcNode *)malloc(sizeof(ArcNode);A.vertices11.firstarc-adjvex=7;A.vertices11.firstarc-nextarc=NULL;A.vertices12.firstarc=(ArcNode *)malloc(sizeof(ArcNode);A.vertices12.firstarc-adjvex=8;

34、A.vertices12.firstarc-nextarc= (ArcNode *)malloc(sizeof(ArcNode);A.vertices12.firstarc-nextarc-adjvex=13;A.vertices12.firstarc-nextarc-nextarc= (ArcNode *)malloc(sizeof(ArcNode);A.vertices12.firstarc-nextarc-nextarc-adjvex=7;A.vertices12.firstarc-nextarc-nextarc-nextarc=NULL;A.vertices13.firstarc=(A

35、rcNode *)malloc(sizeof(ArcNode);A.vertices13.firstarc-adjvex=10;A.vertices13.firstarc-nextarc= (ArcNode *)malloc(sizeof(ArcNode);A.vertices13.firstarc-nextarc-adjvex=12;A.vertices13.firstarc-nextarc-nextarc=NULL;A.vexnum=14;A.arcnum=35; int ShowALGraph(ALGraph A)/輸出此圖的鄰接表 int i;ArcNode *p;p=(ArcNode

36、 *)malloc(sizeof(ArcNode);for(i=0;i%d,p-adjvex);p=p-nextarc;printf(n);int DFSALGraph(ALGraph &A,int &v)/深度優(yōu)先ArcNode *p;p=(ArcNode *)malloc(sizeof(ArcNode);p=A.verticesv.firstarc;visitv=TRUE;printf(姓名:%c n,A.);while(p)if(visitp-adjvex!=TRUE) /如果這個(gè)下標(biāo)沒(méi)被訪問(wèn)過(guò)，進(jìn)行遞歸，否則繼續(xù)遍歷這個(gè)鏈表 v=p-adjvex;DFSALGraph(A,v);p=p-nextarc; int DFSTraverseALGraph(ALGraph &A,int &v) /深度優(yōu)先 for(v=0;vMAX;v+)visitv=FALSE;for(v=0;vMAX;v+)if(visitv=FALSE)DFSALGraph(A,v); int BFSTraverseALGraph(ALGraph &A,int &v)sqQueue L;int i,u