{"id":12389,"date":"2023-02-02T10:29:40","date_gmt":"2023-02-02T10:29:40","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=12389"},"modified":"2023-03-02T06:07:44","modified_gmt":"2023-03-02T06:07:44","slug":"kruskals-algorithm","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/kruskals-algorithm\/","title":{"rendered":"Kruskal\u2019s Algorithm"},"content":{"rendered":"<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1675333521339-Kruskal%E2%80%99s%20Algorithm.jpg\" alt=\"\" \/><\/p>\n<p>In this article, we will study about Kruskal algorithm, its implementation, spanning tree, minimum spanning tree, and time complexity of this algorithm.<\/p>\n<h2>What is a Spanning Tree?<\/h2>\n<p>A spanning tree is a subset of a connected graph G in which every edge is connected, allowing traversal to any edge from a specific edge with or without intermediates. A spanning tree must also be free of cycles. So if the graph has N vertices then the Spanning tree should have N-1 edges.<\/p>\n<h2>What is a Minimum Spanning Tree?<\/h2>\n<p>The spanning tree which has the least weight or minimum weight spanning tree (i.e. the sum of weights of all the edges is minimum)of all possible spanning trees and this spanning tree is minimum spanning tree.<\/p>\n<h3>Application of Minimum Spanning Tree<\/h3>\n<p>In the architecture of networks, such as computer networks, telecommunications networks, transportation networks, water supply networks, and electrical grids, minimum-spanning trees have practical applications <\/p>\n<h2>Kruskal Algorithm<\/h2>\n<p>A greedy Algorithm which is used to determine the graph&#8217;s minimum spanning tree The algorithm&#8217;s primary goal is to identify the subset of edges that will allow us to pass through each graph vertex. Instead of concentrating on a global optimum, it adopts a greedy strategy that seeks the best outcome at each stage. To apply this algorithm graph must be undirected weighted and connected.<\/p>\n<p><strong>Practical Application<\/strong><\/p>\n<ul>\n<li>Wiring between cities can be laid out using Kruskal&#8217;s algorithm.<\/li>\n<li>LAN connection<\/li>\n<\/ul>\n<p><strong>Example<\/strong><br \/>\nWe take an undirected, weighted graph and we find the minimum spanning tree step by step by simply sort the edges in non decreasing. Then pick the edges one by one greedily without forming the cycle.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1675333521430-Kruskal%E2%80%99s%20Algorithm1.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1675333521439-Kruskal%E2%80%99s%20Algorithm2.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1675333521454-Kruskal%E2%80%99s%20Algorithm3.png\" alt=\"\" \/><\/p>\n\t\t\t\t\t\t<style>\r\n\t\t\t\t\r\n\t\t\t\t\t#tab_container_12388 {\r\n\toverflow:hidden;\r\n\tdisplay:block;\r\n\twidth:100%;\r\n\tborder:0px solid #ddd;\r\n\tmargin-bottom:30px;\r\n\t}\r\n\r\n#tab_container_12388 .tab-content{\r\n\tpadding:20px;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n\tmargin-top: 0px;\r\n\tbackground-color:#ffffff !important;\r\n\tcolor: #000000 !important;\r\n\tfont-size:16px !important;\r\n\tfont-family: Open Sans !important;\r\n\t\r\n\t\tborder: 1px solid #e6e6e6 !important;\r\n\t}\r\n#tab_container_12388 .wpsm_nav-tabs {\r\n    border-bottom: 0px solid #ddd;\r\n}\r\n#tab_container_12388 .wpsm_nav-tabs > li.active > a, #tab_container_12388 .wpsm_nav-tabs > li.active > a:hover, #tab_container_12388 .wpsm_nav-tabs > li.active > a:focus {\r\n\tcolor: #000000 !important;\r\n\tcursor: default;\r\n\tbackground-color: #ffffff !important;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n}\r\n\r\n#tab_container_12388 .wpsm_nav-tabs > li > a {\r\n    margin-right: 0px !important; \r\n    line-height: 1.42857143 !important;\r\n    border: 1px solid #d5d5d5 !important;\r\n    border-radius: 0px 0px 0 0 !important; \r\n\tbackground-color: #e8e8e8 !important;\r\n\tcolor: #000000 !important;\r\n\tpadding: 15px 18px 15px 18px !important;\r\n\ttext-decoration: none !important;\r\n\tfont-size: 14px !important;\r\n\ttext-align:center !important;\r\n\tfont-family: Open Sans !important;\r\n}\r\n#tab_container_12388 .wpsm_nav-tabs > li > a:focus {\r\noutline: 0px !important;\r\n}\r\n\r\n#tab_container_12388 .wpsm_nav-tabs > li > a:before {\r\n\tdisplay:none !important;\r\n}\r\n#tab_container_12388 .wpsm_nav-tabs > li > a:after {\r\n\tdisplay:none !important ;\r\n}\r\n#tab_container_12388 .wpsm_nav-tabs > li{\r\npadding:0px !important ;\r\nmargin:0px;\r\n}\r\n\r\n#tab_container_12388 .wpsm_nav-tabs > li > a:hover , #tab_container_12388 .wpsm_nav-tabs > li > a:focus {\r\n    color: #000000 !important;\r\n    background-color: #e8e8e8 !important;\r\n\tborder: 1px solid #d5d5d5 !important;\r\n\t\r\n}\r\n#tab_container_12388 .wpsm_nav-tabs > li > a .fa{\r\n\r\nmargin-right:5px !important;\r\n\r\nmargin-left:5px !important;\r\n\r\n\r\n}\r\n\r\n\t\t#tab_container_12388 .wpsm_nav-tabs a{\r\n\t\t\tbackground-image: none;\r\n\t\t\tbackground-position: 0 0;\r\n\t\t\tbackground-repeat: repeat-x;\r\n\t\t}\r\n\t\t\t\r\n\r\n\r\n#tab_container_12388 .wpsm_nav-tabs > li {\r\n    float: left;\r\n    margin-bottom: -1px !important;\r\n\tmargin-right:0px !important; \r\n}\r\n\r\n\r\n#tab_container_12388 .tab-content{\r\noverflow:hidden !important;\r\n}\r\n\r\n\r\n@media (min-width: 769px) {\r\n\r\n\t#tab_container_12388 .wpsm_nav-tabs > li{\r\n\t\tfloat:left !important ;\r\n\t\t\t\tmargin-right:-1px !important;\r\n\t\t\t\t\t}\r\n\t#tab_container_12388 .wpsm_nav-tabs{\r\n\t\tfloat:none !important;\r\n\t\tmargin:0px !important;\r\n\t}\r\n\r\n\t#tab_container_12388 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_12388 .wpsm_nav{\r\n\t\t\t}\r\n\r\n}\r\n\r\n\r\n\r\n@media (max-width: 768px) {\r\n\t#tab_container_12388 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_12388 .wpsm_nav{\r\n\t\t\t}\r\n}\r\n\r\n\r\n\t.wpsm_nav-tabs li:before{\r\n\t\tdisplay:none !important;\r\n\t}\r\n\r\n\t@media (max-width: 768px) {\r\n\t\t\t\t\r\n\t\t\t\t.wpsm_nav-tabs{\r\n\t\t\tmargin-left:0px !important;\r\n\t\t\tmargin-right:0px !important; \r\n\t\t\t\r\n\t\t}\r\n\t\t\t\t#tab_container_12388 .wpsm_nav-tabs > li{\r\n\t\t\tfloat:none !important;\r\n\t\t}\r\n\t\t\t\r\n\t}\t\t\t\t<\/style>\r\n\t\t\t\t<div id=\"tab_container_12388\" >\r\n\t \r\n\t\t\t\t\t<ul class=\"wpsm_nav wpsm_nav-tabs\" role=\"tablist\" id=\"myTab_12388\">\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  class=\"active\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_12388_1\" aria-controls=\"tabs_desc_12388_1\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>C++<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\t\t\t\t <\/ul>\r\n\r\n\t\t\t\t\t  <!-- Tab panes -->\r\n\t\t\t\t\t  <div class=\"tab-content\" id=\"tab-content_12388\">\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane  in active \" id=\"tabs_desc_12388_1\">\r\n\t\t\t\t\t\t\t\t<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\"> \r\n#include &lt;bits\/stdc++.h&gt;\r\nusing namespace std;\r\n \r\n\r\n \r\nclass DSU {\r\n    int* parent;\r\n    int* rank;\r\n \r\npublic:\r\n    DSU(int n)\r\n    {\r\n        parent = new int[n];\r\n        rank = new int[n];\r\n \r\n        for (int i = 0; i &lt; n; i++) {\r\n            parent[i] = -1;\r\n            rank[i] = 1;\r\n        }\r\n    }\r\n \r\n    \/\/ Find function\r\n    int find(int i)\r\n    {\r\n        if (parent[i] == -1)\r\n            return i;\r\n \r\n        return parent[i] = find(parent[i]);\r\n    }\r\n \r\n    \/\/ Union function\r\n    void unite(int x, int y)\r\n    {\r\n        int s1 = find(x);\r\n        int s2 = find(y);\r\n \r\n        if (s1 != s2) {\r\n            if (rank[s1] &lt; rank[s2]) {\r\n                parent[s1] = s2;\r\n            }\r\n            else if (rank[s1] &gt; rank[s2]) {\r\n                parent[s2] = s1;\r\n            }\r\n            else {\r\n                parent[s2] = s1;\r\n                rank[s1] += 1;\r\n            }\r\n        }\r\n    }\r\n};\r\n \r\nclass Graph {\r\n    vector&lt;vector&lt;int&gt; &gt; edgelist;\r\n    int V;\r\n \r\npublic:\r\n    Graph(int V) { this-&gt;V = V; }\r\n \r\n    void addEdge(int x, int y, int w)\r\n    {\r\n        edgelist.push_back({ w, x, y });\r\n    }\r\n \r\n    void kruskals_mst()\r\n    {\r\n        \/\/ AS WE KNOW KRUSKA IS GREEDY ALGO \r\n        \/\/ WE SIMPLY SORT THE EDGES\r\n        sort(edgelist.begin(), edgelist.end());\r\n \r\n       \r\n        DSU s(V);\r\n        int ans = 0;\r\n        cout &lt;&lt; \"Following are the edges in the \"\r\n                \"constructed MST\"\r\n             &lt;&lt; endl;\r\n        for (auto edge : edgelist) {\r\n            int w = edge[0];\r\n            int x = edge[1];\r\n            int y = edge[2];\r\n \r\n           \r\n            if (s.find(x) != s.find(y)) {\r\n                s.unite(x, y);\r\n                ans += w;\r\n                cout &lt;&lt; x &lt;&lt; \" -- \" &lt;&lt; y &lt;&lt; \" == \" &lt;&lt; w\r\n                     &lt;&lt; endl;\r\n            }\r\n        }\r\n \r\n        cout &lt;&lt; \"Minimum Cost Spanning Tree: \" &lt;&lt; ans;\r\n    }\r\n};\r\n \r\n\r\nint main()\r\n{\r\n   \r\n    Graph g(7);\r\n    g.addEdge(0, 1, 3);\r\n    g.addEdge(0, 3, 6);\r\n    g.addEdge(1, 4, 3);\r\n    g.addEdge(2, 3, 2);\r\n    g.addEdge(2, 1, 1);\r\n    g.addEdge(2, 4, 6);\r\n    g.addEdge(2, 5, 4);\r\n    g.addEdge(2, 4, 6);\r\n    g.addEdge(3, 5, 2);\r\n    g.addEdge(3, 6, 4);\r\n \r\n    \/\/ Function call\r\n    g.kruskals_mst();\r\n    return 0;\r\n}<\/pre>\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t <\/div>\r\n\t\t\t\t\t \r\n\t\t\t\t <\/div>\r\n <script>\r\n\t\tjQuery(function () {\r\n\t\t\tjQuery('#myTab_12388 a:first').tab('show')\r\n\t\t});\r\n\t\t\r\n\t\t\t\tjQuery(function(){\r\n\t\t\tvar b=\"fadeIn\";\r\n\t\t\tvar c;\r\n\t\t\tvar a;\r\n\t\t\td(jQuery(\"#myTab_12388 a\"),jQuery(\"#tab-content_12388\"));function d(e,f,g){\r\n\t\t\t\te.click(function(i){\r\n\t\t\t\t\ti.preventDefault();\r\n\t\t\t\t\tjQuery(this).tab(\"show\");\r\n\t\t\t\t\tvar h=jQuery(this).data(\"easein\");\r\n\t\t\t\t\tif(c){c.removeClass(a);}\r\n\t\t\t\t\tif(h){f.find(\"div.active\").addClass(\"animated \"+h);a=h;}\r\n\t\t\t\t\telse{if(g){f.find(\"div.active\").addClass(\"animated \"+g);a=g;}else{f.find(\"div.active\").addClass(\"animated \"+b);a=b;}}c=f.find(\"div.active\");\r\n\t\t\t\t});\r\n\t\t\t}\r\n\t\t});\r\n\t\t\r\n\r\n\t\tfunction do_resize(){\r\n\r\n\t\t\tvar width=jQuery( '.tab-content .tab-pane iframe' ).width();\r\n\t\t\tvar height=jQuery( '.tab-content .tab-pane iframe' ).height();\r\n\r\n\t\t\tvar toggleSize = true;\r\n\t\t\tjQuery('iframe').animate({\r\n\t\t\t    width: toggleSize ? width : 640,\r\n\t\t\t    height: toggleSize ? height : 360\r\n\t\t\t  }, 250);\r\n\r\n\t\t\t  toggleSize = !toggleSize;\r\n\t\t}\r\n\r\n\r\n\t<\/script>\r\n\t\t\t\t\r\n\t\t\t\n<p><strong>Output:<\/strong><\/p>\n<pre><code>Following are the edges in the constructed MST\n2 -- 1 == 1\n2 -- 3 == 2\n3 -- 5 == 2\n0 -- 1 == 3\n1 -- 4 == 3\n3 -- 6 == 4\nMinimum Cost Spanning Tree: 15<\/code><\/pre>\n<p><strong>Explanation:<\/strong><br \/>\nFirst we sort all the edges in non-decreasing order of their weight and then we do greedily pick the edges means we simply pick the edges which have a minimum weight.<br \/>\nThen simply add these edges, and we use a union-find algorithm to detect the cycle.First, we simply pick the edges which have minimum weight and add the edges if after adding these edges form cycle. then we reject the edge for the tree. After getting all the vertices in our tree and this tree is a Minimum spanning tree. This is how this algorithm works.<\/p>\n<h3>Kruskal\u2019s Algorithm Time Complexity<\/h3>\n<p>O(ElogE) or O(ElogN), here E denotes no of edges and N denotes the total no of vertices. Sorting of edges takes O(ELogE) time. After sorting, we traverse through all edges and apply the find-union algorithm. The find and union operations can take at most O(log N) time. So overall complexity is O(ELogE + ELogN) time. The value of E can be at most O(N2), so O(log N) is O(LogE) the same. Therefore, the overall time complexity is O(E log E) or O(E log N)<\/p>\n<p><strong>Summary<\/strong><br \/>\nKruskal&#8217;s algorithm is a greedy algorithm used to find the minimum spanning tree of a connected, undirected graph. It starts with an empty forest and iteratively adds edges to it, always choosing the edge with the lowest weight that does not form a cycle. The process stops when all the vertices are connected in a single tree. Kruskal&#8217;s algorithm is based on the observation that a minimum spanning tree of a graph can be found by adding edges in increasing order of weight, as long as they do not form a cycle. It runs in time O(E log E) where E is the number of edges in the graph.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>In this article, we will study about Kruskal algorithm, its implementation, spanning tree, minimum spanning tree, and time complexity of this algorithm. What is a Spanning Tree? A spanning tree is a subset of a connected graph G in which every edge is connected, allowing traversal to any edge from a specific edge with or [&hellip;]<\/p>\n","protected":false},"author":52,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[1],"tags":[],"class_list":["post-12389","post","type-post","status-publish","format-standard","hentry","category-miscellaneous"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v25.8 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Kruskal\u2019s Algorithm | PrepBytes Blog<\/title>\n<meta name=\"description\" content=\"Kruskal&#039;s algorithm is a greedy algorithm used to find the minimum spanning tree of a connected, undirected graph.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/prepbytes.com\/blog\/kruskals-algorithm\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Kruskal\u2019s Algorithm | PrepBytes Blog\" \/>\n<meta property=\"og:description\" content=\"Kruskal&#039;s algorithm is a greedy algorithm used to find the minimum spanning tree of a connected, undirected graph.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/prepbytes.com\/blog\/kruskals-algorithm\/\" \/>\n<meta property=\"og:site_name\" content=\"PrepBytes Blog\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/prepbytes0211\/\" \/>\n<meta property=\"article:published_time\" content=\"2023-02-02T10:29:40+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2023-03-02T06:07:44+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1675333521339-Kruskal%E2%80%99s%20Algorithm.jpg\" \/>\n<meta name=\"author\" content=\"Prepbytes\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Prepbytes\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"3 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/prepbytes.com\/blog\/kruskals-algorithm\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/kruskals-algorithm\/\"},\"author\":{\"name\":\"Prepbytes\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e\"},\"headline\":\"Kruskal\u2019s Algorithm\",\"datePublished\":\"2023-02-02T10:29:40+00:00\",\"dateModified\":\"2023-03-02T06:07:44+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/kruskals-algorithm\/\"},\"wordCount\":591,\"commentCount\":0,\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/kruskals-algorithm\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1675333521339-Kruskal%E2%80%99s%20Algorithm.jpg\",\"articleSection\":[\"Miscellaneous\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/prepbytes.com\/blog\/kruskals-algorithm\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/prepbytes.com\/blog\/kruskals-algorithm\/\",\"url\":\"https:\/\/prepbytes.com\/blog\/kruskals-algorithm\/\",\"name\":\"Kruskal\u2019s Algorithm | PrepBytes Blog\",\"isPartOf\":{\"@id\":\"http:\/\/43.205.93.38\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/kruskals-algorithm\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/kruskals-algorithm\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1675333521339-Kruskal%E2%80%99s%20Algorithm.jpg\",\"datePublished\":\"2023-02-02T10:29:40+00:00\",\"dateModified\":\"2023-03-02T06:07:44+00:00\",\"description\":\"Kruskal's algorithm is a greedy algorithm used to find the minimum spanning tree of a connected, undirected graph.\",\"breadcrumb\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/kruskals-algorithm\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/prepbytes.com\/blog\/kruskals-algorithm\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/prepbytes.com\/blog\/kruskals-algorithm\/#primaryimage\",\"url\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1675333521339-Kruskal%E2%80%99s%20Algorithm.jpg\",\"contentUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1675333521339-Kruskal%E2%80%99s%20Algorithm.jpg\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/prepbytes.com\/blog\/kruskals-algorithm\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"http:\/\/43.205.93.38\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Miscellaneous\",\"item\":\"https:\/\/prepbytes.com\/blog\/category\/miscellaneous\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"Kruskal\u2019s Algorithm\"}]},{\"@type\":\"WebSite\",\"@id\":\"http:\/\/43.205.93.38\/#website\",\"url\":\"http:\/\/43.205.93.38\/\",\"name\":\"PrepBytes Blog\",\"description\":\"ONE-STOP RESOURCE FOR EVERYTHING RELATED TO CODING\",\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"http:\/\/43.205.93.38\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"http:\/\/43.205.93.38\/#organization\",\"name\":\"Prepbytes\",\"url\":\"http:\/\/43.205.93.38\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp\",\"contentUrl\":\"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp\",\"width\":160,\"height\":160,\"caption\":\"Prepbytes\"},\"image\":{\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/www.facebook.com\/prepbytes0211\/\",\"https:\/\/www.instagram.com\/prepbytes\/\",\"https:\/\/www.linkedin.com\/company\/prepbytes\/\",\"https:\/\/www.youtube.com\/channel\/UC0xGnHDrjUM1pDEK2Ka5imA\"]},{\"@type\":\"Person\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e\",\"name\":\"Prepbytes\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g\",\"caption\":\"Prepbytes\"},\"url\":\"https:\/\/prepbytes.com\/blog\/author\/gourav-jaincollegedekho-com\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Kruskal\u2019s Algorithm | PrepBytes Blog","description":"Kruskal's algorithm is a greedy algorithm used to find the minimum spanning tree of a connected, undirected graph.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/prepbytes.com\/blog\/kruskals-algorithm\/","og_locale":"en_US","og_type":"article","og_title":"Kruskal\u2019s Algorithm | PrepBytes Blog","og_description":"Kruskal's algorithm is a greedy algorithm used to find the minimum spanning tree of a connected, undirected graph.","og_url":"https:\/\/prepbytes.com\/blog\/kruskals-algorithm\/","og_site_name":"PrepBytes Blog","article_publisher":"https:\/\/www.facebook.com\/prepbytes0211\/","article_published_time":"2023-02-02T10:29:40+00:00","article_modified_time":"2023-03-02T06:07:44+00:00","og_image":[{"url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1675333521339-Kruskal%E2%80%99s%20Algorithm.jpg","type":"","width":"","height":""}],"author":"Prepbytes","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Prepbytes","Est. reading time":"3 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/prepbytes.com\/blog\/kruskals-algorithm\/#article","isPartOf":{"@id":"https:\/\/prepbytes.com\/blog\/kruskals-algorithm\/"},"author":{"name":"Prepbytes","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e"},"headline":"Kruskal\u2019s Algorithm","datePublished":"2023-02-02T10:29:40+00:00","dateModified":"2023-03-02T06:07:44+00:00","mainEntityOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/kruskals-algorithm\/"},"wordCount":591,"commentCount":0,"publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/kruskals-algorithm\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1675333521339-Kruskal%E2%80%99s%20Algorithm.jpg","articleSection":["Miscellaneous"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/prepbytes.com\/blog\/kruskals-algorithm\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/prepbytes.com\/blog\/kruskals-algorithm\/","url":"https:\/\/prepbytes.com\/blog\/kruskals-algorithm\/","name":"Kruskal\u2019s Algorithm | PrepBytes Blog","isPartOf":{"@id":"http:\/\/43.205.93.38\/#website"},"primaryImageOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/kruskals-algorithm\/#primaryimage"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/kruskals-algorithm\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1675333521339-Kruskal%E2%80%99s%20Algorithm.jpg","datePublished":"2023-02-02T10:29:40+00:00","dateModified":"2023-03-02T06:07:44+00:00","description":"Kruskal's algorithm is a greedy algorithm used to find the minimum spanning tree of a connected, undirected graph.","breadcrumb":{"@id":"https:\/\/prepbytes.com\/blog\/kruskals-algorithm\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/prepbytes.com\/blog\/kruskals-algorithm\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/prepbytes.com\/blog\/kruskals-algorithm\/#primaryimage","url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1675333521339-Kruskal%E2%80%99s%20Algorithm.jpg","contentUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1675333521339-Kruskal%E2%80%99s%20Algorithm.jpg"},{"@type":"BreadcrumbList","@id":"https:\/\/prepbytes.com\/blog\/kruskals-algorithm\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"http:\/\/43.205.93.38\/"},{"@type":"ListItem","position":2,"name":"Miscellaneous","item":"https:\/\/prepbytes.com\/blog\/category\/miscellaneous\/"},{"@type":"ListItem","position":3,"name":"Kruskal\u2019s Algorithm"}]},{"@type":"WebSite","@id":"http:\/\/43.205.93.38\/#website","url":"http:\/\/43.205.93.38\/","name":"PrepBytes Blog","description":"ONE-STOP RESOURCE FOR EVERYTHING RELATED TO CODING","publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"http:\/\/43.205.93.38\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"http:\/\/43.205.93.38\/#organization","name":"Prepbytes","url":"http:\/\/43.205.93.38\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/","url":"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp","contentUrl":"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp","width":160,"height":160,"caption":"Prepbytes"},"image":{"@id":"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/prepbytes0211\/","https:\/\/www.instagram.com\/prepbytes\/","https:\/\/www.linkedin.com\/company\/prepbytes\/","https:\/\/www.youtube.com\/channel\/UC0xGnHDrjUM1pDEK2Ka5imA"]},{"@type":"Person","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e","name":"Prepbytes","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g","caption":"Prepbytes"},"url":"https:\/\/prepbytes.com\/blog\/author\/gourav-jaincollegedekho-com\/"}]}},"_links":{"self":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/12389","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/users\/52"}],"replies":[{"embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/comments?post=12389"}],"version-history":[{"count":3,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/12389\/revisions"}],"predecessor-version":[{"id":12476,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/12389\/revisions\/12476"}],"wp:attachment":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/media?parent=12389"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/categories?post=12389"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/tags?post=12389"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}