- Problem Statement<\/a><\/li>
- Approach<\/a><\/li>
- Dry Run<\/a><\/li>
- Step 1:<\/a><\/li>
- Step 2:<\/a><\/li>
- Step 3:<\/a><\/li>
- Step 4:<\/a><\/li>
- Step 5:<\/a><\/li><\/ul>
- C\/C++ Implementation<\/a><\/li>
- Java Implementation<\/a><\/li>
- Python Implementation<\/a><\/li><\/ul>
- Practice Question<\/a><\/li>
- Frequently Asked Questions<\/a><\/li>
- Q.1: What is the difference between Kruskal’s and Prim’s algorithms?<\/a><\/li>
- Q.2: How efficient is the Kruskal algorithm?<\/a><\/li>
- Q.3: Is Kruskal better than prim?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n
Problem Statement<\/h2>\n\n\n\n
In Kruskal Algorithm, initially, all the nodes of the graph are separated from each other, which means they don\u2019t have an edge between them. Then to obtain the minimum spanning tree from that graph we first sort the edges of the graph in a non-decreasing fashion. Then we pick the edges from left to right and connect the graph. <\/p>\n\n\n\n
Now there are two possibilities, first one is if the current picked edge is already connected in the tree so in this case, we will just continue our process and if the current picked edge is not connected then we will just connect those two nodes with dsu (disjoint set union). In this manner, we finally conclude with the final MST of the given graph.<\/p>\n\n\n\n
- Example<\/strong>:<\/li>
- Input:<\/strong><\/li><\/ul>\n\n\n\n
<\/figure><\/div>\n\n\n\n
- Output:<\/strong> 10<\/li><\/ul>\n\n\n\n
Explanation:<\/strong> MST Weight = AB + BC + BE + BC+ EF = 10<\/em><\/p>\n\n\n\n
- Input:<\/strong><\/li><\/ul>\n\n\n\n
- Output: 14<\/strong><\/li><\/ul>\n\n\n\n
Explanation: <\/strong>Here the second image is the MST image of the left image.<\/em><\/p>\n\n\n\n
Approach<\/h2>\n\n\n\n
- Sort all the edges of the graph with respect to their weights. Initially sort the graph edges with respect to weights in a non-decreasing manner.<\/li>
- Now traverse left to right means from smallest weight to largest weight and start adding edges to the MST.<\/li>
- Add all those edges which don’t form a cycle, edges that connect only disconnected components.<\/li><\/ul>\n\n\n\n
So now one more question arises here, how will we check if the 2 vertices are connected or not?<\/p>\n\n\n\n
To check if 2 vertices are connected or not we can use the dfs approach. In this, we first start our dfs from any 1st vertex and then check whether the 2nd vertex is visited or not. To run it efficiently we can do this by DSU (Disjoint Set Union).<\/p>\n\n\n\n
Dry Run<\/h3>\n\n\n\n
Step 1:<\/h4>\n\n\n\n
Dry Run<\/figcaption><\/figure>\n\n\n\n Step 2:<\/h4>\n\n\n\n
Step 3:<\/h4>\n\n\n\n
Step 4:<\/h4>\n\n\n\n
Step 5:<\/h4>\n\n\n\n
C\/C++ Implementation<\/span><\/h3>\n\n\n\n
const int MAX = 1e4 + 5;\nint id[MAX], nodes, edges;\npair <long long, pair<int, int> > p[MAX];\n\nvoid initialize()\n{\n for(int i = 0;i < MAX;++i)\n id[i] = i;\n}\n\nint root(int x)\n{\n while(id[x] != x)\n {\n id[x] = id[id[x]];\n x = id[x];\n }\n return x;\n}\n\nvoid union1(int x, int y)\n{\n int p = root(x);\n int q = root(y);\n id[p] = id[q];\n}\n\nlong long kruskal(pair<long long, pair<int, int> > p[])\n{\n int x, y;\n long long cost, minimumCost = 0;\n for(int i = 0;i < edges;++i)\n {\n \/\/ Selecting edges one by one in increasing order from the beginning\n x = p[i].second.first;\n y = p[i].second.second;\n cost = p[i].first;\n \/\/ Check if the selected edge is creating a cycle or not\n if(root(x) != root(y))\n {\n minimumCost += cost;\n union1(x, y);\n } \n }\n return minimumCost;\n}<\/pre>\n\n\n\nJava Implementation<\/h3>\n\n\n\n
class UnionFind{\n final int[] parents;\n int count;\n \n public UnionFind(int n){\n this.parents = new int[n];\n reset();\n }\n \n public void reset(){\n for(int i =0;i<parents.length;i++){\n parents[i] = i;\n }\n count = parents.length;\n }\n \n public int find(int i){\n int parent = parents[i];\n if(parent == i){\n return i;\n }else{\n int root = find(parent);\n parents[i] = root;\n return root;\n }\n }\n \n public boolean union(int i, int j){\n int r1 = find(i);\n int r2 = find(j);\n if(r1 != r2){\n count--;\n parents[r1] = r2;\n return true;\n }else{\n return false;\n }\n }\n \n}\n\nclass Solution {\n public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {\n \n List<Integer>criticals = new ArrayList<>();\n List<Integer> pseduos = new ArrayList<>();\n \n Map<int[], Integer> map = new HashMap<>();\n for(int i =0;i<edges.length;i++){\n map.put(edges[i], i);\n }\n \n Arrays.sort(edges, (e1, e2)->Integer.compare(e1[2], e2[2]));\n int minCost = buildMST(n, edges, null, null);\n \n for(int i =0;i<edges.length;i++){\n int[] edge = edges[i];\n int index = map.get(edge);\n int costWithout = buildMST(n, edges, null, edge);\n if(costWithout > minCost){\n criticals.add(index);\n }else{\n int costWith = buildMST(n, edges, edge, null);\n if(costWith == minCost){\n pseduos.add(index);\n }\n }\n \n }\n \n return Arrays.asList(criticals, pseduos);\n }\n \n private int buildMST(int n, int[][] edges, int[] pick, int[] skip){\n UnionFind uf = new UnionFind(n);\n int cost = 0;\n if(pick != null){\n uf.union(pick[0], pick[1]);\n cost += pick[2];\n }\n \n for(int[] edge : edges){\n if(edge != skip && uf.union(edge[0], edge[1])){\n cost += edge[2];\n }\n }\n return uf.count == 1? cost : Integer.MAX_VALUE;\n }\n}<\/pre>\n\n\n\nPython Implementation<\/h3>\n\n\n\n
class Solution:\n def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n \n def dfs(curr, level, parent):\n levels[curr] = level\n for child, i in graph[curr]:\n if child == parent:\n continue\n elif levels[child] == -1:\n levels[curr] = min(levels[curr], dfs(child, level + 1, curr))\n else:\n levels[curr] = min(levels[curr], levels[child])\n if levels[child] >= level + 1 and i not in p_cri:\n cri.add(i)\n return levels[curr]\n \n cri, p_cri = set(), set()\n \n dic = collections.defaultdict(list)\n for i, (u, v, w) in enumerate(edges):\n dic[w].append([u, v, i])\n \n union_set = UnionFindSet(n)\n \n for w in sorted(dic):\n seen = collections.defaultdict(set)\n for u, v, i in dic[w]:\n pu, pv = union_set.find(u), union_set.find(v)\n if pu == pv:\n continue\n seen[min(pu, pv), max(pu, pv)].add(i) \n w_edges, graph = [], collections.defaultdict(list)\n for pu, pv in seen:\n if len(seen[pu, pv]) > 1:\n p_cri |= seen[pu, pv]\n \n edge_idx = seen[pu, pv].pop()\n graph[pu].append((pv, edge_idx))\n graph[pv].append((pu, edge_idx))\n w_edges.append((pu, pv, edge_idx))\n \n union_set.union(pu, pv)\n \n \n levels = [-1] * n\n for u, v, i in w_edges:\n if levels[u] == -1:\n dfs(u, 0, -1)\n \n for u, v, i in w_edges:\n if i not in cri:\n p_cri.add(i)\n \n return [cri, p_cri]<\/pre>\n\n\n\n
- Output: 14<\/strong><\/li><\/ul>\n\n\n\n
- Input:<\/strong><\/li><\/ul>\n\n\n\n
- Input:<\/strong><\/li><\/ul>\n\n\n\n
- Q.2: How efficient is the Kruskal algorithm?<\/a><\/li>
- Step 2:<\/a><\/li>
- Step 1:<\/a><\/li>
- Approach<\/a><\/li>
![\"Example\"](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-4-1.jpg\")
<\/figure><\/div>\n\n\n\n![\"Input\"](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-5.jpg\")
<\/figure><\/div>\n\n\n\n![\"Dry](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-7-.jpg\")
![\"Dry](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-3.jpg\")
<\/figure>\n\n\n\n![\"Dry](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-3.jpg\")
<\/figure>\n\n\n\n![\"Dry](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-6.jpg\")
<\/figure>\n\n\n\n![\"Dry](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-3.jpg\")
<\/figure>\n\n\n\n