实验六 图的综合应用
一、实验目的
1．掌握图的基本操作—遍历；
2. 掌握图的应用。
二、实验内容
对给定的输入内容，完成实验任务
输入顶点集：1 2 3 4 5 6 7 8
输入边的集合： 1 2
1 3
2 4
2 5
4 8
5 8
3 6
3 7
6 7
（1）创建一个图（可用邻接矩阵或邻接表的方式进行存储）；
（2）输入选项：0或1，0为DFS，1为BFS；
（3）分别输出DFS和BFS两种遍历序列。
三、实验要求
1. 程序要添加适当的注释，程序的书写要采用缩进格式。
2. 程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反应，如插入删除时指定的位置不对等等。
3. 程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。
4. 实验课前完成实验内容源程序的初稿；实验课对源程序进行编辑、调试、运行；实验课后按规定时间上交实验内容。
5. 按照实验内容完成程序编写，并将源代码和运行结果截图粘贴到word文档中，A4正反打印，写清班级和姓名提交。
代码部分头文件与邻接矩阵、邻接表、辅助队列的定义
#include#include #include #include #define MaxInt 32767 #define MVNum 100 using namespace std; typedef struct{ int vexs[MVNum];//顶点表 int arcs[MVNum][MVNum];//邻接矩阵 int vexnum,arcnum; }AMGraph; typedef struct{ int *base; int frone; int rear; int maxize; }SqQueue; typedef struct ArcNode{ int adivex; struct ArcNode *nextarc; }ArcNode;//指针p typedef struct VNode{ int data; ArcNode * firstarc; }Vnode,AdjList[MVNum]; typedef struct{ AdjList vertices; int vexnum,arcnum; }ALGraph;
菜单函数
void menu1(){
cout<<"<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>>"<>>>>>>>>>>>>>>>"<>>>>>>>>>>>>>>>"<>>>>>>>>>>>>>>>"<>>>>>>>>>>>>>>>"<
邻接矩阵与邻接表的下标定位LocateVex函数
int LocateVex1(AMGraph &G,int v){
for(int i=0;i<=G.vexnum;++i)
if(v==G.vexs[i])
return i;
cout<<"未在图中找到编号为"<
辅助队列所需使用的基本函数
void InitQueue(SqQueue &Q,int n){
Q.base=new int[n];
Q.maxize=n;
Q.frone=Q.rear=0;
}
void EnQueue(SqQueue &Q,int v){
Q.base[Q.rear]=v;
Q.rear=(Q.rear+1)%Q.maxize;
}
int DeQueue(SqQueue &Q){
int x=Q.base[Q.frone];
Q.frone=(Q.frone+1)%Q.maxize;
return x;
}
int QueueEmpty(SqQueue &Q){
if(Q.frone==Q.rear) return 1;
else return 0;
}
以邻接矩阵存储图 代码部分
创建邻接矩阵
void CreatUDNAM(AMGraph &G){
int i,j,k,v1,v2;
cout<<"|---请输入总顶点数与总边数！---|"<>G.vexnum>>G.arcnum;
cout<<"|---------请输入顶点值!--------|"<>G.vexs[i];
}
for(i=0;i>v1>>v2;
i=LocateVex1(G,v1);
j=LocateVex1(G,v2);
if(i==-1||j==-1){
cout<<"|-----邻接矩阵中无"<
输出邻接矩阵
void putAMGragp(AMGraph G){
int i,j;
cout<<" ";
for(i=0;i
DFS递归遍历邻接矩阵
bool visitedDFS[MVNum];
void DFS_AM(AMGraph G,int v){
cout<
BFS遍历邻接矩阵 （需要使用辅助队列）
bool visitedBFS[MVNum];
void BFS_AM(AMGraph G,int v){//注意返回值
SqQueue Q;
InitQueue(Q,G.vexnum);
int i,w;
cout<
以邻接表存储图 代码部分
创建邻接表
void CreatUDNAL(ALGraph &g){
int v1,v2,i,j;
ArcNode *p1,*p2;
cout<<"|---请输入总顶点数与总边数！---|"<>g.vexnum>>g.arcnum;//输入总点数与总边数
cout<<"|--------请输入顶点值！--------|"<>g.vertices[i].data;//输入点值
g.vertices[i].firstarc=NULL;//表头结点的指针域初始化为空
}
cout<<"|--------请输入边的值！--------|"<>v1>>v2;//输入边的两个顶点
i=LocateVex2(g,v1);//定位i
j=LocateVex2(g,v2);//定位j
p1=new ArcNode;//生成边结点p1
p1->adivex=j;//p1的邻接点记为j
p1->nextarc=g.vertices[i].firstarc;
g.vertices[i].firstarc=p1;
p2=new ArcNode;//生成新的边结点p2
p2->adivex=i;//p2的邻接定记为i
p2->nextarc=g.vertices[j].firstarc;
g.vertices[j].firstarc=p2;
}
cout<<"|-----以邻接表建立图完成！-----|"<
DFS递归遍历邻接表
bool visitDFS[MVNum];
void DFS_AL(ALGraph g,int v){
int w;
cout<adivex;//找到v的下个点
if(visitDFS[w]!=true)//未被访问过的点
DFS_AL(g,w);//递归调用，深度遍历
p=p->nextarc;
}
}
BFS遍历邻接表
bool visitBFS[MVNum];
void BFS_AL(ALGraph &g,int v){
SqQueue q;
ArcNode *p;//指针指向邻接表
int w;
InitQueue(q,g.vexnum);//创建队列
cout<adivex]!=true){//判断是否被遍历过
cout<adivex].data<<" ";//输出指针p指向的data
visitBFS[p->adivex]=true;//标记
EnQueue(q,p->adivex);//将指针p指向的值入队
}
if(p->nextarc==NULL){//若为最后一个结点则跳出该循环
break;
}
else{
p=p->nextarc;//不是最后一个结点则p指向下一个结点
}
}
// while(p){//当p的指向为空时候跳出循环
// if(visitBFS[p->adivex]!=true){
// cout<adivex].data<<" ";
// visitBFS[p->adivex]=true;
// EnQueue(q,p->adivex);
// }
// p=p->nextarc;
// }
}
cout<
输出邻接表
void printf_ALGraph(ALGraph &g){
ArcNode *p;
int flag=0;
for(int i=0;i";
cout<adivex].data;
p=p->nextarc;
}
else{
cout<<"《"<"<adivex].data;
flag=1;
p=p->nextarc;
}
}
flag=0;
cout<
主函数
int main(){
int choose,n,v=0;
A: menu1();
cout<<"请选择操作：";
cin>>choose;
if(choose==1){
cout<<"|---图将以邻接矩阵进行存储！---|"<>n;
switch(n){
case 0:
cout<<"该图的深度优先遍历结果为：";
DFS_AM(G,v);
cout<>n;
switch(n){
case 0:
cout<<"该图的深度优先遍历结果为：";
DFS_AL(g,v);
cout<
完整测试样例：
#include
#include
#include
#include
#define MaxInt 32767
#define MVNum 100
using namespace std;
typedef struct{
int vexs[MVNum];//顶点表
int arcs[MVNum][MVNum];//邻接矩阵
int vexnum,arcnum;
}AMGraph;
typedef struct{
int *base;
int frone;
int rear;
int maxize;
}SqQueue;
typedef struct ArcNode{
int adivex;
struct ArcNode *nextarc;
}ArcNode;//指针p
typedef struct VNode{
int data;
ArcNode * firstarc;
}Vnode,AdjList[MVNum];
typedef struct{
AdjList vertices;
int vexnum,arcnum;
}ALGraph;
int LocateVex1(AMGraph &G,int v){
for(int i=0;i<=G.vexnum;++i)
if(v==G.vexs[i])
return i;
cout<<"未在图中找到编号为"<>G.vexnum>>G.arcnum;
cout<<"|---------请输入顶点值!--------|"<>G.vexs[i];
}
for(i=0;i>v1>>v2;
i=LocateVex1(G,v1);
j=LocateVex1(G,v2);
if(i==-1||j==-1){
cout<<"|-----邻接矩阵中无"<>>>>>>>>>>>>>>>"<>>>>>>>>>>>>>>>"<>>>>>>>>>>>>>>>"<>>>>>>>>>>>>>>>"<>>>>>>>>>>>>>>>"<>g.vexnum>>g.arcnum;//输入总点数与总边数
cout<<"|--------请输入顶点值！--------|"<>g.vertices[i].data;//输入点值
g.vertices[i].firstarc=NULL;//表头结点的指针域初始化为空
}
cout<<"|--------请输入边的值！--------|"<>v1>>v2;//输入边的两个顶点
i=LocateVex2(g,v1);//定位i
j=LocateVex2(g,v2);//定位j
p1=new ArcNode;//生成边结点p1
p1->adivex=j;//p1的邻接点记为j
p1->nextarc=g.vertices[i].firstarc;
g.vertices[i].firstarc=p1;
p2=new ArcNode;//生成新的边结点p2
p2->adivex=i;//p2的邻接定记为i
p2->nextarc=g.vertices[j].firstarc;
g.vertices[j].firstarc=p2;
}
cout<<"|-----以邻接表建立图完成！-----|"<adivex;//找到v的下个点
if(visitDFS[w]!=true)//未被访问过的点
DFS_AL(g,w);//递归调用，深度遍历
p=p->nextarc;
}
}
bool visitBFS[MVNum];
void BFS_AL(ALGraph &g,int v){
SqQueue q;
ArcNode *p;//指针指向邻接表
int w;
InitQueue(q,g.vexnum);//创建队列
cout<adivex]!=true){//判断是否被遍历过
cout<adivex].data<<" ";//输出指针p指向的data
visitBFS[p->adivex]=true;//标记
EnQueue(q,p->adivex);//将指针p指向的值入队
}
if(p->nextarc==NULL){//若为最后一个结点则跳出该循环
break;
}
else{
p=p->nextarc;//不是最后一个结点则p指向下一个结点
}
}
// while(p){//当p的指向为空时候跳出循环
// if(visitBFS[p->adivex]!=true){
// cout<adivex].data<<" ";
// visitBFS[p->adivex]=true;
// EnQueue(q,p->adivex);
// }
// p=p->nextarc;
// }
}
cout<";
cout<adivex].data;
p=p->nextarc;
}
else{
cout<<"《"<"<adivex].data;
flag=1;
p=p->nextarc;
}
}
flag=0;
cout<>choose;
if(choose==1){
cout<<"|---图将以邻接矩阵进行存储！---|"<>n;
switch(n){
case 0:
cout<<"该图的深度优先遍历结果为：";
DFS_AM(G,v);
cout<>n;
switch(n){
case 0:
cout<<"该图的深度优先遍历结果为：";
DFS_AL(g,v);
cout<
