实验项目六 图结构基本操作的实现
课程名称：数据结构
实验项目名称：图结构基本操作的实现
实验目的：
1．掌握图的基本操作—遍历。
实验要求：
1、 分别用DFS和BFS的方法实现一个无向图的遍历。
实验过程：
1、 创建一个图（可用邻接矩阵或邻接表的方式进行存储）；
2、 输入选项：0或1，0为DFS，1为BFS。
3、 分别输出DFS和BFS两种遍历序列；
实验报告中给出DFS和BFS两种遍历的算法代码。
实验结果：
1、输入顶点集：1 2 3 4 5 6 7 8
2、输入边的集合： 1 2
1 3
2 4
2 5
4 8
5 8
3 6
3 7
6 7
输入：0（DFS）
输出：DFS遍历序列为：12485367
输入：1（BFS）
输出：BFS遍历序列为：12345678
实验分析：
1.简单分析DFS与BFS实现时用到的方法（DFS通过递归函数实现，用到栈的数据结构，BFS用到队列的数据结构）；
2.列举调试运行过程中出现的错误并分析原因。
要求：
(1) 程序要添加适当的注释，程序的书写要采用缩进格式。
(2) 程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反应。
(3) 程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。
(4) 上传源程序到课堂派。顺序表的源程序保存为TraversalGraph.cpp。
#include<stdio.h> #include<iostream> using namespace std; #define MaxInt 32767 //表示极大值 #define MVNum 100 //最大定点数 #define OK 1 #define MAXQSIZE 100 typedef char VerTexType; //假设顶点的数据类型为字符型 typedef int ArcType; //假设边的权值类型为整型 typedef struct { VerTexType vexs[MVNum]; //定点表 ArcType arcs[MVNum][MVNum]; //邻接矩阵 int vexnum,arcnum; //图的当前点和边数 }AMGraph; AMGraph G; typedef struct { int *base; int front,rear; }SqQueue; int InitQueue(SqQueue &Q) {//构造一个空队列Q Q.base=new int[MAXQSIZE]; //为队列分配一个最大容量为MAXQSIZE的数组空间 if(!Q.base) exit(0); //存储分配失败 Q.front=Q.rear=0; //头指针和尾指针为零，队列为空 return OK; } int EnQueue(SqQueue &Q,int e) {//插入元素e为Q的新的队尾元素 if((Q.rear+1)%MAXQSIZE==Q.front) //尾指针在循环意义上加1后等于头指针，表明队满 return 0; Q.base[Q.rear]=e; //新元素插入队尾 Q.rear=(Q.rear+1)%MAXQSIZE; //队尾指针加1 return OK; } int DeQueue(SqQueue &Q,int &e) {//删除Q的队头元素，用e返回其值 if(Q.front==Q.rear) return 0; //队空 e=Q.base[Q.front]; //保存队头元素 Q.front=(Q.front+1)%MAXQSIZE; //队头指针加1 return OK; } int QueueEmpty(SqQueue &Q) { if (Q.front==Q.rear) return OK; else return 0; } int LocateVex(AMGraph G,int b) { int a; for(a=0;a<G.vexnum;a++) //判断顶点在第几个位置 { if(G.vexs[a]==b) return a; } } int CreateUDN(AMGraph &G) {//采用邻接矩阵表示法，创建无向网G cout<<"请输入顶点的个数： "; cin>>G.vexnum; //输入总顶点数 cout<<"请输入边的条数： "; cin>>G.arcnum; //输入总边数 int i,j,k,v1,v2,w; cout<<"依次输入顶点的信息： "; for(i=0;i<G.vexnum;i++) //依次输入点的信息 cin>>G.vexs[i]; for(i=0;i<G.vexnum;i++) //初始化邻接矩阵，边的权值位置为极大值MaxInt for(j=0;j<G.vexnum;j++) G.arcs[i][j]=0; for(k=0;k<G.arcnum;k++) //构造邻接矩阵 { cout<<"输入一条边依附的顶点: "; cin>>v1>>v2; //输入一条边依附的顶点及权值 // i=LocateVex(G,v1); // j=LocateVex(G,v2); //确定v1和v2在G中的位置，及顶点数组的下标 // G.arcs[i][j]=w; //变<v1，v2>的初值置为w // G.arcs[j][i]=G.arcs[i][j]; //置<v1，v2>的对称边<v2，v1>的权值为w G.arcs[v1][v2]=1; G.arcs[v2][v1]=1; } return OK; } bool visited[MVNum]; //访问标志数组，其初值为“false” void DFS_AM(AMGraph G,int v) {//从第V个定点出发递归的深度优先遍历图G cout<<v; int w; visited[v]=1; //访问第v个顶点，并置访问标志数组相应分量值为true for(w=1;w<=G.vexnum;w++) if((G.arcs[v][w]!=0)&&(!visited[w])) DFS_AM(G,w); } void DFSTraverse(AMGraph G) {//对非连接图G做深度优先遍历 int v; for(v=0;v<G.vexnum;++v) visited[v]=0; for(v=1;v<=G.vexnum;++v) if(!visited[v]) DFS_AM(G,v); //对尚未访问的顶点调用DFS } void BFS(AMGraph G,int v) {//按广度优先非递归遍历连接图 cout<<v; int u,w; SqQueue Q; // for(w=0;w<G.vexnum;w++) // { // visited[w]=0; // } visited[v]=1; InitQueue(Q); EnQueue(Q,v); while(!QueueEmpty(Q)) { DeQueue(Q,u); for(w=1;w<=G.vexnum;w++) if((G.arcs[u][w]!=0)&&(!visited[w])) { cout<<w; visited[w]=1; EnQueue(Q,w); } } } main() { CreateUDN(G); int choose,v; while(1) { cout<<"请输入功能0（DFS）或1（BFS）: "; cin>>choose; if(choose==0) { DFS_AM(G,1); break; } else if(choose==1) { BFS(G,1); break; } else { cout<<"输入错误，请重新输入: "; } } }