{"id":6259,"date":"2025-09-13T12:43:22","date_gmt":"2025-09-13T07:13:22","guid":{"rendered":"https:\/\/study.madeeasy.in\/?p=6259"},"modified":"2025-09-15T09:21:44","modified_gmt":"2025-09-15T03:51:44","slug":"kruskals-algorithm","status":"publish","type":"post","link":"https:\/\/www.madeeasy.in\/study\/cs-it\/algorithms\/kruskals-algorithm","title":{"rendered":"Kruskal Algorithm"},"content":{"rendered":"<p style=\"text-align: justify;\">Let G(V, E) be a connected, weighted graph. Kruskal\u2019s algorithm is used to find a minimum-cost spanning tree (MCST) of a given graph G. It uses a greedy approach to find MCST, because at each step it adds an edge of least possible weight to the set A. In this algorithm,<\/p>\n<ul style=\"text-align: justify;\">\n<li>First examine the edges of G in order of increasing weight.<\/li>\n<li>Then select an edge (u, v) \u2208 E of minimum weight and check whether its end points belongs to same component or different connected components.<\/li>\n<li>If u and v belong to different connected components, then we add it to set A; otherwise, it is rejected because it can create a cycle.<\/li>\n<li>The algorithm terminates when only one connected component remains (i.e. all the vertices of G have been reached).<\/li>\n<\/ul>\n<p style=\"text-align: justify;\">The following pseudo-code is used to construct an MCST, using Kruskal\u2019s algorithm:<\/p>\n<p style=\"text-align: justify;\"><strong> KRUSKAL MCST (G, w)<\/strong><\/p>\n<p style=\"text-align: justify;\">\/* Input: An undirected connected weighted graph G = (V, E).<br \/>\n\/* Output: A minimum cost spanning tree T(V, E\u2019) of G<br \/>\n{<br \/>\n1. Sort the edges of E in order of increasing weight<br \/>\n2. A \u2190 \u03c6<br \/>\n3. for (each vertex v \u2208 V[G])<br \/>\n4. do MAKE_SET(v)<br \/>\n5. for each edge (u, v) \u2208 E, taken in increasing order of weight<br \/>\n{<br \/>\n6. if (FIND_SET (u) \u2260 FIND_SET (v))<br \/>\n7. A \u2190 A \u222a {(u, v)}<br \/>\n8. MERGE(u, v)<br \/>\n}<br \/>\n9. return A<br \/>\n}<\/p>\n<p><strong>Kruskal\u2019s algorithm works as follows:<\/strong><\/p>\n<ul>\n<li style=\"text-align: justify;\">First, sort the edges of E in order of increasing weight<\/li>\n<li style=\"text-align: justify;\">We build a set A of edges that contains the edges of the MCST. Initially A is empty.<\/li>\n<li style=\"text-align: justify;\">In lines 3-4, the function MAKE_SET(v) creates\u00a0a new set {v} for all vertices of G. For a graph with n vertices, it creates n components of disjoint sets, such as {1}, {2}, and so on.<\/li>\n<li style=\"text-align: justify;\">In line 5-8: An edge (u, v) \u2208 E, of minimum weight is added to the set A, if and only if it joins two nodes which belongs to different components (to check this use a FIND_SET() function, which returns a same integer value, if u and v belongs to same components (In this case, adding (u, v) to A creates a cycle); otherwise, it returns a different integer value)<\/li>\n<li style=\"text-align: justify;\">If an edge is added to A, then the two components containing its end points are merged into a single component.<\/li>\n<li style=\"text-align: justify;\">The algorithm terminates when there is just a single component.<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Let G(V, E) be a connected, weighted graph. Kruskal\u2019s algorithm is used to find a minimum-cost spanning tree (MCST) of<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1831,3],"tags":[1843,1844],"class_list":["post-6259","post","type-post","status-publish","format-standard","hentry","category-algorithms","category-cs-it","tag-kruskals-algorithm","tag-kruskals-mcmt"],"_links":{"self":[{"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/posts\/6259","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/comments?post=6259"}],"version-history":[{"count":0,"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/posts\/6259\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/media?parent=6259"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/categories?post=6259"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/tags?post=6259"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}