数据结构图实现介绍.docx

数据结构实验报告实验名称：实验二——图学生姓名：班级： 11111班内序号：学号：2014日期：1．实验要求根据图的抽象数据类型的定义，使用邻接矩阵或邻接表实现一个图。图的基本功能：1、图的建立2、图的销毁3、深度优先遍历图4、广度优先遍历图 5、使用普里姆算法生成最小生成树6、使用克鲁斯卡尔算法生成最小生成树7、求指定顶点到其他各顶点的最短路径8、其他：比如连通性判断等自定义操作编写测试main()函数测试图的正确性2. 程序分析基类-图（Graph）Graph() //图的初始化~Graph() //图的销毁Print() //图矩阵的打印vNum //顶点个数arc //邻接矩阵eNum //边的条数Empty(); //置空图DFS();//深度优先遍历BFS(); //广度优先遍历派生类-无向图（Ugraph）creatGraph(); Prim();Kruskal();isConnected()；派生类-有向图（Dgraph）creatGraph();FloydPath(); DijkstraPath(int); isConnected()；主函数-main()2.1 存储结构逻辑结构存储结构结构实现图顺序表一维数组2.2 关键算法分析算法【1】：creatGraph()算法功能：创建一个有向图或无向图算法基本思想：在堆在申请一个N*N的一维数组存储各边权值算法复杂度分析：N个顶点需要设置O(N*N)次代码逻辑：cinvNum,arc=new int[N*N],输入顶点数并建立邻接矩阵arc如果是无向图，则cinweight,arc[i][j]=arc[j][i]，并设定arc[i][i]=Max;同时，weight为0的同样设为Max;如果是有向图，则cinweight1weight2,arc[i][j]=weight1,arc[j][i]=weight2,并设定arc[i][i]=Max; 同时，weight为0的同样设为Max;记录有效边的条数eNum;算法【2】：DFS(int v),DFSing(int v,int *visited)算法功能：无向图的深度优先遍历算法基本思想：从图中任一顶点V出发，标记V已访问；访问V的第一个未访问的邻接点W,标记W为已访问；访问W的第一个未访问的邻接点U,标记U为已访问；若当前顶点没有未访问的邻接顶点，则回溯，继续深度遍历。算法复杂度分析：每访问一个顶点需要遍历一行N,遍历N个顶点则为O(N*N)代码逻辑：bool *visited=new int[vNum](=false);visited[v]=true //初始化for(j=0;jvNum;j++){If(arc[i][j]!=Max visited[j]==false) //避开间断边和已访问点Coutj; //输出节点visited[j]=true; //设置j为已访问DFSing(v,visited) //递归遍历}delete[]visited;算法【3】：BFS(int v)算法功能：无向图的广度优先遍历算法基本思想：从图中任一顶点V出发，标记V已访问；依次访问所有未被访问的邻接顶点V1,V2,V3…并标记分别从V1,V2,V3…出发并依次访问它们未被访问的邻接顶点反复1,2,3直到所有和V相通的顶点都被访问到算法复杂度分析：结合遍历一行及递归，时间复杂度为O(N+e)，空间则为O(N)代码逻辑：Bool *visited=new bool[vNum](=false);visited[v]=true;Int *queue =new int[vNum],f=0,r=0,queue[r++]=v;While(f!=r){Coutqueue[f++];For(i=0;ivNum;i++){If(arc[i][j]!=Max visited[j]==false)Queue[r++]=j;visited[j]=true;}}Delete[]queue;delete[]visited;算法【4】：Prim()算法功能：从顶点角度选出最小生成树算法基本思想：N个顶点分属两集合U和U-V，U包含已落树的顶点，U-V包含未落到树上的顶点。然后不断寻找U和U-V中各顶点间的最小权值边，直到所有顶点落到集合U中。算法复杂度分析：此算法需要两次循环遍历所有结点，时间复杂度为O(N*N)代码逻辑：Bool *U=new bool[vNum](=true);U[v]=false; //建立并初始化U集合和U-V集合的数组，这里用一个bool数组U[