南邮数据结构上机实验三图的基本运算及飞机换乘次数最少问题

实验报告（2015/2016学年第二学期）课程名称数据结构A实验名称图的基本运算及飞机换乘次数最少问题实验时间2016年5月19日指导单位计算机科学与技术系指导教师骆健学生姓名班级学号学院(系)管理学院专业信息管理与信息系统实习题名:图的基本运算班级姓名学号日期2016.05.19一、问题描述验证教材中关于在邻接矩阵和邻接表两种不同的储存结构上实现图的基本运算的算法(见程序9.1~程序9.8)，在邻接矩阵存储结构上实现图的深度和广度优先遍历算法，设计主函数，测试上述运算。二、概要设计文件graph.cpp中在该文件中定义图数据结构的抽象模板类Graph。邻接矩阵类MGraph是从抽象类Graph派生得来，邻接表类LGraph也是从抽象类Graph派生得来。主函数的代码如图所示。三、详细设计1.类和类的层次设计程序定义了Graph类，以及邻接矩阵类MGraph和邻接表类LGraph以及循环列表类SeqQueue。邻接矩阵类MGraph继承了Graph的数据成员n和e，重载了Graph的纯虚函数。保护数据成员T**a指向动态生成的二维数组，用以存储邻接矩阵。邻接表类LGraph也继承了Graph的数据成员n和e及重载了Graph的纯虚函数，边结点由类ENode定义，每个结点有三个域adjVex、w和nextArc。邻接表的表头组成为一维数组，a是指向该数组的指针。（a）循环队列类（b）模版类Graph，MGraph和LGraphSeqQueue-intfront,rear;-intmaxSize;-BTNodeT**q;+SeqQueue(intmSize);+~SeqQueue(){delete[]q;}+boolIsEmpty()const{returnfront==rear;}+boolIsFull()const{return(rear+1)%maxSize==front;}+boolFront(BTNodeT*&x)const;+boolEnQueue(BTNodeT*x);+boolDeQueue();+voidClear(){front=rear=0;}MGraph#T**a;#TnoEdge;#voidDFS(intv,bool*visited);#voidBFS(intv,bool*visited);+MGraph(intmSize,constT&noedg);+~MGraph();+ResultCodeInsert(intu,intv,T&w);+ResultCodeRemove(intu,intv);+boolExist(intu,intv)const;+voidDFS();+voidBFS();TLGraph#ENodeT**a;+LGraph(intmSize);+~LGraph();+ResultCodeInsert(intu,intv,T&w);+ResultCodeRemove(intu,intv);+boolExist(intu,intv)const;TGraph#intn,e;+virtualResultCodeInsert(intu,intv,T&w)=0;+virtualResultCodeRemove(intu,intv)=0;+virtualboolExist(intu,intv)const=0;TT2.核心算法深度优先搜索用栈来实现：1)把根节点压入栈中2)每次从栈中弹出一个元素，搜索所有在它下一级的元素，把这些元素压入栈中。并把这个元素记为它下一级元素的前驱3)找到所要找的元素时结束程序4)如果遍历整个树还没有找到，结束程序广度优先搜索使用队列来实现：1)把根节点放到队列的末尾2)每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱3)找到所要找的元素时结束程序4)如果遍历整个树还没有找到，结束程序DFS()BFS()四、程序代码templateclassTvoidMGraphT::DFS()//深度遍历{bool*visited=newbool[n];for(inti=0;in;i++)visited[i]=false;for(i=0;in;i++)if(!visited[i])DFS(i,visited);delete[]visited;}templateclassTvoidMGraphT::DFS(intv,bool*visited){visited[v]=true;coutv;for(inti=0;in;i++)if(a[v][i]!=noEdge&&a[v][i]!=0&&!visited[i])DFS(i,visited);}templateclassTvoidMGraphT::BFS()//广度遍历{bool*visited=newbool[n];for(inti=0;in;i++)visited[i]=false;for(i=0;in;i++)if(!visited[i])BFS(i,visited);delete[]visited;}templateclassTvoidMGraphT::BFS(intv,bool*visited){SeqQueueintq(n);visited[v]=true;coutv;q.EnQueue(v);while(!q.IsEmpty()){q.Front(v);q.DeQueue();for(inti=0;in;i++)if(a[v][i]!=noEdge&&a[v][i]!=0&&!visited[i]){visited[i]=true;couti;q.EnQueue(i);}}}五、测试和调试1.测试用例和结果测试结果如下图1)输入元素的个数以及权值2)输入边以及权值3)得到图的深度遍历以及广度遍历4)输入要搜索的边，得到搜索结果5)输入要删除的边，得到新的遍历2.结果分析1)程序能够正确的实现关于在邻接矩阵和邻接表两种不同的储存结构上实现图的基本运算的算法，在邻接矩阵存储结构上实现图的深度和广度优先遍历算法2)由测试结果来看，若在输出数据时以图的形式输出，更简单直观，程序还有待改进。实习题名:飞机最少换乘问题班级姓名学号日期2016.05.19一、问题描述设有n个城市，编号为0～n−1，m条航线的起点和终点由用户输入提供。寻找一条换乘次数最少的线路方案。（提示：可以使用有向图表示城市间的航线。只要两城市间有航班，则图中这两点间存在一条权为1的边。可以使用Dijkstra算法实现）二、概要设计文件min.cpp中定义了两个类,分别是图数据结构的抽象模板类Graph以及从抽象类Graph派生得来邻接矩阵类MGraph。主函数mian的代码如图所示：三、详细设计1.类和类的层次结构程序定义了Graph类，以及邻接矩阵类MGraph。同上邻接矩阵类MGraph也继承了Graph的数据成员n和e，重载了Graph的纯虚函数。保护数据成员T**a指向动态生成的二维数组，用以存储邻接矩阵。模版类Graph和MGraph2.核心算法定义了类之后，求换乘次数最少主要是通过迪杰斯特拉算法实现。迪杰斯特拉算法主要通过动态创建数据结构，初始化操作，将源点v加入集合S，使用for循环，按照长度的非递减次序，依次产生n-1条最短路径等步骤实现。核心算法程图如下：MGraph#T**a;#TnoEdge;#voidDFS(intv,bool*visited);#voidBFS(intv,bool*visited);+MGraph(intmSize,constT&noedg);+~MGraph();+ResultCodeInsert(intu,intv,T&w);+ResultCodeRemove(intu,intv);+boolExist(intu,intv)const;+voidDFS();+voidBFS();TGraph#intn,e;+virtualResultCodeInsert(intu,intv,T&w)=0;+virtualResultCodeRemove(intu,intv)=0;+virtualboolExist(intu,intv)const=0;TDijkstra()四、程序代码templateclassTvoidMGraphT::Dijkstra(intv,T*d,int*path)//迪杰斯特拉算法{inti,k,w;if(v0||vn-1)throwOutOfBounds;bool*s=newbool[n];for(i=0;in;i++){s[i]=false;d[i]=a[v][i];if(i!=v&&d[i]INF)path[i]=v;elsepath[i]=-1;}s[v]=true;d[v]=0;for(i=1;in;i++){k=Choose(d,s);s[k]=true;for(w=0;wn;w++)if(!s[w]&&(d[k]+a[k][w])d[w]){d[w]=d[k]+a[k][w];path[w]=k;}}}五、测试和调试1.测试用例和结果1)输入城市个数以及航线条数2)分别输入每条航线的起点和终点3)得到换乘次数最小的路线4)最后输入N退出2.结果分析1)程序能够完全实现题目的要求，通过迪杰斯特拉算法实现了飞机换乘次数最小的路线2)下一步的目标是使用类似的算法对城市公交车的最少换乘问题进行解决实习小结在本次实验中出现了一些问题在用邻接矩阵存储结构实现图的广度优先遍历时，出现了输出结果为有序排列，改变图的顶点之间的关系后结果仍然不变，修改约束条件后，问题得以解决。在用邻接表存储结构实现Djikstra算法时，出现了指针访问冲突的问题，经调试检查发现是由访问数组越界导致，修改了约束条件后问题得以解决。本次实验主要是要求在邻接表存储结构上实现图的深度优先遍历以及广度优先遍历和使用Djikstra算法求单源最短路径的问题。经过本次实验对图的不同存储结构适用情况有了更进一步认识，通过修改Djikstra算法使其实现在图的邻接表存储结构上求最短路径，进一步加深对该算法的理解。通过这次实验我对图这种应用广泛的数据结构更加熟悉，结合课堂知识，以及老师的帮助，让我学到了更多。附录：1.图的基本运算#includeiostream.hconstintINFTY=2147483640;enumResultCode{Underflow,Duplicate,Failure,Success,NotPresent};templateclassTclassGraph//抽象类{public:virtualResultCodeInsert(intu,intv,T&w)=0;virtualResultCodeRemove(intu,intv)=0;virtualboolExist(intu,intv)const=0;protected:intn,e;};templateclassT//循环队列类classSeqQueue{public:SeqQueue(intmSize);~SeqQueue(){delete[]q;}boolIsEmpty()const{returnfront==rear;}boolIsFull()const{return(rear+1)%maxSize==front;}boolFront(T&x)const;boolEnQueue(Tx);boolDeQueue();voidClear(){front=rear=0;}private:intfront,rear;intmaxSize;T*q;};templateclassTSeqQueueT::SeqQueue(intmSize)//构造函数{maxSize=mSize;q=newT[maxSize];front=rear=0;}templateclassTb