{"id":182307,"date":"2024-03-20T01:13:00","date_gmt":"2024-03-20T00:13:00","guid":{"rendered":"https:\/\/liora.io\/en\/?p=182307"},"modified":"2026-08-08T13:53:12","modified_gmt":"2026-08-08T12:53:12","slug":"kruskal-algorithm-definition-and-purpose","status":"publish","type":"post","link":"https:\/\/liora.io\/en\/kruskal-algorithm-definition-and-purpose","title":{"rendered":"Kruskal Algorithm: Definition and Purpose"},"content":{"rendered":"\n<p><strong>Kruskal&#8217;s algorithm for optimizing connections within a network is one of the key concepts in Machine Learning. Find out how it works and why it&#8217;s so useful in everyday life.<\/strong><\/p>\n\n\n<h2 class=\"wp-block-heading\" id=\"what-is-the-kruskal-algorithm\">What is the Kruskal algorithm?<\/h2>\n\n\n<p>Designed in 1956 by Joseph Kruskal, Kruskal&#8217;s algorithm is used to find a minimum weight spanning tree (MWST) (also known as a minimum spanning tree (MST) or minimum subtending tree (MST)) in a non-oriented, weighted connected graph.<\/p>\n\n\n<p>Before going into detail, we need to define the terms below:<\/p>\n\n\n<ul class=\"wp-block-list\"><li><strong>Tree:<\/strong> corresponds to a connected graph with no cycle (or acyclic).<\/li><li><strong>Connected graph:<\/strong> this means that there is a path to all the vertices of the graph from any other vertex.<\/li><li><strong>Acyclic graph:<\/strong> this means that the cycle is interrupted to access all vertices.<\/li><li><strong>Weighted graph:<\/strong> each edge has a weight.<\/li><li><strong>Undirected graph:<\/strong> each edge can be traversed in either direction.<\/li><li><strong>Spanning tree:<\/strong> refers to a set of edges in a weighted graph that contains all vertices (but not necessarily all edges). The weight of the spanning tree is the sum of the weights of its edges.<\/li><li><strong>Minimum weight spanning tree (MWST):<\/strong> this is a spanning tree whose weight is as small as possible. In other words, it is a subset of edges that connects all the nodes in the graph where the sum of the edge weights is as low as possible.<\/li><\/ul>\n\n\n<p>The aim of Kruskal&#8217;s algorithm is to find this minimum-weight spanning tree.<\/p>\n\n\n<p>Good to know: in addition to Kruskal&#8217;s algorithm, you can also use Prim&#8217;s algorithm to find an ARPM.<\/p>\n\n\n<h2 class=\"wp-block-heading\" id=\"how-does-the-kruskal-algorithm-work\">How does the Kruskal algorithm work?<\/h2>\n\n\n<h3 class=\"wp-block-heading\" id=\"the-steps-of-the-kruskal-algorithm\">The steps of the Kruskal algorithm<\/h3>\n\n\n<p>To find the least-weight spanning tree, the <strong>Kruskal algorithm provides the following steps:<\/strong><\/p>\n\n\n<ul class=\"wp-block-list\"><li>Sort the edges (a) of the graph (G) by increasing weight. In doing so, the lightest edges are examined first.<\/li><li>Start with an empty tree (T). That is, a tree containing no edges; its weight is 0. Its construction is progressive, following these steps.<\/li><li>Select edges by ascending weight. Start with the lightest edges. If the addition of an edge does not imply the creation of a cycle in the graph, add it to the tree.<\/li><li>Repeat the operation until all vertices (S) are connected. And this without creating a cycle in the ARPM.<\/li><\/ul>\n\n\n<figure class=\"wp-block-image size-full\" style=\"margin-top:32px;margin-bottom:32px\"><img alt=\"Illustration for The steps of the Kruskal algorithm\" decoding=\"async\" height=\"500\" loading=\"lazy\" src=\"https:\/\/liora.io\/app\/uploads\/2023\/10\/algorithme-kruskal.jpg\" style=\"width:100%;height:auto\" width=\"927\"\/><\/figure>\n\n\n<div class=\"wp-block-buttons is-layout-flex wp-block-buttons-is-layout-flex is-content-justification-center wp-container-core-buttons-is-layout-5ee10de4\" style=\"margin-top:32px;margin-bottom:32px\"><div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"\/en\/courses\/data-ai\/data-scientist\">Training in Data Science<\/a><\/div><\/div>\n\n\n<h3 class=\"wp-block-heading\" id=\"mathematical-translation\">Mathematical translation<\/h3>\n\n\n<p>In <a href=\"https:\/\/liora.io\/en\/sequences-and-series-understanding-these-two-mathematical-concepts\">mathematical terms<\/a>, the Kruskal algorithm translates as follows:<\/p>\n\n\n<p>T = \u00f8<br\/>Sort the a&#8217;s in G by ascending value<br\/>F = { ao }<br\/>Repeat F = { ao } until all S have been included in T<\/p>\n\n\n<p>Where<\/p>\n\n\n<p>ao : smallest unexamined edge <br\/>T : minimum weight spanning tree <br\/>G : graph<br\/>S : vertex <br\/>p: number of edges already placed in the G graph<br\/>n : number of vertices in graph G<br\/>F = { ao } :addition of the smallest unexamined edge<\/p>\n\n\n<p><strong>Good to know:<\/strong> The number of edges in an ARPM can vary by (n-1)n\/2 . The fewer edges the minimum-weight spanning tree contains, the faster the <strong>Kruskal algorithm.<\/strong><\/p>\n\n\n<h2 class=\"wp-block-heading\" id=\"why-use-the-kruskal-algorithm\">Why use the Kruskal algorithm?<\/h2>\n\n\n<p>In practice, this<strong> algorithm<\/strong> is often used to solve practical problems such as the design of low-cost communication networks, cabling planning, the elimination of less profitable sea links while preserving accessibility to different ports, and so on.<\/p>\n\n\n<p>Whatever the practical application,<strong> Kruskal&#8217;s<\/strong> algorithm enables connections to be optimized. This is precisely why it is so useful in<a href=\"https:\/\/liora.io\/en\/boosting-business-with-3-essential-machine-learning-algorithms\"> Machine Learning<\/a>. By optimizing the weight of connections, it maximizes the efficiency of machine learning models.<\/p>\n\n\n<p>Good to know: you can use Kruskal&#8217;s algorithm in a variety of programming languages, such as <a href=\"https:\/\/liora.io\/en\/c-what-is-this-computer-language-for\">C++<\/a>, Python, Java, C#, Javascript, etc.<\/p>\n\n\n<h2 class=\"wp-block-heading\" id=\"deepen-your-knowledge-of-machine-learning-with-liora\">Deepen your knowledge of Machine Learning with Liora<\/h2>\n\n\n<p>Beyond the <strong>Kruskal algorithm<\/strong>,<a href=\"https:\/\/liora.io\/en\/unraveling-machine-learning-vs-deep-learning-key-differences-explained\"> Machine Learning<\/a> requires mastery of a multitude of mathematical and statistical concepts, not to mention programming languages, <a href=\"https:\/\/liora.io\/en\/big-data-for-dummies\">Big Data tools<\/a>, data visualization and more. These are all technical skills that can only be learned through comprehensive training. Like the one offered by Liora. Discover our program.<\/p>\n\n\n<figure class=\"wp-block-image size-full\" style=\"margin-top:32px;margin-bottom:32px\"><img alt=\"Illustration for Deepen your knowledge of Machine Learning with Liora\" decoding=\"async\" height=\"500\" loading=\"lazy\" src=\"https:\/\/liora.io\/app\/uploads\/2023\/10\/algorithme-kruskal1.jpg\" style=\"width:100%;height:auto\" width=\"814\"\/><\/figure>\n\n\n<div class=\"wp-block-buttons is-layout-flex wp-block-buttons-is-layout-flex is-content-justification-center wp-container-core-buttons-is-layout-5ee10de4\" style=\"margin-top:32px;margin-bottom:32px\"><div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"\/en\/courses\/data-ai\/data-scientist\">Learn to use the algorithm<\/a><\/div><\/div>\n\n","protected":false},"excerpt":{"rendered":"<p>Kruskal&#8217;s algorithm for optimizing connections within a network is one of the key concepts in Machine Learning. Find out how it works and why it&#8217;s so useful in everyday life. What is the Kruskal algorithm? Designed in 1956 by Joseph Kruskal, Kruskal&#8217;s algorithm is used to find a minimum weight spanning tree (MWST) (also known [&hellip;]<\/p>\n","protected":false},"author":76,"featured_media":182312,"comment_status":"open","ping_status":"open","sticky":false,"template":"elementor_theme","format":"standard","meta":{"_acf_changed":false,"editor_notices":[],"footnotes":""},"categories":[2434],"class_list":["post-182307","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-cloud-dev"],"acf":[],"_links":{"self":[{"href":"https:\/\/liora.io\/en\/wp-json\/wp\/v2\/posts\/182307","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/liora.io\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/liora.io\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/liora.io\/en\/wp-json\/wp\/v2\/users\/76"}],"replies":[{"embeddable":true,"href":"https:\/\/liora.io\/en\/wp-json\/wp\/v2\/comments?post=182307"}],"version-history":[{"count":2,"href":"https:\/\/liora.io\/en\/wp-json\/wp\/v2\/posts\/182307\/revisions"}],"predecessor-version":[{"id":210388,"href":"https:\/\/liora.io\/en\/wp-json\/wp\/v2\/posts\/182307\/revisions\/210388"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/liora.io\/en\/wp-json\/wp\/v2\/media\/182312"}],"wp:attachment":[{"href":"https:\/\/liora.io\/en\/wp-json\/wp\/v2\/media?parent=182307"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/liora.io\/en\/wp-json\/wp\/v2\/categories?post=182307"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}