数据结构上机报告4 图.doc

图4--数据结构上机报告数据结构上机4实现最短路径(单源、每对顶点)和最小生成树(Prim)算法。23、20155、一、需求分析构造一个图,实现单源最短路径和每对顶点之间的最短路径,并且实现最小生成树,将结果显示在屏幕上输出。输入数据类型:构造图的数据是整型数字。程序功能:输入或者从文件读取构造图的参数,进行构图,并计算出单源最短路径和每个顶点最短路径,实现最小生成树。测试数据:正确输入:错误输入:二、:classGraph{public:intnumVertex;intnumEdge;int*Mark;int*Indegree;Graph(intnumVert){//有参构造函数,动态创建标记和度的数组,初始化边数、度数和访问numVertex=numVert;numEdge=0;Indegree=newint[numVertex];Mark=newint[numVertex];for(inti=0;i0&&=0)returntrue;returnfalse;}virtualEdgeFirstEdge(intoneVertex)=0;//返回与顶点oneVertex相关联的第一条边virtualEdgeNextEdge(EdgepreEdge)=0;//返回与边PreEdge有相同关联顶点oneVertex的下一条边intEdgesNum()//返回图的边数{returnnumEdge;}intFromVertex(EdgeoneEdge)//返回边oneEdge的始点{;}oneEdge的终点//返回边intToVertex(EdgeoneEdge){;}的权//返回边oneEdgeintWeight(EdgeoneEdge){;}设置边的起虚函数,//virtualvoidsetEdge(intfrom,intto,intweight)=0;点终点以及权值,在子类实例化virtualvoiddelEdge(intfrom,intto)=0;};主程序流程:Main(错误输入选正确输入选错误选项正确选项选行三、详细设计1、实现ADT的数据类型:整型数字;2、算法描述:单源最短:初始集合S只包含源点s,即S={s}。设v是V中某顶点,把从s到v且中间只经过集合S中顶点的路径称“从源到v的特殊路径”,用一维数组D记录当前找到的从s到每个顶点的最短特殊路径长度。D初始,若s到v有弧,D[v]存弧的权值,否则存∞。取最小,每次从集合V-S中取出一个最短特殊路径长度最小的顶点u,将u加入集合S,修改权值(修改D中未求出的最短路径长度):由于引入u,对未求出最短路径的顶点i进行判断,若满足:D[i]>D[u]+W[u,i]则改为最短,令D[i]=D[u]+W[u,i]另设立存储最短路径中当前顶点前驱顶点域pre,用于存顶点u。每对顶点最短路径算法:递归地产生一个矩阵序列adj(0),adj(1),…,adj(k),…,adj(n)