建设银行官方网站是什么,企业网站设计与规划论文,游网站建设方案内容,表白网页制作免费网站题目: 寻宝
题目描述
在世界的某个区域#xff0c;有一些分散的神秘岛屿#xff0c;每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路#xff0c;方便运输。
不同岛屿之间#xff0c;路途距离不同#xff0c;国王希望你可以规划建公路的方案#xf…题目: 寻宝
题目描述
在世界的某个区域有一些分散的神秘岛屿每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路方便运输。
不同岛屿之间路途距离不同国王希望你可以规划建公路的方案如何可以以最短的总公路距离将 所有岛屿联通起来注意这是一个无向图。
给定一张地图其中包括了所有的岛屿以及它们之间的距离。以最小化公路建设长度确保可以链接到所有岛屿;
提取关键: 存在一些点, 存在一些边, 每条边都有一定的代价, 求将所有点连通的最小代价;
Kruskal 算法
思路
将边按代价从小到大进行排序, 然后从代价最小的开始遍历, 尽量选择代价小的边加入结果集中, 最终使得整个图连通;
当我们遍历到一条边, 这条边所连的两个顶点本身就已经连通时, 那么这条边是多余的, 如果加入, 会产生环;
并查集
并查集的作用与代码在上一篇文章中有详细介绍, 可以到专栏中查看;
前文介绍了并查集的两大作用: 判断两点之间是否连通以及求集合大小; 这里, 介绍另一个用途: 判断无向图中是否存在环;
在无向图中, 如果一条边的两个端点本来就是连通的(处在同一集合中), 那么这个边的加入必然会使得图中产生 “环” 假设图中有 1, 2, 3 三个顶点, 有 [1, 2], [1, 3] 两条边, 现在考虑加入 [2, 3] 这条边, 原本结点 2 和 结点 3 就已经处于连通状态, 现在加入 [2, 3] 必定导致图中出现环状结构;
利用并查集, 就可以在将边纳入[边集]之前进行判断, 判断当前边的加入是否会导致出现环;
1 ____ 2\ /\ /3代码
import java.util.*;public class Main{public static void main(String[] args){kruskal();}// 求最小生成树代价; 对边代价排序, 由小到大连接即可, 连接过程中用 Union 判断环private static void kruskal(){Scanner sc new Scanner(System.in);int vNum sc.nextInt();int eNum sc.nextInt();int[][] edges new int[eNum][3];for(int i 0; i eNum; i){for(int j 0; j 3; j){edges[i][j] sc.nextInt();}}Arrays.sort(edges, (e1, e2) - Integer.compare(e1[2], e2[2]));Union union new Union(vNum);int res 0;for(int[] edge : edges){if(!union.isSame(edge[0], edge[1])){res edge[2];union.join(edge[0], edge[1]);}}System.out.println(res);}
}class Union{private int[] father;public Union(int size){father new int[size 1];for(int i 1; i size; i){father[i] i;}}public int root(int i){int temp i;while(father[temp] ! temp){temp father[temp];}father[i] temp;return temp;}public boolean isSame(int i1, int i2){return root(i1) root(i2);}public void join(int i1, int i2){father[root(i2)] root(i1);}
}上一篇 【最小生成树】(一) 预备知识 并查集
