1、图实 验 报 告（2015/2016学年 第2学期）课程名称数据结构A实验名称图的基本运算及飞机换乘次数最少问题实验时间2016年5月23日指导单位计算机科学与技术系指导教师骆健学生姓名班级学号学院(系) 管理学院专 业信息管理与信息系统图的基本运算一、 问题陈述1 验证教材中关于邻接矩阵和邻接表存储结构实现图的基本运算的算法2 在邻接矩阵存储结构上实现图的深度和广度优先遍历算法3 设计主函数测试上述运算二、概要设计编写构造函数MGraph，Insert()插入函数，Remove()删除函数，Exist()查找函数，扩充MGraph类，在扩充类上增加DFS()和BFS()函数进行深度遍历和广度
2、遍历。三、 详细设计四、程序代码#includeconst int INFTY=2147483640;enum ResultCodeUnderflow,Duplicate,Failure,Success,NotPresent;templateclass Graphpublic: 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=0;protected: int n,e;templateclass
3、SeqQueuepublic: SeqQueue(int mSize); SeqQueue()delete q; bool IsEmpty() const return front=rear; bool IsFull() constreturn (rear+1)%maxSize=front; bool Front(T &x)const; bool EnQueue(T x); bool DeQueue(); void Clear()front=rear=0;private: int front,rear; int maxSize; T*q;templateSeqQueue:SeqQueue(in
4、t mSize) maxSize=mSize; q=new TmaxSize; front=rear=0;templatebool SeqQueue:Front(T &x)const if(IsEmpty() return false; x=q(front+1)%maxSize; return true; templatebool SeqQueue:EnQueue(T x)/在队尾插入 if(IsFull() coutFullendl; return false; qrear=(rear+1)%maxSize=x;return true;templatebool SeqQueue:DeQueu
5、e()/删除队头元素 if(IsEmpty() coutUnderflowendl; return false; front=(front+1)%maxSize; return true;templateclass MGraph:public Graph/邻接矩阵类public:MGraph(int mSize,const T& noedg);MGraph();ResultCode Insert(int u,int v,T&w);ResultCode Remove(int u,int v);bool Exist(int u,int v)const;void DFS();void BFS();p
6、rotected:T*a;T noEdge;void DFS(int v,bool*visited);void BFS(int v,bool*visited);templateMGraph:MGraph(int mSize,const T&noedg)/构造函数n=mSize;e=0;noEdge=noedg;a=new T*n;for(int i=0;in;i+)ai=new Tn;for(int j=0;jn;j+)aij=noEdge;aij=0;templateMGraph:MGraph()/析构函数for(int i=0;in;i+)delete ai;delete a;templa
7、teResultCode MGraph:Insert(int u,int v,T&w)/插入函数if(u0|vn-1|vn-1|u=v)return Failure;if(auv!=noEdge)return Duplicate;auv=w;e+;return Success;template ResultCode MGraph:Remove(int u,int v)/删除函数if(u0|vn-1|vn-1|u=v)return Failure;if(auv=noEdge)return NotPresent;auv=noEdge;e-;return Success;templatebool M
8、Graph:Exist(int u,int v)const/判断边是否存在if(u0|vn-1|vn-1|u=v|auv=noEdge)return false;return true;templatevoid MGraph:DFS()/深度遍历bool *visited=new booln;for(int i=0;in;i+)visitedi=false;for(i=0;in;i+)if(!visitedi)DFS(i,visited);deletevisited;template void MGraph:DFS(int v,bool *visited) visitedv=true; cou
9、t v; for(int i=0;in;i+) if(avi!=noEdge&avi!=0&!visitedi) DFS(i,visited);templatevoid MGraph:BFS() /广度遍历 bool *visited=new booln; for(int i=0;in;i+) visitedi=false; for(i=0;in;i+) if(!visitedi) BFS(i,visited); deletevisited;templatevoid MGraph:BFS(int v,bool *visited) SeqQueue q(n); visitedv=true; co
10、ut v; q.EnQueue(v); while(!q.IsEmpty() q.Front(v); q.DeQueue(); for(int i=0;in;i+) if(avi!=noEdge&avi!=0&!visitedi) visitedi=true; cout i; q.EnQueue(i); template /结点类 class ENodepublic: ENode() nextArc=NULL; ENode(int vertex,T weight,ENode *next) adjVex=vertex; w=weight; nextArc=next; int adjVex; T
11、w; ENode *nextArc;templateclass LGraph:public Graph /邻接表类public: LGraph(int mSize); LGraph(); ResultCode Insert(int u,int v,T&w); ResultCode Remove(int u,int v); bool Exist(int u,int v)const;protected: ENode*a;template LGraph:LGraph(int mSize)/构造函数 n=mSize; e=0; a=new ENode*n; for(int i=0;in;i+) ai=
12、NULL; template LGraph:LGraph() ENode *p,*q; for(int i=0;inextArc; delete q; q=p; delete a; template bool LGraph:Exist(int u,int v)const/判断边是否存在 if(u0|vn-1|vn-1|u=v) return false; ENode*p=au; while(p&p-adjVex!=v) p=p-nextArc; if(!p) return false; else return true;templateResultCode LGraph:Insert(int
13、u,int v,T&w)/插入 if(u0|vn-1|vn-1|u=v) return Failure; if(Exist(u,v) return Duplicate; ENode*p=new ENode(v,w,au);au=p;e+;return Success;templateResultCode LGraph:Remove(int u,int v) /删除 if(u0|vn-1|vn-1|u=v) return Failure;ENode*p=au,*q;q=NULL;while(p&p-adjVex!=v) q=p; p=p-nextArc;if(!p)return NotPrese
14、nt;if(q) q-nextArc=p-nextArc;elseau=p-nextArc;delete p;e-;return Success;int main() /主函数 int n,g,operate;coutn;MGraphA(n,INFTY);LGraphB(n);coutg;int*a=new intg;int*b=new intg;int*w=new intg;for(int i=0;ig;i+)coutaibiwi;A.Insert(ai,bi,wi); B.Insert(ai,bi,wi);cout该图的深度优先遍历为:endl;A.DFS();coutendl;cout该
15、图的广度优先遍历为：endl;A.BFS();coutendl;dodo coutoperate;while(operate!=1&operate!=2&operate!=2);if(operate=1) coutcd;if(A.Exist(c,d)cout邻接矩阵中该边存在！endl;elsecout邻接矩阵中该边不存在！endl;if(B.Exist(c,d)cout邻接表中该边存在！endl;elsecout邻接表中该边不存在！endl;else if(operate=2)coutef;if(A.Remove(e,f)=Success)cout邻接矩阵中删除该边成功！endl;else
16、if(A.Remove(e,f)=NotPresent)cout邻接矩阵中该边不存在！endl;elsecout输入错误！endl;if(B.Remove(e,f)=Success)cout邻接表中删除该边成功！endl;else if(B.Remove(e,f)=NotPresent)cout邻接表中该边不存在！endl;elsecout邻接表中输入错误！endl;cout删除后该图的深度优先遍历为：endl;A.DFS();coutendl;cout删除后该图的广度优先遍历为：endl;A.BFS();else if(operate=3) coutendl; return 0;while(
17、0=0);五、测试与调试六、实验小结本次实验很难，运行成功后不仅加深了我对图的理解，更加增长了我的士气，那种敢于解决问题的勇气，以及解决问题的方法。在进行编程时，不可能一次成功，要勤加注释，方便在修正错误时进行更改。飞机最少换乘次数问题：一、 问题陈述设有n个城市，编号为0n-1,m条航线的起点和终点由用户输入提供。寻找一条换乘次数最少的线路方案。二、 概要设计实用有向图表示城市间的航线，航线权值是零，使用Dijkstra算法实现求换乘最少方案。三、 详细设计四、 程序代码#include #includeconst int INF=2147483647;enum ResultCodeUnde
18、rflow,Duplicate,Failure,Success,NotPresent,OutOfBounds;templateclass Graph /抽象类 public: 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=0; protected: int n,e;templateclass MGraph:public Graph /邻接矩阵类public: MGraph(int mSize,
19、const T noedg); MGraph(); ResultCode Insert(int u,int v,T w); ResultCode Remove(int u,int v); bool Exist(int u,int v)const; int Choose(int* d,bool* s); void Dijkstra(int v,T* d,int* path);protected: T*a; T noEdge;templateMGraph:MGraph(int mSize,const T noedg) n=mSize; e=0; noEdge=noedg; a=new T*n; f
20、or(int i=0;in;i+) ai=new Tn; for(int j=0;jn;j+) aij=noEdge; aii=0; templateMGraph:MGraph() for(int i=0;in;i+) delete ai; delete a;templateResultCode MGraph:Insert(int u,int v,T w) if(u0|vn-1|vn-1|u=v) return Failure; if(auv!=noEdge) return Duplicate; auv=w; e+; return Success;template ResultCode MGr
21、aph:Remove(int u,int v) if(u0|vn-1|vn-1|u=v) return Failure; if(auv=noEdge) return NotPresent; auv=noEdge; e-; return Success;templatebool MGraph:Exist(int u,int v)const if(u0|vn-1|vn-1|u=v|auv=noEdge) return false; return true;templateint MGraph:Choose(int* d,bool* s) /求最小di int i,minpos; T min; mi
22、n=INF; minpos=-1;for(i=0;in;i+) if(di=min&!si) min=di; minpos=i; return minpos;templatevoid MGraph:Dijkstra(int v,T* d,int* path)/迪杰斯特拉算法 int i,k,w; if(vn-1) throw OutOfBounds; bool* s=new booln; for(i=0;in;i+) si=false; di=avi; if(i!=v&diINF) pathi=v; else pathi=-1; sv=true; dv=0;for(i=1;in;i+) k=C
23、hoose(d,s); sk=true; for(w=0;wn;w+) if(!sw&(dk+akw)dw) dw=dk+akw; pathw=k; int main() int n,m; coutn; coutm; MGraphA(n,INF); int c,f; cout请输入每条航线的起点和终点：endl; for(int i=0;im;i+) cout第i+1cf; A.Insert(c,f,1); char s;do int v,w; coutvw; while(v0|wn-1|vn-1) coutvw; int* b=new intn;int* d=new intn;int* path=new intn;A.Dijkstra(v,d,path);int e=n-1;for(int j=0;jn;j+) bj=-2;if(w!=v) j=w; while(pathj!=-1) be=pathj; e-; j=pathj; if(e=n-1|dj=INF) cout该路间无线路！endl; else cout从v到w的换乘次数最小的线路方案为：; for(int k=0;kn;k+) if(bk!=-2)coutbk,;
