浙江大学城市学院实验报告
课程名称 数据结构
实验项目名称 实验六 图的基本操作与应用
实验成绩 指导老师（签名 ） 日期
二.实验目的和要求
1、掌握图的存储结构：邻接矩阵、邻接表。
2、掌握图的深度优先与广度优先两个搜素算法。
3、学会对图的存储结构进行基本操作。
4、加强综合程序的分析、设计能力。
三.实验内容
silent all the years
1、现有14个人（分别用字母A、B、... N表示），他们相互之间的朋友关系如图所示（有线相连表示是朋友关系），请分别用邻接矩阵与邻接表表示该关系图，并完成以下功能。
① 以邻接矩阵表示，在此结构上完成：
●创建此图；
●输出此图的邻接矩阵；
●输出从A出发的深度优先搜索序列；
●输出从A出发的广度优先搜索序列；
●输入两个人p1、p2，判断此两人是否为朋友关系，若不是，给出一种从p1能找到p2的路径；（如输入p1=‘Afine china’、p2=‘N’，则A与N不是直接朋友关系，但可以（不唯一）通过A-B-F-K-N方式联系到N。）evil genius
② 以邻接表表示，在此结构上完成：
●创建此图；
●输出此图的邻接表；
●输出从A出发的深度优先搜索序列；
●输出从A出发的广度优先搜索序列；
●输入两个人p1、p2，判断此两人是否为朋友关系，若不是，给出一种从p1能找到p2的路径；（如输入p1=‘A’、p2=‘N’，则A与N不是直接朋友关系，但可以（不唯一）通过A-B-F-K-N方式联系到N。）
③ 建立头文件AdjMatrix.h和AdjLink.h，分别包含邻接矩阵结构和邻接表结构的操作实现
函数，建立主程序文件test6.cpp，在主函数中通过调用来实现上述功能。
④ 自行增加合适的功能，可作为额外的实验成绩进行加分（例如考虑添加或删除一对朋友关系；找出朋友最多的那个人；上面找到A到N的联系路径，若要求找到一条最短的路线怎么找等等）。
2、以小组为单位认真考研结果什么时候出填写实验报告，实验报告必须包括各类数据类型的结构定义说明，各类数据的组织方式，系统的功能结构，各个操作的定义以及实现方法，运行结果与分析，难点如何解决，存在问题以及可改进之处等。同时，在实验报告中需写明小组每位同学的分工，得分（小组总分不超过12分）等。实验报告文件取名为report6.doc。每组还必须制作一个答辩PPT以备答辩。
3、由组长上传实验报告文件report6.doc 、源程序文件test6.cpp及AdjMatrix.h和AdjLink.h到BB平台上。
功能模块图：
函数调用结构图：
左侧为邻接矩阵的相关函数，右侧为邻接表的相关函数
结构体定义
typedef struct MGraph
{
status vexs[MAXMAX];
int arcs[MAXMAX][MAXMAX];
int vernum,arcnum;
}MGraph; //邻接矩阵
//邻接表
typedef struct ArcNode
{
int adjvex; //下标
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode
{
status data;
ArcNode *firstarc;
} VNode,AdjList[MAXMAX];
typedef struct
{
AdjList vertices;
int vexnum,arcnum;
}ALGraph;
//队列
typedef struct
{
int *data;
int rear;
int front;
}sqQueue;
实现思路
深度优先搜索序列利用一个数组来记录顶点是否被访问，对未访问的邻接顶点进行递归，直至所有顶点均被访问。
广度优先搜索序列利用一个数组来记录顶点是否被访问，未被访问的顶点及其邻接点进队列，并且“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至所有顶点均被访问，访问完后出队列至队空。
运行结果与分析
输入数字，进行对应的操作
输入1创建此图，输入1或2建立邻接矩阵或邻接表
可改进之处
可以增加查找两人的最短路径；
可以增加对错误信息的处理；
源代码
test6.cpp
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#include<windows.h>
#define OK 1
#define FALSE 0
#define TRUE 1
#define ERROR 0
#define INFEASIBLE -1
excite#define OVERFLOW -2
#define MAXMAX 100
int MAX=14;
typedef struct
{
char name;
}status;
typedef struct MGraph
{
status vexs[MAXMAX];
adhereto
int arcs[MAXMAX][MAXMAX];
int vernum,arcnum;
}MGraph; //邻接矩阵
//邻接表
typedef struct ArcNode
{
int adjvex; //下标
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode
{
status data;
ArcNode *firstarc;
} VNode,AdjList[MAXMAX];
typedef struct
{
AdjList vertices;
int vexnum,arcnum;
}ALGraph;
//队列
typedef struct
必须的英文{
int *data;
int rear;
int front;
}sqQueue;
int visit[MAXMAX]; //访问标志数组
int v;
#include"Queue.h"
#include"AdjMatrix.h"
#include"AdjLink.h"
篡夺的意思void 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.退出\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)
{
26个汉语拼音字母表 InitALGraph(A);
}
printf("输入9返回，输入0退出\n");
}
if(n==2)
{
system("CLS");
if(a==1)
{
ShowMGraph(M);
}
if(a==2)
{
ShowALGraph(A);
}
printf("输入9返回，输入0退出\n");
}
if(n==3)
{
system("CLS");
if(a==1)
{
v=0;
DFSTraverMGraph(M,v);
}
if(a==2)
{
v=0;
DFSTraverALGraph(A,v);
}
printf("输入9返回，输入0退出\n");
}
if(n==4)
{
system("CLS");
if(a==1)
{
BFSTraverMGraph(M,v);
