图遍历的演示实验报告书.doc

1．实验题目 图遍历的演示 2．需求分析 本演示程序用VC++6.0编写，以邻接矩阵为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。 ①输入形式：要先输入顶点个数和边的条数，然后依次输入顶点的值，再输入每条边两端的值； ②输出形式：输出无向图的邻接矩阵，深度优先遍历序列及广度优先遍历序列。 ③测试数据： 测试结果： 3．概要设计 class WXT {　　　数据对象：tu={ ddxl[maxsize], juzhen[maxsize][maxsize], n, bian } 　 Bianwz(WXT tu,char v)　　操作结果：寻找V的位置　　GZWTU(WXT tu)　　操作结果：数组邻接矩阵表示法构造无向图　 DYljdd(WXT tu,int i)　　初始条件：图已存在　　操作结果：顶点下标为i的顶点的第一个邻接顶点　　XYdd(WXT tu,int i,int k)　　 初始条件：图已存在　　操作结果：顶点下标为i的顶点相对于k的下一个顶点,k为i的当前邻接顶点,二者都是顶点下标　　SDbl(WXT tu,int v)　　操作结果：无向图的深度优先遍历，从第v个顶点出发，v为顶点下标 SDbl_V(WXT tu,int vex) 操作结果：从vex开始深度遍历图 GDbl(WXT tu,int a) 操作结果：无向图的广度遍历，从第v个顶点出发，v为顶点下标 2）本程序包含8个函数：　　① 主函数main()　　②图的基本操作，寻找V的位置函数Bianwz(WXT tu,char v)　　③构造无向图函数GZWTU(WXT tu)　　④邻接顶点操作函数DYljdd(WXT tu,int i)　　⑤邻接顶点操作函数XYdd(WXT tu,int i,int k)　　⑥深度优先遍历函数SDbl(WXT tu,int v)　　⑦从vex开始深度遍历图函数SDbl_V(WXT tu,int vex) ⑧广度优先遍历函数GDbl(WXT tu,int a) 各函数间关系如下： 4．详细设计 #includeiostream #includequeue using namespace std; queueintq; //---------------------------------------------------------------- class WXT //无向图的邻接矩阵类型 { public: int Bianwz(WXT tu,char v);//图的基本操作，寻找V的位置 int GZWTU(WXT tu);//数组邻接矩阵表示法构造无向图 int DYljdd(WXT tu,int i);//顶点下标为i的顶点的第一个邻接顶点 int XYdd(WXT tu,int i,int k);//顶点下标为i的顶点相对于k的下一个顶点,k为i的当前邻接顶点,二者都是顶点下标 void SDbl(WXT tu,int v);//无向图的深度优先遍历，从第v个顶点出发，v为顶点下标 void SDbl_V(WXT tu,int vex);// 从vex开始深度遍历图 int GDbl(WXT tu,int a);//无向图的广度遍历，从第v个顶点出发，v为顶点下标 char ddxl[maxsize];//顶点向量// AdjMatrix int juzhen[maxsize][maxsize];//邻接矩阵 int n;//顶点数 int bian; //边数 }; WXT tu; //申明一个无向图的邻接矩阵类型 int biaozhi[maxsize];//设置标志数组 int WXT::Bianwz(WXT tu,char v)//图的基本操作，寻找V的位置 { int i=0; while(itu.n v!=tu.ddxl[i]) i++; if(itu.n) return i;//查找成功则返回顶点的下标 else return -1; } int WXT::GZWTU(WXT tu) //数组邻接矩阵表示法构造无向图 { char v1,v2; cout请输入图的顶点数和边数：endl; cintu.ntu.bian; cout请输入tu.n个顶点值：endl; for(int i=0;itu.n;i++)//构造顶点向量 cintu.ddxl[i]; for(int