数据结构A第三次实验报告

1、实 验 报 告（2014 / 2015 学年 第 二 学期）课程名称数据结构A实验名称图的基本运算及飞机换乘次数最少问题实验时间年月日指导单位计算机学院计算机科学与技术系指导教师学生姓名班级学号学院(系)管理学院专 业 信息管理与信息系统实 验 报 告实验名称图的基本运算及飞机换乘次数最少问题指导教师陈蕾实验类型设计实验学时2实验时间2一、 实验目的和要求（1）图的基本运算验证教材中关于在邻接矩阵和邻接表两种不同存储结构上实现图的基本运算的算法。在邻接矩阵存储结构上实现图的深度和广度优先遍历算法。设计主函数，测试上述运算。提示：扩充MGraph类，在扩充类上增加DFS和BFS函数。（2）飞机最

2、少换乘次数问题 设有n个城市，编号为0n-1，m条航线的起点和终点由用户输入提供。寻找一条换乘次数最少的线路方案。 提示：可以使用有向图表示城市间的航线。只要两城市间有航班，则图中这两点间存在一条权为1的边。可以使用Dijkstra算法实现。思考：如果是城市公交车的最少换乘问题，将如何解决？假如希望使用类似的算法，则图中的边如何设置？要求：（1）掌握在图的邻接矩阵和邻接表存储结构实现图的基本运算的算法。（2）学习使用图算法解决应用问题的方法。二、实验环境(实验设备)中文五号宋体，英文五号Times new roman字体，1.25倍行距硬件：微型计算机软件：Windows 操作系统、Micro

3、soft Visual C+6.0 三、实验原理及内容1、类和类的层次结构Queueabstrat+ virtual void EnQueue( T &x)=0; + virtual void DeQueue()=0+ virtual bool IsEmpty() const=0 + virtual bool IsFull() const=0+ virtual T Front()=0 SeqQueue-int front,rear;-int MaxSize;-T *q;+ SeqQueue()+SeqQueue()+ void EnQueue( T &x)+ void DeQu

4、eue()+ T Front()+ bool IsEmpty() const+ bool IsFull() constT GraphQueue 父类： 父类： LGraphSeqQueue 子类： 子类:继承关系 继承关系Graphabstract#int n#int e+virtual Graph()+virtual ResultCode Insert(int u, int v, T& w)=0+virtual ResultCode Remove(int u, int v)=0+virtual bool Exist(int u, int v)const=0LGraph#ENode&l

5、t;T>* a+LGraph(int mSize)+LGraph()+ResultCode Insert(int u, int v, T& w)+ResultCode Change(int u,int v,T& w)+ResultCode Remove(int u, int v)+bool Exist(int u, int v)const+int Vertices()+void Output()ExtLGraph+ExtLGraph(int mSize):LGraph<T>(mSize)+void DFS(); +void BFS();+void CallIn

6、Degree(int* InDegree);+void TopoSort(int* order);+int Choose(int *d,bool* s);+void Dijkstra(int v,T* d,int* path);+void BetweenMinPath(int a,int b);-void DFS(int v, bool* visited);-void BFS(int v, bool* visited);实 验 报 告2、算法及数据结构(1)图的宽度优先遍历所使用的队列结构 0 1 2 3 4 5 6 7=maxSize-1 f r 队列结构示意图(2)图的结构示意 70 10

7、 35 20 30 (3)图的邻接表表示 (4)图的邻接矩阵表示 0 1 2 3 4 50 0 0 0 0 0 01 1 0 1 0 0 12 0 1 0 0 1 13 1 0 0 0 1 04 0 1 0 0 1 15 1 1 0 0 0 03、函数流程示意图开始对象调用函数BFS（）判断对象是否为空 是 否将图的顶点存入队列判断队列是否为空 是 否按照FIFO原则，输出顶点值后出队判断出队顶点是否有未访问顶点 否 是未访问顶点入队结束实现按层次遍历函数BFS()流程示意图实 验 报 告4、核心算法代码（1）图的宽度优先遍历，使用邻接矩阵实现void MGraph<T>:BFS(

8、) bool* visited =new booln; for(int i= 0; i <n; i+) visitedi =false; for(int i= 0; i <n; i+) if(!visitedi) BFS(i, visited); delete visited;void MGraph<T>:BFS(int v, bool* visited)SeqQueue<int> q(20);visitedv =true; cout << " " << v;q.EnQueue(v);while(!q.IsEmpt

9、y()q.Front(v);q.DeQueue();for(int i=0;i<n;i+)if(!visitedi)&&(avi!=INFTY) /当顶点未被访问以及两顶点间存在路径才访问visitedi=true;cout<<" "<<i;q.EnQueue(i);（2）图的深度优先遍历，使用邻接矩阵实现void MGraph<T>:DFS() bool* visited =new booln; for(int i= 0; i <n; i+) visitedi =false; for(int i= 0; i

10、<n; i+) if(!visitedi) DFS(i, visited); delete visited;template<class T>void MGraph<T>:DFS(int v, bool* visited) visitedv =true; cout << " " <<v; for(int i=0;i<n;i+) if(!visitedi)&&(avi!=INFTY) DFS(i,visited); （3）Djikstra算法void ExtLGraph<T>:Dijkst

11、ra(int v,T* d,int* path)int i,k,w1;ENode<T>* p=av;if(v<0|v>n-1) cout<<"OutOfBounds!"<<endl;bool* s=new booln;for(i=0;i<n;i+)si=false;if(i=v) di=0;else di=INFTY;pathi=-1;while(p)i=p->adjVex;di=p->w;pathi=v;p=p->nextArc;p=NULL;sv=true;dv=0;for(i=1;i<n;i

12、+)k=Choose(d,s);sk=true;p=ak;for(;p;p=p->nextArc)w1=p->adjVex;if(!sw1&&dk+p->w<dw1)dw1=dk+p->w;pathw1=k;（4）求图的任意两点之间的最短路径算法void ExtLGraph<T>:BetweenMinPath(int a, int b)int x=this->n;int y=b;if(a<0|a>x|b<0|b>x) /对输入数据进行越界判断cout<<"OutofBounds!&qu

13、ot;<<endl;int* d=new intx;int* path=new intx;this->Dijkstra(a,d,path);if(pathb=-1)cout<<"The path is NotPresent!"<<endl;return;elseint n=0;int* pathmin=new int; /申请动态一维数组由于存储路径while(pathy!=-1)pathminn=pathy;n+;y=pathy;n=n-2;cout<<"the path is: ("<<

14、;a;for(;n>=0;n-) /倒序输出路径数组，结果为顶点a到b的路径cout<<" "<<pathminn; cout<<" "<<b<<")"<<endl;cout<<"the distance is:"<<db<<endl;（5）主函数程序int main(void)int b=10;cout<<"请输入将要建立图的顶点数："<<endl;cin&

15、gt;>b;ExtLGraph<int> lg(b);enum ResultCode status=Failure;int u=0,v=0,w=0,a=0;int* order=new intb;system("color 70");menu(); while (a!=7) cin>>a;switch(a) case 1:cout<<"请输入始点u和终点v以及权值w:"<<endl;while(!(u<0|v<0|w<0)cin>>u>>v>>w;

16、status=lg.Insert(u,v,w);if(status=Success)/cout<<"Success!"<<endl;else if(status=Duplicate)cout<<"the path is exist!"<<endl<<"Please input again!"<<endl;cin>>u>>v>>w;else if(status=Failure&&!(u<0|v<0|w&

17、lt;0)cout<<"Input Error!"<<endl;cin>>u>>v>>w;system("pause");system("cls");menu(); break; case 2:cout<<"请输入始点u和终点v以及要改变的权值w:"<<endl;cin>>u>>v>>w;status=lg.Change(u,v,w);if(status=Success)/*cout<<

18、;"Success!"<<endl;*/else cout<<"The path is NotPresent!"<<endl;system("pause");system("cls");menu();break;case 3: cout<<"请输入要删除的始点u和终点v:"<<endl;cin>>u>>v;status=lg.Remove(u,v);if(status=Success)cout<<&q

19、uot;Success!"<<endl;else cout<<"The path is NotPresent!"<<endl<<"Remove Failure!"<<endl;system("pause"); system("cls");menu(); break; case 4:cout<<"BFS :"<<endl; lg.BFS();cout<<endl<<"DF

20、S :"<<endl;lg.DFS();cout<<endl;system("pause");system("cls");menu(); break;case 5:cout<<"the TopoSort is: "lg.TopoSort(order);cout<<endl;system("pause");system("cls");menu(); break;case 6: cout<<"请输入要查询最短路径的始点u和终点v:"<<endl;cin>>u>>v;lg.BetweenMinPath(u,v);system("pause");system("cls");menu();