实验四：图的遍历题目：图及其应用——图的遍历班级：姓名：学号：完成日期：一.需求分析1.问题描述：很多涉及图上操作的算法都是以图的遍历操作为基础的。
试写一个程序，演示在连通的无向图上访问全部结点的操作。
2.基本要求：以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。
以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。
3.测试数据：教科书图7.33。
暂时忽略里程，起点为北京。
4.实现提示：设图的结点不超过30个，每个结点用一个编号表示（如果一个图有n个结点，则它们的编号分别为1,2,…,n）。
通过输入图的全部边输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制，注意，生成树的边是有向边，端点顺序不能颠倒。
5.选作内容：（1）.借助于栈类型（自己定义和实现），用非递归算法实现深度优先遍历。
（2）.以邻接表为存储结构，建立深度优先生成树和广度优先生成树，再按凹入表或树形打印生成树。
二.概要设计1.为实现上述功能，需要有一个图的抽象数据类型。
该抽象数据类型的定义为：ADT Graph{数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。
数据关系R：R={VR}VR={<v，w> | v，w v且P(v，w)，<v，w>表示从v到w得弧，谓词P(v，w)定义了弧<v，w>的意义或信息}} ADT Graph2.此抽象数据类型中的一些常量如下：#define TRUE 1#define FALSE 0#define OK 1#define max_n 20 //最大顶点数typedef char VertexType[20];typedef enum{DG, DN, AG, AN} GraphKind;enum BOOL{False,True};3.树的结构体类型如下所示：typedef struct{ //弧结点与矩阵的类型int adj; //VRType为弧的类型。
图--0,1;网--权值int *Info; //与弧相关的信息的指针,可省略}ArcCell, AdjMatrix[max_n][max_n];typedef struct{VertexType vexs[max_n];//顶点AdjMatrix arcs; //邻接矩阵int vexnum, arcnum; //顶点数，边数}MGraph;//队列的类型定义typedef int QElemType;typedef struct QNode{QElemType data;struct QNode *next;}QNode, *QueuePtr;typedef struct{QueuePtr front;QueuePtr rear;}LinkQueue;4.本程序包含三个模块1).主程序模块void main( ){创建树；深度优先搜索遍历；广度优先搜索遍历；}2).树模块——实现树的抽象数据类型3).遍历模块——实现树的深度优先遍历和广度优先遍历各模块之间的调用关系如下：主程序模块树模块遍历模块三.详细设计#include "stdafx.h"#include<iostream>using namespace std;#define TRUE 1#define FALSE 0#define OK 1#define max_n 20 //最大顶点数typedef char VertexType[20];typedef enum{DG, DN, AG, AN} GraphKind;enum BOOL{False,True};typedef struct{ //弧结点与矩阵的类型int adj; //VRType为弧的类型。
图--0,1;网--权值int *Info; //与弧相关的信息的指针,可省略}ArcCell, AdjMatrix[max_n][max_n];typedef struct{VertexType vexs[max_n]; //顶点AdjMatrix arcs; //邻接矩阵int vexnum, arcnum;//顶点数，边数}MGraph;//队列的类型定义typedef int QElemType;typedef struct QNode{QElemType data;struct QNode *next;}QNode, *QueuePtr;typedef struct{QueuePtr front;QueuePtr rear;}LinkQueue;//初始化队列int InitQueue(LinkQueue *Q){return OK;}//判断队列是否为空int EmptyQueue(LinkQueue Q){if(Q.front==Q.rear)return TRUE;elsereturn FALSE;}//入队列int EnQueue(LinkQueue *Q, QElemType e) {QueuePtr p;p->data=e;p->next=NULL;(*Q).rear->next=p;(*Q).rear=p;return OK;}//出队列int DeQueue (LinkQueue *Q, QElemType *e) {QueuePtr p;if((*Q).front==(*Q).rear) return -1;p=(*Q).front->next;*e=p->data;(*Q).front->next=p->next;if((*Q).rear==p)(*Q).rear=(*Q).front;delete p;return OK;}/* 顶点在顶点向量中的定位*/int Locate(MGraph G, VertexType v){int i;for(i=0;i<G.vexnum;i++)if(strcmp(v,G.vexs[i])==0) break;return i;void CreateGraph(MGraph &G){ // 图G用邻接矩阵表示,创建图int k,i,j;VertexType vi,vj;cout<<"请输入图的顶点个数和边的数目: ";cin>>G.vexnum>>G.arcnum;cout<<"请输入顶点: ";for(k=0;k<G.vexnum;k++)cin>>G.vexs[k];for(i=0;i<G.vexnum;i++) //初始化邻接矩阵for(j=0;j<G.vexnum;j++)G.arcs[i][j].adj=0;cout<<"请输入边集: "<<endl;for(k=0; k<G.arcnum; k++){cin>>vi>>vj;i=Locate(G,vi); j=Locate(G, vj); //求Vi和Vj的下标G.arcs[i][j].adj=1;G.arcs[j][i].adj=1;}}int FirstAdjVex(MGraph G, int V){ // 图G用邻接矩阵表示，求下标为V的顶点的第一个邻接点int i=0;while(i<G.vexnum && G.arcs[V][i].adj==0){i++;}if(i>=G.vexnum) return -1;else return i; //返回V的第一个邻接点的下标}int NextAdjVex(MGraph G,int V,int w){ // 图G用邻接矩阵表示int i=w+1;while(i<G.vexnum && G.arcs[V][i].adj==0) i++;if(i>=G.vexnum)return -1; //V的w邻接点之后没有邻接点elsereturn i; //返回V行w列之后第一个非0元的下标}int visited[100]; /* 设置全局的访问标志数组*/void DFS(MGraph G, int v){//从序号为v的顶点出发，对图G做一次深度优先搜索遍历int w;visited[v]=1;cout<<G.vexs[v]<<" ";for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)){if(!visited[w]) DFS(G,w);}}//深度优先搜索遍历图Gvoid DFSTraverse(MGraph G){int v;for(v=0;v<G.vexnum;v++) visited[v]=0;for(v=0;v<G.vexnum;v++)if(!visited[v])DFS(G,v);//若顶点v未被访问，从v开始遍历}void BFSTraverse(MGraph G){int v,w,u;LinkQueue Q;for(v=0;v<G.vexnum;++v) visited[v]=0;InitQueue(&Q); //初始化队列for(v=0;v<G.vexnum;++v){if(!visited[v]){visited[v]=1;cout<<G.vexs[v]<<" ";EnQueue(&Q,v); //v入队while(!EmptyQueue(Q)){DeQueue(&Q,&u); //队头元素u出队for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w)){if(!visited[w]){visited[w]=1;cout<<G.vexs[w]<<" ";EnQueue(&Q,w);}}}}}}int main(){MGraph G;CreateGraph(G);cout<<"深度优先搜索遍历顺序为: ";DFSTraverse(G);cout<<endl;cout<<"广度优先搜索遍历序列为: ";BFSTraverse(G);cout<<endl;return 0;}四.调试分析1.先建立一幅图，然后依次进行深度优搜索先遍历。