图的基本操作与应用

1、浙江大学城市学院实验报告课程名称 数据结构 实验项目名称 实验六 图的基本操作与应用 实验成绩 指导老师（签名 ） 日期 一. 实验目的和要求1、 掌握图的存储结构：邻接矩阵、邻接表。2、 掌握图的深度优先与广度优先两个搜素算法。3、学会对图的存储结构进行基本操作。4、加强综合程序的分析、设计能力。二. 实验内容1、 现有14个人（分别用字母A、B、. N表示），他们相互之间的朋友关系如图所示（有线相连表示是朋友关系），请分别用邻接矩阵与邻接表表示该关系图，并完成以下功能。 以邻接矩阵表示，在此结构上完成：l 创建此图；l 输出此图的邻接矩阵；l 输出从A出发的深度优先搜索序列；l 输出从A出

2、发的广度优先搜索序列；l 输入两个人p1、p2，判断此两人是否为朋友关系，若不是，给出一种从p1能找到p2的路径；（如输入p1=A、p2=N，则A与N不是直接朋友关系，但可以（不唯一）通过A-B-F-K-N方式联系到N。） 以邻接表表示，在此结构上完成：l 创建此图；l 输出此图的邻接表；l 输出从A出发的深度优先搜索序列；l 输出从A出发的广度优先搜索序列；l 输入两个人p1、p2，判断此两人是否为朋友关系，若不是，给出一种从p1能找到p2的路径；（如输入p1=A、p2=N，则A与N不是直接朋友关系，但可以（不唯一）通过A-B-F-K-N方式联系到N。） 建立头文件AdjMatrix.h和A

3、djLink.h，分别包含邻接矩阵结构和邻接表结构的操作实现函数，建立主程序文件test6.cpp，在主函数中通过调用来实现上述功能。 自行增加合适的功能，可作为额外的实验成绩进行加分（例如考虑添加或删除一对朋友关系；找出朋友最多的那个人；上面找到A到N的联系路径，若要求找到一条最短的路线怎么找等等）。2、以小组为单位认真填写实验报告，实验报告必须包括各类数据类型的结构定义说明，各类数据的组织方式，系统的功能结构，各个操作的定义以及实现方法，运行结果与分析，难点如何解决，存在问题以及可改进之处等。同时，在实验报告中需写明小组每位同学的分工，得分（小组总分不超过12分）等。实验报告文件取名为re

4、port6.doc。每组还必须制作一个答辩PPT以备答辩。3、由组长上传实验报告文件report6.doc 、源程序文件test6.cpp及AdjMatrix.h和AdjLink.h到BB平台上。功能模块图：主菜单创建此图输出此图的邻接表或邻接矩阵查找朋友最多的人判断两人是否为朋友输出从A出发的广度优先搜索序列输出从A出发的深度优先搜索序列邻接表邻接矩阵函数调用结构图：mainInitMGraphShowMGraphmenuInitALGraphFindALGraphDFSTraverseMGraphShowALGraphBFSTraverseMGraphDFSTraverseALGraphF

5、indMGraphJudgeALGraphJudgeMGraphBFSTraverseALGraph左侧为邻接矩阵的相关函数，右侧为邻接表的相关函数结构体定义typedef struct MGraphstatus vexsMAXMAX; int arcsMAXMAXMAXMAX;int vernum,arcnum;MGraph; /邻接矩阵 /邻接表 typedef struct ArcNodeint adjvex; /下标 struct ArcNode *nextarc;ArcNode;typedef struct VNodestatus data;ArcNode *firstarc; VN

6、ode,AdjListMAXMAX;typedef structAdjList vertices;int vexnum,arcnum;ALGraph; /队列 typedef structint *data;int rear;int front;sqQueue; 实现思路深度优先搜索序列利用一个数组来记录顶点是否被访问，对未访问的邻接顶点进行递归，直至所有顶点均被访问。广度优先搜索序列利用一个数组来记录顶点是否被访问，未被访问的顶点及其邻接点进队列，并且“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至所有顶点均被访问，访问完后出队列至队空。运行结果与分析输入数字，进行对应的

7、操作输入1创建此图，输入1或2建立邻接矩阵或邻接表可改进之处可以增加查找两人的最短路径；可以增加对错误信息的处理；源代码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; /下标 struct ArcNode *nextarc;ArcNode;typedef struct VNodestatus data;ArcNode *firstarc; VNode,AdjListMAXMAX;typedef structAdjList vertices;int vexnum,arcnum;ALGraph; /队列 typedef structint *data;int r

9、ear;int front;sqQueue; int visitMAXMAX; /访问标志数组 int v;#includeQueue.h#includeAdjMatrix.h#includeAdjLink.hvoid menu()printf(1.创建此图n);printf(2.输出此图的邻接表或邻接矩阵n);printf(3.输出从A出发的深度优先搜索序列n); printf(4.输出从A出发的广度优先搜索序列n);printf(5.输入两个人p1、p2，判断此两人是否为朋友关系，若不是，给出一种从p1能找到p2的路径n);printf(6.查找朋友最多的那个人n);printf(0.退出

10、n);printf(输入您想进行的操作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) /创建队列 L.data=(int *)malloc(MAXMAX*sizeof(int);L.rear=0;L.front=0;int EnQueue(sqQueue &L,int v) /进队列 L.dataL.rear=v;L.rear=(

13、L.rear+1)%MAXMAX;int DeQueue(sqQueue &L,int &u) /出队列 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)/创建此图 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) /深度优先int i;visitv=TRUE;printf(姓名:%c n,M.);for(i=0;iMAX;i+) /遍历当前顶点的各个直接后继 if(!visitv)&(M.arcsvi=1)DFSMGraph(M,i); /对未访问过的且是邻接的点i进行递归 int

17、DFSTraverseMGraph(MGraph &M,int v) /深度优先 for(v=0;vMAX;v+)visitv=FALSE; /对访问标志数组初始化 for(v=0;vMAX;v+) if(!visitv) DFSMGraph(M,v);int BFSTraverseMGraph(MGraph &M,int v) /广度优先算法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的各个后继依次进队列 int JudgeDFS(MGraph &M,int &v,int *c,int b,int &o)/判断是否为朋友的函数中要用到的深度优先算法int n,i,j;visitv=TRUE;co=v; /用co来保存路径 o+;if(v=b) /当联通时，输出路径 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-; /消除无法连通的路径co=0; v=co-1; int JudgeMGraph(MGraph &M,int v)/判断是否为朋友 char n,p1,p2;int a,b,o=0,i;int cMAX;printf(请输入两个人的名字n);scanf(%c %c,&p1,&p2);for(i=0;iMAX;i+)if(M.=p1)a=i;if(M.=p2)b=i

20、; /得出下标 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); /深度优先算法 int FindMGraph(MGraph &M) /寻找朋友最多的人 int countMAX,i,j,max;for(i=0;iMAX;i+)counti=0; /将计数归零 for(i=0;iMAX;i+)for(j=0;jMAX;j+)if(M.arcsij=1)counti+; /用count计数，来计算每个人的朋友

21、个数 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)/深度优先ArcNode *p;p=(ArcNode *)malloc(sizeof(ArcNode);p=A.verticesv.firstarc;visitv=TRUE;printf(姓名:%c n,A.);while(p)if(visitp-adjvex!=TRUE) /如果这个下标没被访问过，进行递归，否则继续遍历这个链表 v=p-adjvex;DFSALGraph(A,v);p=p-nextarc; int DFSTraverseALGraph(ALGraph &A,int &v) /深度优先 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