图论-最小生成树prim算法（Java）
最小生成树需要一个加权连通图，连通图就是所有顶点都是连在一起的，从任意一个顶点，都能到达除本身外任意一个顶点
prim算法：将顶点分成两个集合 U和 V，U用来存放每次遍历得到的与U中顶点最小路径的邻接顶点，V用来存放U中没有的顶点。U初始化存放任意一个顶点，每次从V中遍历得到与U集合中的顶点最小路径的顶点后，放入U，将V中的对应顶点删除，当U存放到所有顶点后，最小生成树就得到了。
利用之前的类实现prim算法：
public void prim() {
//权最小的边
int[] minWeigth = new int[verticeSize];
//将任意一个点设为初始点，这边用第一个顶点
for (int i = 0; i < verticeSize; i++) {
minWeigth[i] = matrix[0][i];
}
//目前minWeigth中存放着第一个顶点的边的信息
int sum = 0;
for (int i = 0; i < verticeSize; i++) {//遍历每个顶点，第一个点可以在上面的循环处理
//存放最小边的信息
int min = MAX;
//存放最小边的邻接点
int mid = 0;
//获取下最小的边
for (int j = 0; j < verticeSize; j++) {
if (minWeigth[j] != 0 && minWeigth[j] != MAX && min > minWeigth[j]) {
//最小的边赋值
min = minWeigth[j];
//最小边的邻接点赋值为j
mid = j;
}
}
if (min == MAX) {//没有边了，直接退出循环
break;
}
sum += min;
//接下来改变最小边的集合值，因为集合新加了mid的顶点
minWeigth[mid] = 0;//设为0，因为新加了mid的顶点，下次mid顶点就可以剔除了
for (int j = 0; j < verticeSize; j++) {
//minWeigth中本身存放着最小边，只要将mid顶点的最小边集合和当前集合合并
if (minWeigth[j] != 0 && matrix[mid][j] < minWeigth[j]) {
minWeigth[j] = matrix[mid][j];
}
}
}
System.out.println(sum);
}
/**
* 和prim代码相同，注释更加容易理解
*/
public void prims() {
//将第一个顶点作为u的第一个顶点
//存放u到v所有顶点的距离
int[] dis = new int[verticeSize];
//用了第一个顶点，初始化下dis
for (int i = 0; i < verticeSize; i++) {
dis[i] = matrix[0][i];
}
//此时matrix[0][0]对应的值是0，我们用0表示已经该顶点在u集合中了
//用来最后打印下最小权
int sum = 0;
//接下来开始遍历每个顶点了 第一个顶点就没必要了
for (int i = 1; i < verticeSize; i++) {
int v = 0;
int min = MAX;
//获取u集合中，最小权的另一端顶点
for (int j = 0; j < verticeSize; j++) {
if (dis[j] != 0 && min > dis[j]) {
min = dis[j];
v = j;
}
}
//上面遍历，我们得到的下一次v中需要放入的顶点
if (min == MAX) {//所有dis集合中都是0，就是所有顶点都存在了
break;
}
//u中添加了新顶点，置为0
dis[v] = 0;
//记录下最小权，也可以做其他操作
sum += min;
//更新u集合中的距离
for (int j = 0; j < verticeSize; j++) {
if (dis[j] != 0) {//在集合内了，就不用操作了
if (dis[j] > matrix[v][j]) {
//dis[j]是原本u到j顶点的距离
//matrix[v][j]为v到j的距离
dis[j] = matrix[v][j];
}
}
}
}
System.out.println(sum);
}测试代码：
Graph graph = new Graph(7);
int[] v0 = new int[]{0, 50, 60, Graph.MAX, Graph.MAX, Graph.MAX, Graph.MAX};
int[] v1 = new int[]{50, 0, Graph.MAX, 65, 40, Graph.MAX, Graph.MAX};
int[] v2 = new int[]{60, Graph.MAX, 0, 52, Graph.MAX, Graph.MAX, 45};
int[] v3 = new int[]{Graph.MAX, 65, 52, 0, 50, 30, 42};
int[] v4 = new int[]{Graph.MAX, 40, Graph.MAX, 50, 0, 70, Graph.MAX};
int[] v5 = new int[]{Graph.MAX, Graph.MAX, Graph.MAX, 30, 70, 0, Graph.MAX};
int[] v6 = new int[]{Graph.MAX, Graph.MAX, 45, 42, Graph.MAX, Graph.MAX, 0};
graph.matrix[0] = v0;
graph.matrix[1] = v1;
graph.matrix[2] = v2;
graph.matrix[3] = v3;
graph.matrix[4] = v4;
graph.matrix[5] = v5;
graph.matrix[6] = v6;
graph.prim();结果：
257
本文参与?腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021/8/17 上，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读