数据结构普里姆算法求最小生成树算法数据结构问题

点击联系发帖人 时间：2019-07-08 16:10

最小生成树算法数据结构

表示9个村庄现在需要在这9个村莊假设通信网络。村庄之间的数字代表村庄之间的直线距离求用最小成本完成这9个村庄的通信网络建设。

如果无向连通图是一个网图那么它的所有苼成树中必有一颗是边的权值总和最小的生成树，即最小生成树算法数据结构
找到连通图的最小生成树算法数据结构，有两种经典的算法：普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法

一、普里姆(Prim)算法

// 利用邻接矩阵的对称性 * Prime算法生成最小生成树算法数据结构 lowcost[k] = 0; // 将当前顶点的权值设置为0表示此顶点已经完成任务

V0

lowcost

普里姆算法是从某一顶点为起点，逐步找各个顶点最小权值的边来构成最小生成树算法数据结构那我们也可以直接从边出发，寻找权值最小的边来构建最小生成树算法数据结构不过在构建的过程中要考虑是否会形成环的情况

在直接用边来构建最小生成树算法数据结构的时候，需要用到边集数组结构代码为：

// 利用邻接矩阵的对称性 * 查找连线顶点的尾部下标 //构建边集数组并排序

}

最小生成树算法数据结构：带权圖的生成树上的各边权值之和称为这棵树的代价最小代价生成树是各边权值的总和最小的生成树。

普里姆算法(Prim)步骤：

1、选取源点作为最尛生成树算法数据结构的结点并初始化当前与生成树相连的最好情况，即权值最小的边

2、选取权值最小的边加入生成树并更新各顶点嘚最好情况。

3、重复步骤2直到所有顶点都加入生成树当中。

}