最小生成树

为什么prim算法通过不了，只能过前六个测试，不知道问题出哪里了 public int miniSpanningTree(int n, int m, int[][] cost) {

        int[][] graph = new int[n][n];

        //构建邻接矩阵图
        for (int i = 0; i < m; i++) {
            int u = cost[i][0] - 1;
            int v = cost[i][1] - 1;
            int weight = cost[i][2];
            graph[u][v] = weight;
            graph[v][u] = weight;
        }


        if (n == 2) return cost[0][2];
        // write code here
        //status数组记录节点是否联通了，初始化都为false
        boolean[] status = new boolean[n];
        Arrays.fill(status, false);
        //distance数组记录各个点到联通部分的最短距离,初始化无穷
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        //pre数组记录节点和谁联通,初始化都为-1
        int[] pre = new int[n];
        Arrays.fill(pre, -1);

        //开始遍历，n个点需要遍历n-1次，从点0（下标）开始
        dist[0] = 0;
        int totalCost = 0;
        for (int i = 0; i < n; i++) {//循环次数为点的个数，因为每个点都要加入mst
            // 选择键值最小的顶点u，它尚未包含在MST中
            int u = -1;//初始化该点为不连通（可能没必要？）
            int max = Integer.MAX_VALUE;//初始化一个值为整型最大值来循环排除无穷不可达
            for (int j = 0; j < n; j++) {
                if (!status[j] && dist[j] < max) {
                    max = dist[j];//这里不能忘记更新
                    u = j;
                }
            }
            //找到相应点，添加到集合
            if (u == -1) break;
            status[u] = true;
            totalCost += dist[u];
            for (int v = 0; v < n; v++) {
                if (!status[v] && graph[u][v] != 0 && graph[u][v] < dist[v]) {
                    pre[v] = u;
                    dist[v] = graph[u][v];
                }
            }
        }
        return totalCost;
    }

import java.util.*;
public class Solution {
    
    public class bb{
        int from;
        int to;
        int w;
        public bb(int from,int to,int w){
            this.from=from;
            this.to=to;
            this.w=w;
        }
    }
    public int miniSpanningTree (int n, int m, int[][] cost) {
        // write code here
        HashSet<Integer> set=new HashSet<>();
        HashMap<Integer,List<bb>> map=new HashMap<>();
        for(int i=0;i<n;i++){
            List<bb> l=new ArrayList<>();
            map.put(i+1,l);
        }
        PriorityQueue<bb> q=new  PriorityQueue<>(new Comparator<bb>() {
            public int compare(bb o1, bb o2) {
                bb b1=(bb)o1;
                bb b2=(bb)o2;
                return b1.w-b2.w;
            }
        });
        for(int i=0;i<m;i++){
            bb a=new bb(cost[i][0],cost[i][1],cost[i][2]);
            map.get(cost[i][0]).add(a);
            map.get(cost[i][1]).add(a);
        }
        int sum=0;
        set.add(1);
        for(bb b:map.get(1)){
            q.add(b);
        }
        while(!q.isEmpty()){
            bb b=q.poll();
            if((!set.contains(b.from))||(!set.contains(b.to))){
                int d=set.contains(b.from)?b.to:b.from;
                sum+=b.w;
                set.add(d);
                for(bb B:map.get(d)){
                    q.add(B);
                }
            }
        }
        return sum;
    }
}

克鲁斯卡 + 并查集

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int n户人家的村庄
     * @param m int m条路
     * @param cost int二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int
     */
    public int miniSpanningTree (int n, int m, int[][] cost) {
        int minCost = 0;
        UnionFind uf = new UnionFind(n);
        List<int[]> list = new ArrayList<>();
        for (int[] elem : cost) {
            list.add(elem);
        }
        list.sort((o1,o2)->o1[2]-o2[2]);

        for (int[] elem : list) {
            if (uf.find(elem[0]) != uf.find(elem[1])) {
                uf.merge(elem[0],elem[1]);
                minCost+=elem[2];
            }
        }

        return minCost;
    }

    class UnionFind {

        private int N;
        private int[] innerArr;

        public UnionFind(int n) {
            N = n;
            innerArr = new int[N+1];
            init(n);
        }

        /**
         * 并查集初始化
         * 一开始每个节点的父节点都是自己
         * @param n
         */
        private void init(int n) {
            for (int i = 1; i <=N ; i++) {
                innerArr[i]=i;
            }
        }

        /**
         * 查找父节点
         * @param num
         * @return
         */
        public int find(int num) {
            if (innerArr[num]==num) return num;
            //// 方法1：回溯寻找父节点
            //return find(innerArr[num]);

            // 方法2：在递归找寻的时候更新父节点
            // 即让最底层节点直指最顶父节点
            int topFather = find(innerArr[num]);
            innerArr[num] = topFather;
            return topFather;
        }

        /**
         * 合并两个节点所在的集合
         * 即将 num2 的父节点修改为 num1 的父节点
         * @param num1
         * @param num2
         */
        public void merge(int num1,int num2) {
            innerArr[find(num2)] = find(num1);
        }

    }
}

import java.util.*;
public class Solution {
    int[] parent;
    int findParent(int i) {
        if(parent[i] == i) return i;
        parent[i] = findParent(parent[i]);
        return parent[i];
    }
    public int miniSpanningTree (int n, int m, int[][] cost) {
        // write code here
        parent = new int[n + 1];
        for(int i = 0; i <= n; i ++) {
            parent[i] = i;
        }
        Arrays.sort(cost, new Comparator<int[]>(){
            @Override
            public int compare(int[] p1,int[] p2) {
                return p1[2] - p2[2];
            }
        });
        int w = 0;
        for(int i = 0; i < m; i ++) {
            int a = cost[i][0];
            int b = cost[i][1];
            int p1 = findParent(a);
            int p2 = findParent(b);
            if(p1 != p2) {
                w = w + cost[i][2];
                parent[p2] = p1;
            }
        }
        return w;
    }

}

import java.util.*;
//六刷终于搞懂了：克鲁斯卡尔+并查集
//https://www.bilibili.com/video/BV1g5411c7iS?from=search&seid=5350587815569640429
//https://zhuanlan.zhihu.com/p/93647900
//https://www.bilibili.com/video/BV1Mf4y117bZ?from=search&seid=914796745468480478


//整体思路知道，但是实在没搞清楚find和join的内部实现逻辑

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int n户人家的村庄
     * @param m int m条路
     * @param cost int二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int
     */
    public int miniSpanningTree (int n, int m, int[][] cost) {
        // write code here
        //声明和初始化并查集
        int[] fa = new int[n+1];
        for (int i = 1; i <= n; ++i)fa[i] = i;
        
        int ans = 0;
        //几户人家，几!=0，所以从1开始
        Arrays.sort(cost, (int[] a, int[] b)-> a[2]-b[2]);
        for(int i = 0; i < cost.length; i++) {
            if(find(fa, cost[i][0]) != find(fa, cost[i][1])) {
                // add edge
                join(fa, cost[i][0], cost[i][1]);
                ans += cost[i][2];
            }
        }
        return ans;
    }
    public int find(int[] fa, int x) {
        if(fa[x] != x) {
            fa[x] = find(fa, fa[x]);
        }
        return fa[x];
    }
    public void join(int[] fa, int x, int y) {
        int fax = find(fa, x);
        int fay = find(fa, y);
        fa[fax] = fay;
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int n户人家的村庄
     * @param m int m条路
     * @param cost int二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int
     */
    public int miniSpanningTree (int n, int m, int[][] cost) {
        // write code here
        int[] fa = new int[n+1];
        int ans = 0;
        for(int i = 0; i < fa.length; i++) fa[i] = i;
        Arrays.sort(cost, (int[] a, int[] b)-> a[2]-b[2]);
        for(int i = 0; i < cost.length; i++) {
            if(find(fa, cost[i][0]) != find(fa, cost[i][1])) {
                // add edge
                join(fa, cost[i][0], cost[i][1]);
                ans += cost[i][2];
            }
        }
        return ans;
    }
    public int find(int[] fa, int x) {
        if(fa[x] != x) {
            fa[x] = find(fa, fa[x]);
        }
        return fa[x];
    }
    public void join(int[] fa, int x, int y) {
        int fax = find(fa, x);
        int fay = find(fa, y);
        fa[fax] = fay;
    }
}

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int n户人家的村庄
     * @param m int m条路
     * @param cost int二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int
     */
    public int miniSpanningTree (int n, int m, int[][] cost) {
        // write code here
        Graph graph=createGraph(cost);
        return KruskalMST(graph);
    }
    public class Graph{
        HashMap<Integer,Node> nodes;
        HashSet<Edge> edges;
        public Graph(){
            nodes=new HashMap<>();
            edges=new HashSet<>();
        }
    }
    public class Node{
        int value;
        ArrayList<Node> nexts;
        ArrayList<Edge> edges;
        public Node(int value){
            this.value=value;
            nexts=new ArrayList<>();
            edges=new ArrayList<>();
        }
    }
    public class Edge{
        int weight;
        Node from;
        Node to;
        public Edge(int weight,Node from,Node to){
            this.weight=weight;
            this.to=to;
            this.from=from;
        }
    }
    public Graph createGraph(int[][] cost){
        Graph graph=new Graph();
        for(int i=0;i<cost.length;i++){
            int weight=cost[i][2];
            int from=cost[i][0];
            int to=cost[i][1];
            if(!graph.nodes.containsKey(from)){
                graph.nodes.put(from,new Node(from));
            }
            if(!graph.nodes.containsKey(to)){
                graph.nodes.put(to,new Node(to));
            }
            Node fromNode=graph.nodes.get(from);
            Node toNode=graph.nodes.get(to);
            Edge newEdge=new Edge(weight,fromNode,toNode);
            fromNode.nexts.add(toNode);
            fromNode.edges.add(newEdge);
            graph.edges.add(newEdge);
        }
        return graph;
    }
    public class UnionFind{
        HashMap<Node,Node> fatherMap;
        HashMap<Node,Integer> rankMap;
        public UnionFind(){
            fatherMap=new HashMap<Node,Node>();
            rankMap=new HashMap<Node,Integer>();
        }
        public Node findFather(Node n){
            Node father=fatherMap.get(n);
            if(father!=n){
                father=findFather(father);
            }
            fatherMap.put(n,father);
            return father;
        }
        public void makeSets(Collection<Node> nodes){
            fatherMap.clear();
            rankMap.clear();
            for(Node node:nodes){
                fatherMap.put(node,node);
                rankMap.put(node,1);
            }
        }
        public boolean isSameSet(Node a,Node b){
            return findFather(a)==findFather(b);
        }
        public void union(Node a,Node b){
            if(a==null||b==null){
                return;
            }
            Node aFather=findFather(a);
            Node bFather=findFather(b);
            if(aFather!=bFather){
                int aFrank=rankMap.get(aFather);
                int bFrank=rankMap.get(bFather);
                if(aFrank<=bFrank){
                    fatherMap.put(aFather,bFather);
                    rankMap.put(bFather,aFrank+bFrank);
                }
                else{
                    fatherMap.put(bFather,aFather);
                    rankMap.put(aFather,aFrank+bFrank);
                }
            }
        }
    }
    public class EdgeComparator implements Comparator<Edge>{
            public int compare(Edge o1,Edge o2){
                return o1.weight-o2.weight;
            }
        }
    public int KruskalMST(Graph graph){
        int sum=0;
        UnionFind unionFind=new UnionFind();
        unionFind.makeSets(graph.nodes.values());
        PriorityQueue<Edge> priorityQueue=new PriorityQueue<>(new EdgeComparator());
        for(Edge edge:graph.edges){
            priorityQueue.add(edge);
        }
        while(!priorityQueue.isEmpty()){
            Edge edge=priorityQueue.poll();
            if(!unionFind.isSameSet(edge.from,edge.to)){
                sum+=edge.weight;
                unionFind.union(edge.from,edge.to);
            }
        }
        return sum;
    }
}


prim算法却没过了，难受