Prim（普里姆）算法求最小生成树（邻接矩阵） |
您所在的位置：网站首页 › kruskal算法求最小生成树距离矩阵结果代表什么 › Prim（普里姆）算法求最小生成树（邻接矩阵） |
Prim（普里姆）算法求最小生成树（邻接矩阵）
|
功能： 1.列出目标系统具有的各个功能，并简述其作用 建立无向图： 输入点的数目和标识、边的数目及其权值，使用二维数组的方式建立无向图并用邻接矩阵的方式进行存储。 找出最小生成树： 从输入的起始点开始，使用Prim算法来寻找最小生成树，并输出树的结点和边。 构造辅助数组： 设置一个一维数组每寻找一个顶点，清空一次，得到最小权值的顶点下标。 画出连通图： 使用EasyX画出之前输入的无向图及标记边的权值。 演示Prim算法： 逐步演示Prim算法的寻找过程，并把得到的最小生成树用蓝色进行标记，辅以文字说明。 画出最小生成树： 对最小生成树进行重构得到MST。 2.列出目标系统计划完成的界面样式及操作 方案选择： 1、完成目标系统计划采用数据结构的逻辑结构； 数据结构：无向图——使用邻接矩阵来存储无向图。 逻辑结构：图形结构——因为图形结构的元素之间的关系是邻接的。 2、完成目标系统计划采用的存储结构。 存储结构：顺序存储结构——使用二维数组来存储邻接矩阵。 2、说明目标系统的时间特性。 使用Prim算法在邻接矩阵中求最小生成树，设顶点数为n，时间复杂度为O(n²)。 响应时间：小于1ms； 更新处理时间：大约1μs； 数据的转换和传送时间：小于1μs； 运行时间：大约1μs。 主要开发思路： 将项目分为三大模块：无向图模块、Prim算法模块、演示动画模块。 （1）无向图模块： 通过顶点的个数和边及其权值，使用二维数组来构造邻接矩阵，使用邻接矩阵来存储无向图，包括了顶点和边的信息的输入。 （2）Prim算法模块： 通过无向图模块得到一个邻接矩阵，使用Prim算法在邻接矩阵中找到最小生产数，并输出数的边及其两个端点，为动画演示求得结果。 （3）动画演示模块： 由邻接矩阵来画出无向图，通过Prim算法的每一步求得符合条件的顶点及边，并将其输出在画面，一步一步直到寻找到整颗完整的最小生成树。 工作重点： Prim算法：单独使用一个数组，来存储最小权值边的顶点，来一步步求出最小生成树。 动画演示：在无向图中，根据Prim算法来一步步演示求得的顶点和边，最后得到最小生成树。 技术路线：如采用C/S模式，使用C++语言编程实现。主要涉及的技术有：MFC中各种控件，图形绘制，窗口拆分，自定义消息，线程同步，数据共享锁等。 使用C++语言编程实现。 主要涉及的技术有：EasyX的图片读取、窗口定义、图形绘制等；多函数的互相调用，宏定义等。 开发环境及工具： 系统核心算法采用Visual Studio开发平台，界面采用EasyX来进行动画演示。 三、软件结构设计1、软件功能结构 2.2 构造辅助数组： 模块全名：int minimun(MGraph G, closedge close); 初始条件：closedge a_close为空 过程：设置一个一维数组每寻找一个顶点，清空一次，得到最小权值的顶点下标。 操作结果： closedge a_close每寻找一个顶点，清空一次，得到最小权值的顶点下标 2.3 PRIM算法求最小生成树： 模块全名：void miniSpanTreePrim(MGraph G, VertexType u); 初始条件：已知起始顶点的下标，closedge a_close为空。 过程：从输入的起始点开始，使用Prim算法来寻找最小生成树，并输出树的结点和边。 操作结果：每一次得到一个最小权值边的终止顶点的下标。 2.4 画出连通图： 模块全名：void cartoon_DRAW(); 初始条件：画布为空，背景为白，画线颜色为黑色。 过程：使用EasyX画出之前输入的无向图及标记边的权值。 操作结果：画出之前输入的无向图及标记边的权值。 2.5演示PRIM算法： 模块全名：void cartoon_TEXT(); 初始条件：背景为白，画线颜色为蓝色，画布有无向图一个。 过程：逐步演示Prim算法的寻找过程，并把得到的最小生成树用蓝色进行标记，辅以文字说明。 操作结果：逐步演示Prim算法的寻找过程，并把得到的最小生成树用蓝色进行标记，辅以文字说明。 2.6画出最小生成树： 模块全名：void cartoon_MST(); 初始条件：得到了无向图及其最小生成树权值的边和过程的文字说明。 过程：对最小生成树进行重构得到MST。 操作结果：对最小生成树进行重构得到MST。 四、数据结构设计1、构造无向图： 数组：使用二维数组可以存储邻接矩阵，无向图可以用邻接矩阵表示，且邻接矩阵在Prim算法中寻找更加方便，可以节约空间。 定义： typedef struct { ARCType adj; //对于无权图，用 1 或 0 表示是否相邻；对于带权图，直接为权值 }ArcCell, AdjMatrix[MAX_SIZE][MAX_SIZE]; typedef struct { VertexType vexs[MAX_SIZE]; //存储图中顶点数据 AdjMatrix arcs; //二维数组，记录顶点之间的关系 int vexnum, arcnum; //记录图的顶点数和边数 }MGraph;2、构造辅助数组： 数组：使用一维数组来存储寻找的顶点的边，使用遍历寻找出权值最小的边，对应的下一个顶点。 定义： typedef struct { VertexType adjvex; //记录权值最小的边的起始点 ARCType lowcost; //记录该边的权值 }closedge[MAX_SIZE];3、PrIM算法求最小生成树： 数组：利用邻接矩阵和辅助数组来求得最小生成树，从起始点开始，寻找出权值最小的边及其及其对应的点，再寻找下一个顶点 五、关键算法设计1、PRIM算法求最小生成树算法
|
性能： 1、说明目标系统的数据处理能力。 一次只能处理一个无向图，无向图使用邻接矩阵来存储，用二维数组来实现，即无向图的顶点数目不超过10000。
2、功能模块说明 2.1 构造无向图 模块全名：void CreateUDN(MGraph *G); 初始条件：MGraph、ArcCell两个结构体为空，无向图的大小未定义。 过程：输入点的数目和标识、边的数目及其权值，使用二维数组的方式建立无向图并用邻接矩阵的方式进行存储。 操作结果：定义无向图的顶点数和边数，并用邻接矩阵存储了无向图的顶点及其边的权值。
【本文地址】
今日新闻 |
推荐新闻 |