Minimum Spanning Tree (Kruskal's algorithm) Using Disjoint set

Graph Learning (17 Part Series)

1 Breadth First Search Traversal of Graph GeeksForGeeks
2 Topological Sorting in Graph Using DFS and BFS GeeksForGeeks
… 13 more parts…
3 Check if a graph is Bipartite or not Leetcode
4 Cycle detection in a graph using Breadh First Search and Depth First Search GeeksForGeeks
5 Depth first search GeeksForGeeks
6 Shortest Distance from source to all other nodes in the graph where the edge weight is 1 unit
7 Dijkstra’s single source shortest path algorithm
8 Minimum Spanning Tree (Prims Algorithm)
9 Minimum Spanning Tree (Kruskal’s algorithm) Using Disjoint set
10 Bridges in the graph
11 Strongly connected components in the graph
12 Bellman ford algorithm(Single Source Shorted Path in DAG)
13 Floyd Warshall Algorithm (Multi-source shorted path)
14 Disjoint Set Graph Learning
15 Disjoint set graph with union by rank and union by size
16 Number of islands
17 Find safest walk through the grid

Time complexity is O(mlogm) + (m*O(4alpha) ~ constant time = O(1) for disjoint set )
Hence,
Efficient time complexity is : O(mlogm) where m is the no of edges in the graph logm is the time complexity to sort the List of m edges.

For more information go through

class Main{

 int findParent(int node,int parent[]){
        if(node == parent[node]) return node; // ie if the parent of 'node' is 'node' itself then just return the node.
        //return findParent(parent[node]);// else recursively call findParent to get the parent of this union.
        // in order to path compress (making sure that every node is connected to its parent in the given union)
        return parent[node]  = findParent(parent[node]);
        //example : 7->6->4->3 , here 3 is the parent of this union, so in order to get the parent of 7 which is 3 we can path compress it. like 7->3,6->3,4->3 etc.
    }
    void union(int u, int v,int parent[], int rank[]){
        u = findParent(u);
        v = findParent(v);
        if(rank[u] < rank[v]) parent[u] =v;
        else if (rank[u] > rank[v]) parent[v] = u;
        else parent[u] =v; // or parent[v] = u;
        // here u and v had the same rank
        //and now v became parent of u hence its rank will increase
        rank[v]++;
    }

    public static void main(String args[]) throws Exception{
        int n =5;
        ArrayList<Node> adj = new ArrayList<>();
        adj.add(new Node(0,1,2));
        adj.add(new Node(0,3,6));
        adj.add(new Node(1, 3, 8));
        adj.add(new Node(1, 2, 3));
        adj.add(new Node(1, 4, 5));
        adj.add(new Node(2, 4, 7));
        Main obj = new Main();
        obj.kruskalAlgo(adj,n);
    }
    public void kruskalAlgo(ArrayList<Node> adj, int n){
        Collections.sort(adj, new Comparator<Node> {
            public int compare(Node a, Node b){
                return a.getW()-b.getW();// sorting in ascending order of the weight;
            }
        });

        int parent[]  = new int[n];
        int rank[] = new int[n];
        //makeSet();
        for(int i =0;i<n;i++){
            parent[i] =i;
            rank[i] = 0;
        }
        int costOfMst = 0;
        ArrayList<Node> mst = new ArrayList<>();
        for(Node it : adj){
            // taking the node that is not taken already to avoid cycle.
            if(findParent(it.getU(),parent)!=findParent(it.getV(),parent)){
                costOfMst+=it.getW(); // add the cost in the costOfMst to keep track of growing cost to cover all the nodes
                mst.add(it);
                union(it.getU(),it.getV(),parent,rank); // make the node part of the union 
            }
        }
        System.out.println(costOfMst);
        for(Node it: mst){
            System.out.println(it.getU()+" - "+ it.getV());
        }
    }
    class Node {
        int u;
        int v;
        int weight;
        public Node(int u,int v, int w){
            this.u = u;
            this.v = v;
            this.weight = w;
        }
        public int getU(){
            return this.u;
        }
        public int getV(){
            return this.v;
        }
        public int getW(){
            return this.weight;
        }
    }
}

Enter fullscreen mode Exit fullscreen mode

Graph Learning (17 Part Series)

原文链接：Minimum Spanning Tree (Kruskal’s algorithm) Using Disjoint set

文章版权声明 1、本网站名称：拾光赋
2、本站永久网址：https://www.blogs.ink
3、本网站的文章部分内容可能来源于网络，仅供大家学习与参考，如有侵权，请联系站长QQ：805375623进行删除处理。
4、本站一切资源不代表本站立场，并不代表本站赞同其观点和对其真实性负责。
5、本站一律禁止以任何方式发布或转载任何违法的相关信息，访客发现请向站长举报
6、本站资源大多存储在云盘，如发现链接失效，请联系我们我们会第一时间更新。

THE END