数据结构图实现

1、北京邮电大学信息与通信工程学院数据结构实验报告实验名称： 实验二图学生姓名： 班 级： 11111班内序号： 学 号： 2014日 期： 1实验要求根据图的抽象数据类型的定义，使用邻接矩阵或邻接表实现一个图。图的基本功能：1、图的建立2、图的销毁3、深度优先遍历图4、广度优先遍历图 5、使用普里姆算法生成最小生成树6、使用克鲁斯卡尔算法生成最小生成树7、求指定顶点到其他各顶点的最短路径8、其他：比如连通性判断等自定义操作编写测试main()函数测试图的正确性2. 程序分析基类-图（Graph）² Graph() /图的初始化² Graph() /图的销毁² Pri

2、nt() /图矩阵的打印² vNum /顶点个数² arc /邻接矩阵² eNum /边的条数² Empty(); /置空图² DFS(); /深度优先遍历² BFS(); /广度优先遍历派生类-无向图（Ugraph）Ø creatGraph(); Ø Prim();Ø Kruskal();Ø isConnected()； 派生类-有向图（Dgraph）Ø creatGraph();Ø FloydPath(); Ø DijkstraPath(int); Ø

3、 isConnected()； 主函数-main()2.1 存储结构逻辑结构存储结构结构实现图顺序表一维数组2.2 关键算法分析算法【1】：creatGraph()算法功能：创建一个有向图或无向图算法基本思想：在堆在申请一个N*N的一维数组存储各边权值算法复杂度分析：N个顶点需要设置O(N*N)次代码逻辑：A. cin>>vNum,arc=new intN*N,输入顶点数并建立邻接矩阵arcB. 如果是无向图，则cin>>weight,arcij=arcji，并设定arcii=Max;同时，weight为0的同样设为Max;C. 如果是有向图，则cin>>w

4、eight1>>weight2,arcij=weight1,arcji=weight2,并设定arcii=Max; 同时，weight为0的同样设为Max;D. 记录有效边的条数eNum;算法【2】：DFS(int v),DFSing(int v,int *visited)算法功能：无向图的深度优先遍历算法基本思想：1. 从图中任一顶点V出发，标记V已访问；2. 访问V的第一个未访问的邻接点W,标记W为已访问；3. 访问W的第一个未访问的邻接点U,标记U为已访问；4. 若当前顶点没有未访问的邻接顶点，则回溯，继续深度遍历。算法复杂度分析：每访问一个顶点需要遍历一行N,遍历N个顶点则

5、为O(N*N)代码逻辑：A. bool *visited=new intvNum(=false);visitedv=true /初始化B. for(j=0;j<vNum;j+)If(arcij!=Max && visitedj=false) /避开间断边和已访问点Cout<<j; /输出节点visitedj=true; /设置j为已访问DFSing(v,visited) /递归遍历C. deletevisited;算法【3】：BFS(int v)算法功能：无向图的广度优先遍历算法基本思想：1. 从图中任一顶点V出发，标记V已访问；2. 依次访问所有未被访问的邻

6、接顶点V1,V2,V3并标记3. 分别从V1,V2,V3出发并依次访问它们未被访问的邻接顶点反复1,2,3直到所有和V相通的顶点都被访问到算法复杂度分析：结合遍历一行及递归，时间复杂度为O(N+e)，空间则为O(N)代码逻辑：A. Bool *visited=new boolvNum(=false);visitedv=true;B. Int *queue =new intvNum,f=0,r=0,queuer+=v;C. While(f!=r)Cout<<queuef+;For(i=0;i<vNum;i+)If(arcij!=Max && visitedj=f

7、alse)Queuer+=j;visitedj=true;D. Deletequeue;deletevisited;算法【4】：Prim()算法功能：从顶点角度选出最小生成树算法基本思想：N个顶点分属两集合U和U-V，U包含已落树的顶点，U-V包含未落到树上的顶点。然后不断寻找U和U-V中各顶点间的最小权值边，直到所有顶点落到集合U中。算法复杂度分析：此算法需要两次循环遍历所有结点，时间复杂度为O(N*N)代码逻辑：A. Bool *U=new boolvNum(=true);Uv=false; /建立并初始化U集合和U-V集合的数组，这里用一个bool数组U表示，Ui为true表明顶点i为U

8、-V集合，为false表明顶点i为U集合；B. Int min3;min2=Max;min0=min1=v;/设定一个数组min3,前两位保存最小边的两顶点，第3位保存边权值,将min2初始化为MaxC. For(找到U集合的顶点，即Ui=true)For(找到U-V集合的顶点，即Uj=false)If(arcij<min2)Min0=i;min1=j,min2=arcij;/更新数组min3)每次循环完后必能找到最小值，将j顶点从U-V集合中删除并添加到U集合，即Ui=false;D. 反复执行C步骤，N个顶点需要执行N-1次，用一个count变量和while循环计数。Whlie(co

9、unt!=N)count+;算法【5】：Kruskal()算法功能：从边的角度选出最小生成树算法基本思想：首先对边从小到大排序，然后依次挑取最小权值的边到生成树中，此过程里每添加一条新边需要判断是否会构成回路，一旦构成回路则放弃此边。算法复杂度分析：此算法主要来自于边的排序，时间复杂度为O(N*N)代码逻辑：A. 准备好struct Vedge int fromV,endV,weight;Vedge *edgelist=new VedgevNum.B. For(i=0;i<vNum;i+)For(j=0;j<vNum;j+;count+)Edgelistcount(fromV=i,

10、endV=j,weight=arcij;C. bubblesort(edgelist)，用冒泡排序边集数组，排序代码此处省略D. int *vset=new intvNum(0,1,2,3,N-1) /建立顶点集合数组vset并用for循环初始化为自然数列0,1,2,3N-1；E. for(i=0;i<eNum;i+)遍历边集数组edgelisti，If(vsetfromV=vsetendV) continue; /边两顶点同属一数组时跳过Cout<<fromV和endVFor(j=0;j<vNum;j+) /遍历vset集合更新信息 /将所有和顶点fromV具有相同集

11、合的点调整成endV的集合If(vsetj=vsetfromV) vsetj=vsetendVF. deleteedgelist;deletevset;算法【6】：FloydPath();算法功能：求出任意两顶点间的最短路径算法基本思想：1. 若<Vi,Vj>存在，则路径存在<Vi,Vj>；2. 若<Vi,Vl>，<Vl,Vj>存在，则存在路径<Vi,Vl,Vj>；3. 若<Vi,V2>，<V2,Vj>存在，则存在路径<Vi,V2,Vj>；依次类推，直到选出所有路径中的最小值。算法复杂度分析：核心的

12、3重循环每一层需遍历N次，则时间复杂度为O(N3)代码逻辑：int *dist(new intN*N)(arcN*N);int *path(new intN*N)(判断通路则设为arcij中的i,断路则设为Max);/-/以上为初始化路径矩阵for (int k = 0; k < vNum; k+) for (int i = 0; i < vNum; i+)for (int j = 0; j < vNum; j+) if (i = j) continue; /跳过自身到自身的回路if (distik+distkj < distij)distij = distik+dis

13、tkj;pathij = k; /此时k为i->j的中转顶点/-/以上Floyd核心的三重循环，k必须在外层输出路径矩阵diskij用两层for循环即可输出路径信息同Dijkstra算法deletedist;deletepath;deletestack;算法【7】：DijkstraPath(int)算法功能：求出一个顶点到其他顶点的最短路径算法基本思想：1. 首先找出源点能直达的最短路径顶点和边2. 然后以上一顶点为中转顶点，找出经过此中转顶点后的最短路径，此时如果从源点到目的点路径更短，则不必中转3. 重复执行2，直到找出所有顶点的路径为止。算法复杂度分析：每个顶点需要一次O(N)的迭

14、代，N个点需要N-1次，时间复杂度为O(N*N)代码逻辑：int *path = new intvNum(Max); /路径数组,初始化为Maxint *disk = new intvNum(Max); /路程数组,初始化为Maxbool *visited = new boolvNum(false); /访问数组,初始化为falsevisitedv = true; /设置源点为trueint minV(v), minDis(0), lastV(v), newDis;for (int count = 1; count != vNum; count+) /n个顶点需要n-1次迭代for (int

15、j = 0; j < vNum; j+)if (visitedj = true) continue;minV = j; /minV要在找最小前初始化为一个没被visit的顶点 if (arcik+arckj < diskj) /lastV表示当前节点的前驱 diskj = arcik+arckj; pathj = lastV;for (int j = 0; j < vNum; j+) /找最小路径和顶点if (visitedj = false && diskj < diskminV)minV = j;visitedminV = true; /更新最小顶点

16、，更新最短路径，更新末顶点minDis = diskminV;lastV = minV;/-/以上为得到单点出发到各顶点的最短路径cout << "下面输出v" << v << "与其他顶点的最短路径：" << endl;int p, *stack, top(-1),count(1); /使用一个临时栈将路径倒序输出stack = new intvNum;for (int i = 0; i < vNum; i+)if (pathi = Max) continue; /如果是断路，则不用输出路径p =

17、i;while (pathp != Max)stack+top = p; /前驱结点入栈p = pathp; /跳转到前驱结点cout << '(' << count+ << ") " << "v" << v << ""while (top != -1) /有栈将路径倒序输出cout << "->v" << stacktop- << ""cout << &

18、quot; | Distance = " << diski << endl;/-/以上为多此一举的输出路径deletestack;deletepath;deletevisited;deletedisk;2.3 其他编译环境Visual Studio 2013无穷大Max1061109567输出域宽sl5一维数组对应矩阵关系Matrixij=arck,k=i*N+j;3. 程序运行结果测试流程：按顺序执行以下流程1- 构建一个有向图Dgraph对象，输入一个无向图（课本P208图）；2- 打印邻接矩阵；3- 输出以各顶点为出发点的广度遍历；4- 输出以各顶点为出发点的深度遍历；5- 输出以各顶点为出发点的Dijkstra算法最短路径；6- 输出FloydPath算法的各顶点间的最短路径；7- (清屏)8- 构建一个无向图Ugraph对象，输入一个有向图（课本P207图）；9- 打印邻接矩阵；10- 输出以各顶点为出发点的广度遍历；11- 输出以各顶点为出发点的深度遍历；12- 任取一顶点按Prim算法生成最小生成树；13- 用Kruskal算法生成最小生成树，并与12的比较是否一致；14- 程序运行完毕。运行结果(图片太大，用链接存放)：有向图