图的各结点连线间存在权值,寻找一种访问路径,使得访问各结点最终的路径的权值和最小,
最终访问路径和结点形成树的结构,即最小生成树
普里姆算法
主要思路:研究对象为结点,以某顶点为起点,逐步找各个顶点上最小权值的边来构建最小生成树
编程思路:新建一数组,初始化为起点(最小生成树的根结点)在邻接矩阵所在行的权值
找到该组权值最小值,最小权值下标即要选择路径的终点,同时也是接下来要比较的邻接矩阵权值行的行号,
将该最小权值置0,然后将新建数组与矩阵权值行比较,
相同位置,矩阵行若小于新建数组值,就将新建数组值替换为矩阵行的值,
再次寻找新建数组中的最小权值,重复以上步骤
代码链接
克鲁斯卡尔算法
主要思路:研究对象为边,将边集数组从小到大排序,依次取边集数组的元素,判断边与边是否形成环路,不会形成则选择该边构建最小树
代码链接