最小生成树问题的算法实现及复杂度分析—天津大学计算机科学与技术学院(算法设计与分析)

算法设计与分析课程设计报告算法设计与分析课程设计报告 学学 院院 计算机科学与技术计算机科学与技术 专专 业业 计算机科学与技术计算机科学与技术 年年 级级 2011 姓姓 名名 XXX 学学 号号 2013 年年 5 月月 19 日日 题目 题目 最小生成树问题的算法实现及复杂度分析 摘要 摘要 该程序操作简单 具有一定的应用性 数据结构是计算机科学的算 法理论基础和软件设计的技术基础 在计算机领域中有着举足轻重的作用 是 计算机学科的核心课程 而最小生成树算法是算法设计与分析中的重要算法 最小生成树也是最短路径算法 最短路径的问题在现实生活中应用非常广泛 如邮递员送信 公路造价等问题 本设计以 Visual Studio 2010 作为开发平台 C C 语言作为编程语言 以邻接矩阵作为存储结构 编程实现了最小生成树算 法 构造最小生成树有很多算法 本文主要介绍了图的概念 图的遍历 并分 析了 PRIM 经典算法的算法思想 最后用这种经典算法实现了最小生成树的生 成 引言 引言 假设要在 n 个城市之间建立通信联络网 则连接 n 个城市只需要 n 1 条线路 这时 自然会考虑这样一个问题 如何在节省费用的前提下建立 这个通信网 自然在每两个城市之间都可以设置一条线路 而这相应的就要付 出较高的经济代价 n 个城市之间最多可以设置 n n 1 2 条线路 那么如何 在这些可能的线路中选择 n 1 条使总的代价最小呢 可以用连通网来表示 n 个 城市以及 n 个城市之间可能设置的通信线路 其中网的顶点表示城市 边表示 两个城市之间的线路 赋予边的权值表示相应的代价 对于 n 个顶点的连通网 可以建立许多不同的生成树 每一个生成树都可以是一个通信网 现在要选择 这样一棵生成树 也就是使总的代价最小 这个问题便是构造连通网的最小代 价生成树 简称最小生成树 的问题 最小生成树是指在所有生成树中 边上 权值之和最小的生成树 另外最小生成树也可能是多个 他们之间的权值之和 相等 一棵生成树的代价就是树上各边的代价之和 而实现这个运算的经典算 法就是普利姆算法 正文正文 普里姆 普里姆 PrimPrim 算法思想 算法思想 普里姆算法则从另一个角度构造连通网的最小生成树 它的基本思想是 首先选取图中任意一个顶点 v 作为生成树的根 之后继续往生成树中添加顶点 w 则在顶点 w 和顶点 v 之间必须有边 且该边上的权值应在所有和 v 相邻 接的边中属最小 在一般情况下 假设图 G V E 中已落在生成树上的顶点集 为 U 则尚未落在生成树上的顶点集为 V U 则从 V U 顶点集中选取加入生 成树的顶点 w 应满足下列条件 它和生成树上的顶点之间的边上的权值是在联 接这两类顶点的所有边中权值属最小 从 上述生成树的构造过程中回还可以发现一点 即每个顶点都是通过 一 条边 加入到生成树上的 因此对集合 V U 中的每个顶点 当它和集合 U 中的 顶点有一条以上的边相连时 只需要保留一条权值最小的边即可 由此 在普 里姆算法中需要附设一个辅助数组 closedge 以记录从集合 U 到集合 V U 中 每个顶点当前的权值最小边 普里姆算法构造最小生成树的过程 普里姆 普里姆 PrimPrim 算法设计 算法设计 一 定义模块 一 定义模块 1 头文件 新类型及固定值定义 本程序可接受的最大顶点数为 20 个 没有 连接的点之间 用 100 表示其权值 include using namespace std define MAX VERTEX NUM 20 最大顶点数 define QM 100 最大值 define OK 1 define ERROR 0 int visited MAX VERTEX NUM typedef int VertexType typedef int VRType 2 首先设计图的存储模块 即定义类型 本程序采用的图定义是无向图的定义 方式 存储模块采用邻接矩阵 便于查找 typedef int VertexType typedef int VRType typedef struct ArcCell 邻接矩阵的值 int adj ArcCell AdjMatrix MAX VERTEX NUM MAX VERTEX NUM typedef struct VertexType vexs MAX VERTEX NUM 顶点向量 AdjMatrix arcs 邻接矩阵 int vexnum arcnum 图的当前顶点数和弧数 MGraph 3 在实现最小生成树算法时 定义辅助数组 进行判断遍历 typedef struct VertexType adjvex VRType lowcost closedge MAX VERTEX NUM 4 最后生成最小生成树时 采用辅助数组进行结果的记录 typedef struct VertexType head VRType last int weight result MAX VERTEX NUM 二 实现模块 函数 二 实现模块 函数 1 顶点查找函数 因为顶点的值和数组位置的下标不一定相等 所以加入 顶点查找函数 返回顶点的值 便于结果显示 区分指针与内容 使思 路更为清晰 int LocateVex MGraph for k 0 k G vexnum k if G vexs k v return k return 1 没有这个顶点 2 无向图的创建函数 int CreateUDN MGraph int weight VertexType v1 v2 cout 输入无向图的顶点数和弧数 G vexnum G arcnum for i 0 i G vexnum i for j 0 j G vexnum j G arcs i j adj QM cout 输出网的 G vexnum 个顶点 限数字 endl for i 0 i G vexs i cout 建立弧 请输入 G arcnum 条弧的顶点和权值 v1 v2 w endl for k 0 k v1 v2 weight i LocateVex G v1 j LocateVex G v2 if i 0 j 0 return ERROR G arcs i j adj weight G arcs j i adj G arcs i j adj return OK 3 最小生成树建立主程序 采用借助辅助数组的方式 对于辅助的数组 以邻接表的选择点加入该数组 然后查找数组中权值最小 且未被选中 的顶点 然后返回该边 加入最小生成树中 void MiniSpanTree PRIM MGraph G VertexType u closedge dge 申请数组 result pax int k j i lax time 0 x y lax G vexnum 1 k LocateVex G u 确定初始结点的下标 for j 0 j G vexnum j 初始化临时辅助数组 if j k dge j lowcost G arcs k j adj 数组中的 adjvex 均为 u 即从 u 开始到所有其他结点的权值赋给了数组中 lowcost dge j adjvex u 数组中的下标 起箭头的作用 即它是边的第二个尾结点 dge k lowcost 0 u 在数组 dge 的下标即为 k 故自身到自身权值标为 0 也表示纳入点集 V for i 1 i G vexnum i k minimun G dge 在 dge 数组中找 到最小的一条边 并返回尾结点的下标 cout K 的寻求结果为 数组 dge 中的下标 k endl cout dge k adjvex G vexs k endl 输出 边 pax time head dge k adjvex pax time last G vexs k x LocateVex G dge k adjvex y LocateVex G G vexs k pax time weight G arcs x y adj time dge k lowcost 0 把 下标为 k 的结点纳入点集 V 标注权值为 0 for j 0 j G vexnum j if G arcs k j adj dge j lowcost 新加入的点到其他各点的权值比原来的权值 更小 则替换 采取遍历的方法 dge j lowcost G arcs k j adj dge j adjvex G vexs k 点的 名字进行修改 cout 最小生成树为 endl 起点 终点 权值 endl for time 0 time lax time cout pax time head pax time last pax time weight endl 4 辅助生成最小生成树的函数 int minimun MGraph G closedge F int i min for i 0 i G vexnum i if F i lowcost 0 break min i for i 0 i G vexnum i if F i lowcost 0 return min 数组的样式 j Lowcost adjvex 过程如下表 顶点标号都比图中的小 1 比如 v1 为 0 v2 为 1 这里首先 选择 v1 点 j012345 Lowcost0423100100 adjvex111111 从这个表格可以看到依附到 v1 顶点的 v3 的 Lowcost 最小为 2 那么选择 v3 选择了之后我们必须要更新 Lowcost 数组的值 因为记录从 U 到 V U 具有 最小代价的边 加入之后就会改变 新加入的点到其他各点的权值比原来的权 值更小 则替换 采取遍历的方法 j012345 Lowcost04011002 adjvex111416 Lowcost 0 为我们已经选出来的顶点 接着继续在 Lowcost 中选出值不为 0 的最小值 作为下一个最小生成树的点 这样一直选择下去直到选出所有的顶点 5 最小生成树建立 那么需要借用辅助数组 进行记录 int minimun MGraph G closedge F int i min for i 0 i G vexnum i if F i lowcost 0 break min i for i 0 i G vexnum i if F i lowcost 0 return min 6 调试时 加入的函数 输出邻接矩阵和辅助数组 进行查看和判断正误 void PrintMatrix MGraph printf 邻接矩阵为 n for i 0 i G vexnum i for j 0 j G vexnum j if G arcs i j adj QM cout G arcs i j adj else cout cout endl void printclosedge MGraph G closedge X 输出辅助建立最小 生成树数组 int i cout dge 数组值为 endl i for i 0 i G vexnum i cout i cout endl lowcost for i 0 i G vexnum i cout X i lowcost cout endl adjvex for i 0 i G vexnum i cout X i adjvex 7 主程序 void main MGraph G VertexType u G vexnum G arcnum 0 CreateUDN G PrintMatrix G cout u MiniSpanTree PRIM G u system pause 普里姆 普里姆 PrimPrim 算法分析 算法分析 Prim 算法的时间复杂度主要是在双重循环构造最小生成树的过程中 设图 的顶点数为 n 则双重循环的时间复杂度为 O n2 在生成最小生成树的过程中 增加了两个数组 closedge 和 result 数组 用来记录所选顶点的全趋结点 故空间复杂度为 O 2n 普里姆算法的时间复杂度与边数 e 无关 该算法更适 合于求边数较多的带权无向连通图的最小生成树 普里姆 普里姆 PrimPrim 算法实验结果 算法实验结果 采用的数据 采用的数据 6 11 1 2 3 4 5 6 1 2 4 1 4 3 1 3 2 2 5 3 2 4 4 2 3 5 3 4 1 3 6 2 4 5 6 4 6 2 5 6 4 1 实验结果 实验结果 图表分析 图表分析 2 4 2 3 5 4 1 3 2 2 6 4 a b 2 2 1 1 1 2 4 3 1 2 4 3 5 6 1 234 4 5 6 1 2 4 1 2 c d 4 4 2 2 1 1 2 3 2 e f 结论与展望 结论与展望 运用 prim 算法构造图的最小生成树 使生成树的权值和 达到最小 即耗费最 小 这里选择贪心策略 从一个顶点出发 选择到剩余顶点的边权值最小的顶 点 将之并入到所够造的生成树之中 同时修改剩下的顶点到生成 树的权值 再从剩余顶点中继续选择到生成树耗费最小的顶点 继续并入该顶点 直到所 有的