{"id":217960,"date":"2023-12-12T06:30:00","date_gmt":"2023-12-12T06:30:00","guid":{"rendered":"https:\/\/datascientest.com\/?p=217960"},"modified":"2023-12-08T13:31:32","modified_gmt":"2023-12-08T13:31:32","slug":"algorithme-de-kruskal-tout-savoir","status":"publish","type":"post","link":"https:\/\/datascientest.com\/algorithme-de-kruskal-tout-savoir","title":{"rendered":"L\u2019algorithme de Kruskal : Qu&rsquo;est ce que c&rsquo;est ? Quel est son but ?"},"content":{"rendered":"\t\t<div data-elementor-type=\"wp-post\" data-elementor-id=\"217960\" class=\"elementor elementor-217960\" data-elementor-post-type=\"post\">\n\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-022a9d1 e-flex e-con-boxed e-con\" data-id=\"022a9d1\" data-element_type=\"container\" data-settings=\"{&quot;content_width&quot;:&quot;boxed&quot;}\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t\t\t<div class=\"elementor-element elementor-element-0fcddd2 elementor-widget elementor-widget-heading\" data-id=\"0fcddd2\" data-element_type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<style>\/*! elementor - v3.15.0 - 02-08-2023 *\/\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><h2 class=\"elementor-heading-title elementor-size-default\">Permettant d\u2019optimiser les connexions au sein d\u2019un r\u00e9seau, l\u2019algorithme de Kruskal figure parmi les concepts incontournables en Machine Learning. D\u00e9couvrez son fonctionnement et son int\u00e9r\u00eat au quotidien. <\/h2>\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-8331be0 e-flex e-con-boxed e-con\" data-id=\"8331be0\" data-element_type=\"container\" data-settings=\"{&quot;content_width&quot;:&quot;boxed&quot;}\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t\t\t<div class=\"elementor-element elementor-element-c49a4f4 elementor-widget elementor-widget-heading\" data-id=\"c49a4f4\" data-element_type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<h3 class=\"elementor-heading-title elementor-size-default\">C\u2019est quoi l\u2019algorithme de Kruskal ?<\/h3>\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-e768dd7 elementor-widget elementor-widget-text-editor\" data-id=\"e768dd7\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<style>\/*! elementor - v3.15.0 - 02-08-2023 *\/\n.elementor-widget-text-editor.elementor-drop-cap-view-stacked .elementor-drop-cap{background-color:#69727d;color:#fff}.elementor-widget-text-editor.elementor-drop-cap-view-framed .elementor-drop-cap{color:#69727d;border:3px solid;background-color:transparent}.elementor-widget-text-editor:not(.elementor-drop-cap-view-default) .elementor-drop-cap{margin-top:8px}.elementor-widget-text-editor:not(.elementor-drop-cap-view-default) .elementor-drop-cap-letter{width:1em;height:1em}.elementor-widget-text-editor .elementor-drop-cap{float:left;text-align:center;line-height:1;font-size:50px}.elementor-widget-text-editor .elementor-drop-cap-letter{display:inline-block}<\/style>\t\t\t\t<p><span style=\"font-weight: 400;\">Con\u00e7u en 1956 par Joseph Kruskal, l&rsquo;algorithme de Kruskal permet de<\/span><b> trouver un arbre recouvrant de poids minimum <\/b><span style=\"font-weight: 400;\">(ARPM) (\u00e9galement appel\u00e9 arbre couvrant minimum (ACM) ou arbre sous-tendant minimum) <\/span><b>dans un graphe connexe non-orient\u00e9 et pond\u00e9r\u00e9.<\/b><\/p><p><span style=\"font-weight: 400;\">Avant de rentrer dans les d\u00e9tails, il convient de d\u00e9finir les termes ci-dessous :\u00a0<\/span><\/p><ul><li style=\"font-weight: 400;\" aria-level=\"1\"><b>Arbre<\/b><span style=\"font-weight: 400;\"> : il correspond \u00e0 un graphique connexe et sans cycle (ou acyclique).\u00a0<\/span><\/li><\/ul><ul><li style=\"font-weight: 400;\" aria-level=\"1\"><b>Graphe connexe<\/b><span style=\"font-weight: 400;\"> : cela signifie qu\u2019il existe un chemin permettant d\u2019acc\u00e9der \u00e0 tous les sommets du graphique depuis n\u2019importe quel autre sommet.<\/span><\/li><li style=\"font-weight: 400;\" aria-level=\"1\"><b>Graphe acyclique :<\/b><span style=\"font-weight: 400;\"> cela signifie que le cycle s\u2019interrompt pour acc\u00e9der \u00e0 tous les sommets.\u00a0<\/span><\/li><li style=\"font-weight: 400;\" aria-level=\"1\"><b>Graphe pond\u00e9r\u00e9<\/b><span style=\"font-weight: 400;\"> : chaque ar\u00eate poss\u00e8de un poids.\u00a0<\/span><\/li><li style=\"font-weight: 400;\" aria-level=\"1\"><b>Graphe non orient\u00e9<\/b><span style=\"font-weight: 400;\"> : chaque ar\u00eate peut \u00eatre parcourue dans les deux sens.\u00a0<\/span><\/li><li style=\"font-weight: 400;\" aria-level=\"1\"><b>Arbre couvrant :<\/b><span style=\"font-weight: 400;\"> il renvoie \u00e0 un ensemble d\u2019ar\u00eates d\u2019un graphe pond\u00e9r\u00e9 qui contient tous les sommets (mais pas forc\u00e9ment toutes les ar\u00eates). Le poids de l\u2019arbre couvrant est la somme des poids de ses ar\u00eates.\u00a0<\/span><\/li><li><b>Arbre recouvrant de poids minimum (ARPM)<\/b><span style=\"font-weight: 400;\"> : il s\u2019agit d\u2019un arbre couvrant dont le poids est le plus petit possible. Autrement dit, il s\u2019agit d\u2019un sous-ensemble d&rsquo;ar\u00eates qui connecte tous les n\u0153uds du graphe o\u00f9 la somme des poids des ar\u00eates est la plus basse possible.<\/span><\/li><\/ul>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-2b76f83 elementor-widget elementor-widget-text-editor\" data-id=\"2b76f83\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<p><span style=\"font-weight: 400;\">L\u2019objectif de l\u2019algorithme de Kruskal est justement de retrouver cet arbre recouvrant de poids minimum.\u00a0<\/span><\/p><p><span style=\"font-weight: 400;\"><span style=\"text-decoration: underline;\"><strong>Bon \u00e0 savoir<\/strong><\/span> : en plus de l\u2019algorithme de Kruskal, il est aussi possible d\u2019utiliser l\u2019algorithme de Prim pour trouver un ARPM. <\/span><\/p>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-9d4f18d e-flex e-con-boxed e-con\" data-id=\"9d4f18d\" data-element_type=\"container\" data-settings=\"{&quot;content_width&quot;:&quot;boxed&quot;}\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t\t\t<div class=\"elementor-element elementor-element-f178772 elementor-widget elementor-widget-heading\" data-id=\"f178772\" data-element_type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<h3 class=\"elementor-heading-title elementor-size-default\">Comment fonctionne l'algorithme de Kruskal ?<\/h3>\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-30ad016 elementor-widget elementor-widget-heading\" data-id=\"30ad016\" data-element_type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<h4 class=\"elementor-heading-title elementor-size-medium\">Les \u00e9tapes de l\u2019algorithme de Kruskal<\/h4>\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-f4642ea elementor-widget elementor-widget-text-editor\" data-id=\"f4642ea\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<p><span style=\"font-weight: 400;\">Pour trouver l\u2019arbre recouvrant de poids minimum, l\u2019algorithme de Kruskal\u00a0 pr\u00e9voit les \u00e9tapes ci-dessous :\u00a0<\/span><\/p><ul><li style=\"font-weight: 400;\" aria-level=\"1\"><span style=\"font-weight: 400;\">Trier les ar\u00eates (a) du graphique (G) par poids croissant. Ce faisant, les ar\u00eates les plus l\u00e9g\u00e8res sont examin\u00e9es en premi\u00e8res.\u00a0<\/span><\/li><li style=\"font-weight: 400;\" aria-level=\"1\"><span style=\"font-weight: 400;\">Partir d\u2019un arbre (T) vide. C\u2019est-\u00e0-dire un arbre qui ne contient aucune ar\u00eate ; son poids est \u00e9gal \u00e0 0. Sa construction est progressive en suivant les \u00e9tapes suivantes.\u00a0<\/span><\/li><li style=\"font-weight: 400;\" aria-level=\"1\"><span style=\"font-weight: 400;\">S\u00e9lectionner les ar\u00eates par poids croissant. Il faut donc commencer par les ar\u00eates les plus l\u00e9g\u00e8res. Si l\u2019ajout d\u2019une ar\u00eate n\u2019implique pas la cr\u00e9ation d\u2019un cycle dans le graphe, il convient de l\u2019ajouter \u00e0 l\u2019arbre.\u00a0<\/span><\/li><li style=\"font-weight: 400;\" aria-level=\"1\"><span style=\"font-weight: 400;\">R\u00e9p\u00e9tez l\u2019op\u00e9ration jusqu\u2019\u00e0 ce que tous les sommets (S) soient reli\u00e9s. Et ce, sans cr\u00e9er de cycle dans l\u2019ARPM. <\/span><\/li><\/ul>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-e4e79da elementor-widget elementor-widget-image\" data-id=\"e4e79da\" data-element_type=\"widget\" data-widget_type=\"image.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<style>\/*! elementor - v3.15.0 - 02-08-2023 *\/\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\t\t\t<img decoding=\"async\" width=\"927\" height=\"500\" src=\"https:\/\/datascientest.com\/wp-content\/uploads\/2023\/10\/algorithme-kruskal.jpg\" class=\"attachment-full size-full wp-image-217981\" alt=\"\" srcset=\"https:\/\/datascientest.com\/wp-content\/uploads\/2023\/10\/algorithme-kruskal.jpg 927w, https:\/\/datascientest.com\/wp-content\/uploads\/2023\/10\/algorithme-kruskal-300x162.jpg 300w, https:\/\/datascientest.com\/wp-content\/uploads\/2023\/10\/algorithme-kruskal-768x414.jpg 768w\" sizes=\"(max-width: 927px) 100vw, 927px\" \/>\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-e548686 elementor-align-center button-principale elementor-widget elementor-widget-button\" data-id=\"e548686\" data-element_type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm elementor-animation-grow\" href=\"https:\/\/datascientest.com\/formation-data-scientist\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t<span class=\"elementor-button-text\">Se former \u00e0 la Data Science<\/span>\n\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-a8fafb7 elementor-widget elementor-widget-heading\" data-id=\"a8fafb7\" data-element_type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<h4 class=\"elementor-heading-title elementor-size-medium\">La traduction math\u00e9matique<\/h4>\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-f211b42 elementor-widget elementor-widget-text-editor\" data-id=\"f211b42\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<p><span style=\"font-weight: 400;\">En math\u00e9matique, l\u2019algorithme de Kruskal se traduit comme suit :\u00a0<\/span><\/p><ol><li><span style=\"font-weight: 400;\">T = \u00f8<\/span><\/li><li><span style=\"font-weight: 400;\">Trier les a de G par valeurs croissantes<\/span><\/li><li><span style=\"font-weight: 400;\">F = { ao }<\/span><\/li><li><span style=\"font-weight: 400;\">R\u00e9p\u00e9tez F = { ao } tant que tous les S n\u2019ont pas \u00e9t\u00e9 int\u00e9gr\u00e9s \u00e0 T<\/span><\/li><\/ol><p><span style=\"font-weight: 400;\">O\u00f9\u00a0<\/span><\/p><ul><li style=\"font-weight: 400;\" aria-level=\"1\"><span style=\"font-weight: 400;\">ao : la plus petite ar\u00eate non examin\u00e9e\u00a0<\/span><\/li><li style=\"font-weight: 400;\" aria-level=\"1\"><span style=\"font-weight: 400;\">T : arbre recouvrant de poids minimum\u00a0<\/span><\/li><li style=\"font-weight: 400;\" aria-level=\"1\"><span style=\"font-weight: 400;\">G : graphique<\/span><\/li><li style=\"font-weight: 400;\" aria-level=\"1\"><span style=\"font-weight: 400;\">S : sommet\u00a0<\/span><\/li><li style=\"font-weight: 400;\" aria-level=\"1\"><span style=\"font-weight: 400;\">p : le nombre d\u2019ar\u00eates d\u00e9j\u00e0 plac\u00e9es dans le graphe G<\/span><\/li><li style=\"font-weight: 400;\" aria-level=\"1\"><span style=\"font-weight: 400;\">n : le nombre de sommets du graphe G<\/span><\/li><li style=\"font-weight: 400;\" aria-level=\"1\"><span style=\"font-weight: 400;\">F = { ao } :ajout de la plus petite ar\u00eate non examin\u00e9e <\/span><\/li><\/ul>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-63585cf elementor-widget elementor-widget-text-editor\" data-id=\"63585cf\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<p><span style=\"font-weight: 400;\"><span style=\"text-decoration: underline;\"><strong>Bon \u00e0 savoir<\/strong><\/span> : Le nombre d&rsquo;ar\u00eates d&rsquo;un ARPM peut varier de (<em>n<\/em>-1)<em>n<\/em>\/2 <\/span><span style=\"font-weight: 400;\">.Moins l\u2019arbre recouvrant de poids minimum contient d\u2019ar\u00eates, plus l\u2019algorithme de Kruskal est rapide.<\/span><\/p>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-2c36421 e-flex e-con-boxed e-con\" data-id=\"2c36421\" data-element_type=\"container\" data-settings=\"{&quot;content_width&quot;:&quot;boxed&quot;}\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t\t\t<div class=\"elementor-element elementor-element-8ebcec7 elementor-widget elementor-widget-heading\" data-id=\"8ebcec7\" data-element_type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<h3 class=\"elementor-heading-title elementor-size-default\">Pourquoi utiliser l\u2019algorithme de Kruskal ?<\/h3>\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-c430867 elementor-widget elementor-widget-text-editor\" data-id=\"c430867\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<p><span style=\"font-weight: 400;\">Dans la pratique, cet <a href=\"https:\/\/datascientest.com\/algorithme-tout-savoir\">algorithme<\/a> est souvent utilis\u00e9 pour r\u00e9soudre des\u00a0 probl\u00e8mes pratiques tels que la conception de r\u00e9seaux de communication \u00e0 moindre co\u00fbt, la planification de c\u00e2blage, la suppression des liaisons maritimes les moins rentables tout en pr\u00e9servant l&rsquo;accessibilit\u00e9 aux diff\u00e9rents ports, etc.<\/span><\/p><p><span style=\"font-weight: 400;\">Quelle que soit l\u2019utilisation concr\u00e8te, l\u2019algorithme de Kruskal permet d<\/span><b>\u2019optimiser les connexions.<\/b><span style=\"font-weight: 400;\"> C\u2019est justement pour cette raison qu\u2019il est particuli\u00e8rement utile en <a href=\"https:\/\/datascientest.com\/machine-learning-tout-savoir\">Machine Learning<\/a>. En optimisant le poids des connexions, il permet <\/span><b>d\u2019optimiser l\u2019efficacit\u00e9 des<\/b> <a href=\"https:\/\/datascientest.com\/apprentissage-automatique\">mod\u00e8les d\u2019apprentissage automatique<\/a>.<\/p><p><span style=\"text-decoration: underline;\"><strong>Bon \u00e0 savoir<\/strong><\/span> : vous pouvez utiliser l\u2019algorithme de Kruskal \u00e0 travers diff\u00e9rents langages de programmation, comme C++, <a href=\"https:\/\/datascientest.com\/python-tout-savoir\"><span style=\"font-weight: 400;\">Python<\/span><\/a>, Java, C#, Javascript, etc.<\/p>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-dd106d6 e-flex e-con-boxed e-con\" data-id=\"dd106d6\" data-element_type=\"container\" data-settings=\"{&quot;content_width&quot;:&quot;boxed&quot;}\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t\t\t<div class=\"elementor-element elementor-element-81b0338 elementor-widget elementor-widget-heading\" data-id=\"81b0338\" data-element_type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<h3 class=\"elementor-heading-title elementor-size-default\">Approfondissez vos connaissances en Machine Learning  avec DataScientest<\/h3>\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-885297e elementor-widget elementor-widget-text-editor\" data-id=\"885297e\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<span style=\"font-weight: 400;\">Au-del\u00e0 de l\u2019algorithme de Kruskal, le Machine Learning n\u00e9cessite de ma\u00eetriser une multitude de concepts math\u00e9matiques et statistiques, sans oublier les langages de programmation, les outils de Big Data, de data visualisation, etc. Autant de comp\u00e9tences techniques qui ne s\u2019apprennent qu\u2019\u00e0 travers une formation compl\u00e8te. Comme celle propos\u00e9e par DataScientest. <a href=\"https:\/\/datascientest.com\/formation-data-scientist\">D\u00e9couvrez notre programme<\/a>.<\/span>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-dbfb5e4 elementor-widget elementor-widget-image\" data-id=\"dbfb5e4\" data-element_type=\"widget\" data-widget_type=\"image.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<img decoding=\"async\" width=\"814\" height=\"500\" src=\"https:\/\/datascientest.com\/wp-content\/uploads\/2023\/10\/algorithme-kruskal1.jpg\" class=\"attachment-full size-full wp-image-217985\" alt=\"\" srcset=\"https:\/\/datascientest.com\/wp-content\/uploads\/2023\/10\/algorithme-kruskal1.jpg 814w, https:\/\/datascientest.com\/wp-content\/uploads\/2023\/10\/algorithme-kruskal1-300x184.jpg 300w, https:\/\/datascientest.com\/wp-content\/uploads\/2023\/10\/algorithme-kruskal1-768x472.jpg 768w\" sizes=\"(max-width: 814px) 100vw, 814px\" \/>\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-0eac32f elementor-align-center button-principale elementor-widget elementor-widget-button\" data-id=\"0eac32f\" data-element_type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm elementor-animation-grow\" href=\"https:\/\/datascientest.com\/formation-data-scientist\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t<span class=\"elementor-button-text\">Apprendre \u00e0 utiliser l'algorithme<\/span>\n\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-03b4f80 e-flex e-con-boxed e-con\" data-id=\"03b4f80\" data-element_type=\"container\" data-settings=\"{&quot;content_width&quot;:&quot;boxed&quot;}\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t\t\t<div class=\"elementor-element elementor-element-69174ea elementor-widget elementor-widget-html\" data-id=\"69174ea\" data-element_type=\"widget\" data-widget_type=\"html.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<script type=\"application\/ld+json\">\r\n{\r\n  \"@context\": \"https:\/\/schema.org\",\r\n  \"@type\": \"FAQPage\",\r\n  \"mainEntity\": [{\r\n    \"@type\": \"Question\",\r\n    \"name\": \"https:\/\/datascientest.com\/business-intelligence\",\r\n    \"acceptedAnswer\": {\r\n      \"@type\": \"Answer\",\r\n      \"text\": \"Con\u00e7u en 1956 par Joseph Kruskal, l'algorithme de Kruskal permet de trouver un arbre recouvrant de poids minimum (ARPM) (\u00e9galement appel\u00e9 arbre couvrant minimum (ACM) ou arbre sous-tendant minimum) dans un graphe connexe non-orient\u00e9 et pond\u00e9r\u00e9.\"\r\n    }\r\n  },{\r\n    \"@type\": \"Question\",\r\n    \"name\": \"Comment fonctionne l'algorithme de Kruskal ?\",\r\n    \"acceptedAnswer\": {\r\n      \"@type\": \"Answer\",\r\n      \"text\": \"Pour trouver l\u2019arbre recouvrant de poids minimum, l\u2019algorithme de Kruskal  pr\u00e9voit les \u00e9tapes ci-dessous : Trier les ar\u00eates (a) du graphique (G) par poids croissant. Ce faisant, les ar\u00eates les plus l\u00e9g\u00e8res sont examin\u00e9es en premi\u00e8res. Partir d\u2019un arbre (T) vide. C\u2019est-\u00e0-dire un arbre qui ne contient aucune ar\u00eate ; son poids est \u00e9gal \u00e0 0. Sa construction est progressive en suivant les \u00e9tapes suivantes. S\u00e9lectionner les ar\u00eates par poids croissant. Il faut donc commencer par les ar\u00eates les plus l\u00e9g\u00e8res. Si l\u2019ajout d\u2019une ar\u00eate n\u2019implique pas la cr\u00e9ation d\u2019un cycle dans le graphe, il convient de l\u2019ajouter \u00e0 l\u2019arbre.  R\u00e9p\u00e9tez l\u2019op\u00e9ration jusqu\u2019\u00e0 ce que tous les sommets (S) soient reli\u00e9s. Et ce, sans cr\u00e9er de cycle dans l\u2019ARPM.\"\r\n    }\r\n  },{\r\n    \"@type\": \"Question\",\r\n    \"name\": \"Pourquoi utiliser l\u2019algorithme de Kruskal ?\",\r\n    \"acceptedAnswer\": {\r\n      \"@type\": \"Answer\",\r\n      \"text\": \"Dans la pratique, cet algorithme est souvent utilis\u00e9 pour r\u00e9soudre des  probl\u00e8mes pratiques tels que la conception de r\u00e9seaux de communication \u00e0 moindre co\u00fbt, la planification de c\u00e2blage, la suppression des liaisons maritimes les moins rentables tout en pr\u00e9servant l'accessibilit\u00e9 aux diff\u00e9rents ports, etc. Quelle que soit l\u2019utilisation concr\u00e8te, l\u2019algorithme de Kruskal permet d\u2019optimiser les connexions. C\u2019est justement pour cette raison qu\u2019il est particuli\u00e8rement utile en Machine Learning. En optimisant le poids des connexions, il permet d\u2019optimiser l\u2019efficacit\u00e9 des mod\u00e8les d\u2019apprentissage automatique.\"\r\n    }\r\n  }]\r\n}\r\n<\/script>\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"<p>Permettant d\u2019optimiser les connexions au sein d\u2019un r\u00e9seau, l\u2019algorithme de Kruskal figure parmi les concepts incontournables en Machine Learning. D\u00e9couvrez son fonctionnement et son int\u00e9r\u00eat au quotidien. C\u2019est quoi l\u2019algorithme de Kruskal ? Con\u00e7u en 1956 par Joseph Kruskal, l&rsquo;algorithme de Kruskal permet de trouver un arbre recouvrant de poids minimum (ARPM) (\u00e9galement appel\u00e9 arbre [&hellip;]<\/p>\n","protected":false},"author":77,"featured_media":217962,"comment_status":"open","ping_status":"open","sticky":false,"template":"elementor_theme","format":"standard","meta":{"content-type":"","inline_featured_image":false},"categories":[2497],"tags":[],"yoast_head":"<!-- This site is optimized with the Yoast SEO Premium plugin v21.7 (Yoast SEO v21.7) - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>L\u2019algorithme de Kruskal : Qu&#039;est ce que c&#039;est ? Quel est son but ?<\/title>\n<meta name=\"description\" content=\"En recherchant l\u2019arbre recouvrant de poids minimum, l\u2019algorithme de Kruskal optimise les connexions existantes dans tous types de r\u00e9seaux. D\u00e9couvrez tout ce qu&#039;il faut savoir sur cet algorithme\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/datascientest.com\/algorithme-de-kruskal-tout-savoir\" \/>\n<meta property=\"og:locale\" content=\"fr_FR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"L\u2019algorithme de Kruskal : Qu&#039;est ce que c&#039;est ? Quel est son but ?\" \/>\n<meta property=\"og:url\" content=\"https:\/\/datascientest.com\/algorithme-de-kruskal-tout-savoir\" \/>\n<meta property=\"og:site_name\" content=\"Formation Data Science | DataScientest.com\" \/>\n<meta property=\"article:published_time\" content=\"2023-12-12T06:30:00+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2023-12-08T13:31:32+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/datascientest.com\/wp-content\/uploads\/2023\/10\/algorithme-de-kruskal.png\" \/>\n\t<meta property=\"og:image:width\" content=\"1200\" \/>\n\t<meta property=\"og:image:height\" content=\"600\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/png\" \/>\n<meta name=\"author\" content=\"Raphael Kassel\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"\u00c9crit par\" \/>\n\t<meta name=\"twitter:data1\" content=\"Raphael Kassel\" \/>\n\t<meta name=\"twitter:label2\" content=\"Dur\u00e9e de lecture estim\u00e9e\" \/>\n\t<meta name=\"twitter:data2\" content=\"4 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/datascientest.com\/algorithme-de-kruskal-tout-savoir\",\"url\":\"https:\/\/datascientest.com\/algorithme-de-kruskal-tout-savoir\",\"name\":\"L\u2019algorithme de Kruskal : Qu'est ce que c'est ? Quel est son but ?\",\"isPartOf\":{\"@id\":\"https:\/\/datascientest.com\/#website\"},\"datePublished\":\"2023-12-12T06:30:00+00:00\",\"dateModified\":\"2023-12-08T13:31:32+00:00\",\"author\":{\"@id\":\"https:\/\/datascientest.com\/#\/schema\/person\/6eca16f63daaafcbc96e15549b9d4ee1\"},\"description\":\"En recherchant l\u2019arbre recouvrant de poids minimum, l\u2019algorithme de Kruskal optimise les connexions existantes dans tous types de r\u00e9seaux. D\u00e9couvrez tout ce qu'il faut savoir sur cet algorithme\",\"inLanguage\":\"fr-FR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/datascientest.com\/algorithme-de-kruskal-tout-savoir\"]}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/datascientest.com\/#website\",\"url\":\"https:\/\/datascientest.com\/\",\"name\":\"Formation Data Science | DataScientest.com\",\"description\":\"Leader de la formation en Data Science\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/datascientest.com\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"fr-FR\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/datascientest.com\/#\/schema\/person\/6eca16f63daaafcbc96e15549b9d4ee1\",\"name\":\"Raphael Kassel\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"fr-FR\",\"@id\":\"https:\/\/datascientest.com\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/datascientest.com\/wp-content\/uploads\/2023\/11\/raph.jpeg\",\"contentUrl\":\"https:\/\/datascientest.com\/wp-content\/uploads\/2023\/11\/raph.jpeg\",\"caption\":\"Raphael Kassel\"},\"description\":\"Raphael Kassel est le Head of Data Programs chez DataScientest. Il supervise une \u00e9quipe Data, impl\u00e9mente de nouveaux parcours comme \\\"Chef de projet IA\\\" et \\\"Data Product Manager\\\", et contribue \u00e0 la modernisation des op\u00e9rations du groupe. En collaboration \u00e9troite avec l'\u00e9quipe de d\u00e9veloppement, il adapte l'accompagnement acad\u00e9mique aux \u00e9volutions de l'\u00e9quipe data et \u00e0 l'internationalisation.\",\"sameAs\":[\"https:\/\/www.linkedin.com\/in\/raphaelkassel\/\",\"Data Science\"],\"url\":\"https:\/\/datascientest.com\/author\/raphaelkassel\"}]}<\/script>\n<!-- \/ Yoast SEO Premium plugin. -->","yoast_head_json":{"title":"L\u2019algorithme de Kruskal : Qu'est ce que c'est ? Quel est son but ?","description":"En recherchant l\u2019arbre recouvrant de poids minimum, l\u2019algorithme de Kruskal optimise les connexions existantes dans tous types de r\u00e9seaux. D\u00e9couvrez tout ce qu'il faut savoir sur cet algorithme","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:\/\/datascientest.com\/algorithme-de-kruskal-tout-savoir","og_locale":"fr_FR","og_type":"article","og_title":"L\u2019algorithme de Kruskal : Qu'est ce que c'est ? Quel est son but ?","og_url":"https:\/\/datascientest.com\/algorithme-de-kruskal-tout-savoir","og_site_name":"Formation Data Science | DataScientest.com","article_published_time":"2023-12-12T06:30:00+00:00","article_modified_time":"2023-12-08T13:31:32+00:00","og_image":[{"width":1200,"height":600,"url":"https:\/\/datascientest.com\/wp-content\/uploads\/2023\/10\/algorithme-de-kruskal.png","type":"image\/png"}],"author":"Raphael Kassel","twitter_card":"summary_large_image","twitter_misc":{"\u00c9crit par":"Raphael Kassel","Dur\u00e9e de lecture estim\u00e9e":"4 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/datascientest.com\/algorithme-de-kruskal-tout-savoir","url":"https:\/\/datascientest.com\/algorithme-de-kruskal-tout-savoir","name":"L\u2019algorithme de Kruskal : Qu'est ce que c'est ? Quel est son but ?","isPartOf":{"@id":"https:\/\/datascientest.com\/#website"},"datePublished":"2023-12-12T06:30:00+00:00","dateModified":"2023-12-08T13:31:32+00:00","author":{"@id":"https:\/\/datascientest.com\/#\/schema\/person\/6eca16f63daaafcbc96e15549b9d4ee1"},"description":"En recherchant l\u2019arbre recouvrant de poids minimum, l\u2019algorithme de Kruskal optimise les connexions existantes dans tous types de r\u00e9seaux. D\u00e9couvrez tout ce qu'il faut savoir sur cet algorithme","inLanguage":"fr-FR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/datascientest.com\/algorithme-de-kruskal-tout-savoir"]}]},{"@type":"WebSite","@id":"https:\/\/datascientest.com\/#website","url":"https:\/\/datascientest.com\/","name":"Formation Data Science | DataScientest.com","description":"Leader de la formation en Data Science","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/datascientest.com\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"fr-FR"},{"@type":"Person","@id":"https:\/\/datascientest.com\/#\/schema\/person\/6eca16f63daaafcbc96e15549b9d4ee1","name":"Raphael Kassel","image":{"@type":"ImageObject","inLanguage":"fr-FR","@id":"https:\/\/datascientest.com\/#\/schema\/person\/image\/","url":"https:\/\/datascientest.com\/wp-content\/uploads\/2023\/11\/raph.jpeg","contentUrl":"https:\/\/datascientest.com\/wp-content\/uploads\/2023\/11\/raph.jpeg","caption":"Raphael Kassel"},"description":"Raphael Kassel est le Head of Data Programs chez DataScientest. Il supervise une \u00e9quipe Data, impl\u00e9mente de nouveaux parcours comme \"Chef de projet IA\" et \"Data Product Manager\", et contribue \u00e0 la modernisation des op\u00e9rations du groupe. En collaboration \u00e9troite avec l'\u00e9quipe de d\u00e9veloppement, il adapte l'accompagnement acad\u00e9mique aux \u00e9volutions de l'\u00e9quipe data et \u00e0 l'internationalisation.","sameAs":["https:\/\/www.linkedin.com\/in\/raphaelkassel\/","Data Science"],"url":"https:\/\/datascientest.com\/author\/raphaelkassel"}]}},"_links":{"self":[{"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/posts\/217960"}],"collection":[{"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/users\/77"}],"replies":[{"embeddable":true,"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/comments?post=217960"}],"version-history":[{"count":0,"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/posts\/217960\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/media\/217962"}],"wp:attachment":[{"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/media?parent=217960"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/categories?post=217960"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/tags?post=217960"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}