题解 | #最小生成树(prim算法 java set list)#
最小生成树
http://www.nowcoder.com/practice/735a34ff4672498b95660f43b7fcd628
效率不高,希望能拓宽大家的思路:
import java.util.*; public class Solution { // 这是用集合模拟的普利姆算法,希望能拓宽大家的思路 public int miniSpanningTree (int n, int m, int[][] cost) { Arrays.sort(cost, (o1,o2)->{ return o1[2] - o2[2]; //先按照边的权值非降序排列 }); HashSet<Integer> set = new HashSet<>(); // 存储可达的点 ArrayList<int[]> list = new ArrayList<>(); // 存储所有的边 for (int[] c : cost) { list.add(c); } int res = 0; res += cost[0][2]; set.add(cost[0][0]); set.add(cost[0][1]); while (true) { // 从剩余边中选择 for (int i = 1; i < list.size(); i++) { // prim 核心,下一条边是连接一个可达点和不可达点的最小权值边 if ((set.contains(list.get(i)[0]) && !set.contains(list.get(i)[1])) || (!set.contains(list.get(i)[0]) && set.contains(list.get(i)[1]))) { res += list.get(i)[2]; set.add(list.get(i)[0]); set.add(list.get(i)[1]); list.remove(list.get(i)); // 下一次不用再遍历这一条边了 break; } } if (set.size() == n) { // 当所有点可达,结束循环 break; } } return res; } }