{"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-02-06T08:20:25","modified_gmt":"2026-02-06T07:20:25","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":"<style>\n.elementor-heading-title{padding:0;margin:0;line-height:1}.elementor-widget-heading .elementor-heading-title[class*=elementor-size-]>a{color:inherit;font-size:inherit;line-height:inherit}.elementor-widget-heading .elementor-heading-title.elementor-size-small{font-size:15px}.elementor-widget-heading .elementor-heading-title.elementor-size-medium{font-size:19px}.elementor-widget-heading .elementor-heading-title.elementor-size-large{font-size:29px}.elementor-widget-heading .elementor-heading-title.elementor-size-xl{font-size:39px}.elementor-widget-heading .elementor-heading-title.elementor-size-xxl{font-size:59px}<\/style><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>\t\t\n\t\t\t<h3>What is the Kruskal algorithm?<\/h3>\t\t\n\t\t<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><p>Before going into detail, we need to define the terms below:<\/p><ul><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><p>The aim of Kruskal&#8217;s algorithm is to find this minimum-weight spanning tree.<\/p><p>Good to know: in addition to Kruskal&#8217;s algorithm, you can also use Prim&#8217;s algorithm to find an ARPM.<\/p>\t\t\n\t\t\t<h3>How does the Kruskal algorithm work?<\/h3>\t\t\n\t\t\t<h4>The steps of the Kruskal algorithm<\/h4>\t\t\n\t\t<p>To find the least-weight spanning tree, the <strong>Kruskal algorithm provides the following steps:<\/strong><\/p><ul><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>\t\t\n\t\t\t<style>\n.elementor-widget-image{text-align:center}.elementor-widget-image a{display:inline-block}.elementor-widget-image a img[src$=\".svg\"]{width:48px}.elementor-widget-image img{vertical-align:middle;display:inline-block}<\/style>\t\t\t\t\t\t\t\t\t<figure>\n\t\t\t\t\t\t\t\t\t\t<img decoding=\"async\" src=\"https:\/\/liora.io\/app\/uploads\/2023\/10\/algorithme-kruskal.jpg\" title=\"\" alt=\"\" loading=\"lazy\">\t\t\t\t\t\t\t\t\t\t\t<figcaption><\/figcaption>\n\t\t\t\t\t\t\t\t\t\t<\/figure>\n\t\t\t\n<div class=\"wp-block-buttons is-layout-flex wp-block-buttons-is-layout-flex is-content-justification-center\"><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\t\t\t<h4>Mathematical translation<\/h4>\t\t\n\t\t<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><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><p>Where<\/p><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><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>\t\t\n\t\t\t<h3>Why use the Kruskal algorithm?<\/h3>\t\t\n\t\t<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><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><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>\t\t\n\t\t\t<h3>Deepen your knowledge of Machine Learning with Liora<\/h3>\t\t\n\t\t<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>\t\t\n\t\t\t\t\t\t\t\t\t\t\t\t<figure>\n\t\t\t\t\t\t\t\t\t\t<img decoding=\"async\" src=\"https:\/\/liora.io\/app\/uploads\/2023\/10\/algorithme-kruskal1.jpg\" title=\"\" alt=\"\" loading=\"lazy\">\t\t\t\t\t\t\t\t\t\t\t<figcaption><\/figcaption>\n\t\t\t\t\t\t\t\t\t\t<\/figure>\n\t\t\t\n<div class=\"wp-block-buttons is-layout-flex wp-block-buttons-is-layout-flex is-content-justification-center\"><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","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":1,"href":"https:\/\/liora.io\/en\/wp-json\/wp\/v2\/posts\/182307\/revisions"}],"predecessor-version":[{"id":205944,"href":"https:\/\/liora.io\/en\/wp-json\/wp\/v2\/posts\/182307\/revisions\/205944"}],"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}]}}