图算法(一)-MST最小生成树

最小生成树（minimum spanning tree）的3种解法：

稀疏图：1>Prim PQ implementation  O(ElogV) 2>Kruskal implementationm (ElogV)

稠密图：Prim Naive implementation O(V²)

 

Minimum cost to connect all cities

• Difficulty Level : Medium

• There are n cities and there are roads in between some of the cities. Somehow all the roads are damaged simultaneously. We have to repair the roads to connect the cities again. There is a fixed cost to repair a particular road. Find out the minimum cost to connect all the cities by repairing roads. Input is in matrix(city) form, if city[i][j] = 0 then there is not any road between city i and city j, if city[i][j] = a > 0 then the cost to rebuild the path between city i and city j is a. Print out the minimum cost to connect all the cities. 

It is sure that all the cities were connected before the roads were damaged.

Examples: 

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.  To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.

In case you wish to attend live classes with experts, please refer DSA Live Classes for Working Professionals and Competitive Programming Live for Students.

Input : {{0, 1, 2, 3, 4},
         {1, 0, 5, 0, 7},
         {2, 5, 0, 6, 0},
         {3, 0, 6, 0, 0},
         {4, 7, 0, 0, 0}};
Output : 10

 Prim PQ implementation 

import java.io.*;
import java.util.*;

class GFG {
    public static void main (String[] args) {
        int[][] matrix = new int[][]{{0, 1, 1, 100, 0, 0},
         {1, 0, 1, 0, 0, 0},
         {1, 1, 0, 0, 0, 0},
         {100, 0, 0, 0, 2, 2},
         {0, 0, 0, 2, 0, 2},
         {0, 0, 0, 2, 2, 0}};
        System.out.println(getMinPath(matrix));
    }
    static class Edge{
        int x;
        int y;
        int value;
        Edge(int x,int y,int value){
            this.x=x;
            this.y=y;
            this.value=value;
        }
    }
    private static int getMinPath(int[][] matrix){
        int len = matrix.length;
        //1.create heap
        PriorityQueue pq = new PriorityQueue<>((a,b)->a.value-b.value);
        //2.put the first element into heap
        Set visited = new HashSet<>();
        visited.add(0);
        for(int i=0;iif(i!=0 && matrix[0][i]!=0) pq.offer(new Edge(0,i,matrix[0][i]));
        //3.while loop 
        int sum = 0;
        while(!pq.isEmpty()){
            Edge edge = pq.poll();
            if(visited.add(edge.y)){
                sum+=edge.value;
                for(int i=0;iif(i!=edge.y && matrix[edge.y][i]!=0) pq.offer(new Edge(edge.y,i,matrix[edge.y][i]));
            }
        }
        if(visited.size()==len) return sum;
        return -1;
    }
}

 Kruskal 

import java.io.*;
import java.util.*;

class GFG {
    public static void main (String[] args) {
        int result = mst(new int[][]
        {{0, 1, 1, 100, 0, 0},
         {1, 0, 1, 0, 0, 0},
         {1, 1, 0, 0, 0, 0},
         {100, 0, 0, 0, 2, 2},
         {0, 0, 0, 2, 0, 2},
         {0, 0, 0, 2, 2, 0}});
        System.out.println(result);
    }
    private static int mst(int[][] matrix){
        List list = new ArrayList<>();
        for(int i=0;i){
            for(int j=i+1;j){
                if( matrix[i][j]!=0) 
                    list.add(new Edge(i,j,matrix[i][j]));
            }
        }
        Collections.sort(list,(x,y)->x.len-y.len);
        UnionFind uf = new UnionFind(matrix.length);
        int sum=0;
        int count=0;
        for(Edge edge:list){
            if(uf.findParent(edge.x)!=uf.findParent(edge.y)) {//已经连通的不能再union
                uf.union(edge.x,edge.y);
                sum+=edge.len;
                count++;
                if(count==matrix.length-1) break;//当边数==顶点数-1 的时候，就已经全部连通了
            }
        }
        return sum;
    }
    static class Edge{
        int x;int y;int len;
        Edge(int x,int y,int len){
            this.x=x;
            this.y=y;
            this.len=len;
        }
    }
    static class UnionFind{
        int[] parent;
        UnionFind(int n){
            parent = new int[n];
            for(int i=0;ii;
        }
        int findParent(int i){
            if(parent[i]==i) return i;
            parent[i]=findParent(parent[i]);
            return parent[i];
        }
        void union(int x,int y){
            int px = findParent(x);
            int py = findParent(y);
            parent[px] = py;
        }
    }
}

1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree Hard

Given a weighted undirected connected graph with n vertices numbered from 0 to n - 1, and an array edges where edges[i] = [ai, bi, weighti] represents a bidirectional and weighted edge between nodes ai and bi. A minimum spanning tree (MST) is a subset of the graph's edges that connects all vertices without cycles and with the minimum possible total edge weight.

Find all the critical and pseudo-critical edges in the given graph's minimum spanning tree (MST). An MST edge whose deletion from the graph would cause the MST weight to increase is called a critical edge. On the other hand, a pseudo-critical edge is that which can appear in some MSTs but not all.

Note that you can return the indices of the edges in any order.

Example 1:

Input: n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
Output: [[0,1],[2,3,4,5]]
Explanation: The figure above describes the graph.
The following figure shows all the possible MSTs:

Notice that the two edges 0 and 1 appear in all MSTs, therefore they are critical edges, so we return them in the first list of the output.
The edges 2, 3, 4, and 5 are only part of some MSTs, therefore they are considered pseudo-critical edges. We add them to the second list of the output.

Example 2:

Input: n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
Output: [[],[0,1,2,3]]
Explanation: We can observe that since all 4 edges have equal weight, choosing any 3 edges from the given 4 will yield an MST. Therefore all 4 edges are pseudo-critical.

Constraints:

• 2 <= n <= 100
• 1 <= edges.length <= min(200, n * (n - 1) / 2)
• edges[i].length == 3
• 0 <= ai < bi < n
• 1 <= weighti <= 1000
• All pairs (ai, bi) are distinct.

class Solution {
    public List> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
        //1.将数组下标位置加入edges
        int[][] nEdges = new int[edges.length][4];
        for(int i=0;inew int[]{edges[i][0],edges[i][1],edges[i][2],i};
        Arrays.sort(nEdges,(x,y)->x[2]-y[2]);
        //初次计算mst
        int min = mst(n,nEdges,-1,-1);
        //逐条edge移除后，检查新mst是否大于原始mst
        List critical = new ArrayList();
        List pseudo = new ArrayList();
        for(int i=0;i){
            int curr = mst(n,nEdges,i,-1);
            //如果去除此边会mst会变大，说明是critical
            if(min ) critical.add(i);
            else{
                //如果mst中强制增加这条边mst没有变大，说明是pseudo    此处关键点，如何判定是pseudo的边
                if(min==mst(n,nEdges,-1,i)) pseudo.add(i);
            }
        }
        //3.return result;
        return Arrays.asList(critical,pseudo);
    }
    private int mst(int n, int[][] edges,int exclude,int include){
        int count = 0,sum=0;
        UnionFind uf = new UnionFind(n);
        if(include>=0) {//如果强制加入的边不为空，先加入强制的边
            int i = 0;
            for(i=0;iif(edges[i][3]==include) break; 
            uf.union(edges[i][0],edges[i][1]);
            sum+=edges[i][2];
            count++;
        }
        for( int i=0;i ){
            int[] edge = edges[i];
            if(edge[3]==exclude) continue;//滤除要过滤的边
            if(uf.findParent(edge[0])!=uf.findParent(edge[1])){
                uf.union(edge[0],edge[1]);
                sum+=edge[2];
                count++;
                if(count==n-1) return sum;
            }
        }
        return count==n-1 ? sum : -1;
    }
    class UnionFind{
        int[] parent;
        UnionFind(int n){
            parent = new int[n];
            for(int i=0;ii;
        }
        void union(int x,int y){
            parent[findParent(x)] = parent[findParent(y)];
        }
        int findParent(int x){
            if(x==parent[x]) return x;
            parent[x]= findParent(parent[x]);
            return parent[x];
        }
    }
}