Algorithme de Prim

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Prim.
Arbre couvrant de poids minimum

L'algorithme de Prim est un algorithme glouton qui calcule un arbre couvrant minimal dans un graphe connexe valué et non orienté. En d'autres termes, cet algorithme trouve un sous-ensemble d'arêtes formant un arbre sur l'ensemble des sommets du graphe initial, et tel que la somme des poids de ces arêtes soit minimale. Si le graphe n'est pas connexe, alors l'algorithme détermine un arbre couvrant minimal d'une composante connexe du graphe.

Historique[modifier | modifier le code]

L'algorithme a été développé en 1930 par un mathématicien tchèque Vojtěch Jarník [1]puis a été redécouvert et republié par Robert C. Prim[2] et Edsger W. Dijkstra in 1959. Ainsi, il est aussi parfois appelé DJP algorithm[3], Jarník's algorithm[4], the Prim–Jarník algorithm[5], or the Prim–Dijkstra algorithm[6].

Principe[modifier | modifier le code]

L'algorithme[7] consiste à faire croître un arbre depuis un sommet. On commence avec un seul sommet puis à chaque étape, on ajoute une arête de poids minimum adjacente à l'arbre en construction.

Exemple[modifier | modifier le code]

Exécution de l'algorithme de Prim depuis le sommet A.

À droite, on donne un exemple d'exécution de l'algorithme de Prim.

Algorithme[modifier | modifier le code]

Pseudo-code[modifier | modifier le code]

Le pseudo-code[7] de l'algorithme de Prim est similaire à celui de l'algorithme de Dijkstra et utilise le type abstrait file de priorité.

 fonction prim(G, s)
       pour tout sommet t
              cout[t] := +∞
              pred[t] := nil
       cout[s] := 0
       F := file de priorité contenant les sommets de G avec cout[.] comme priorité
       tant que F ≠ vide
            t := F.defiler
            pour toute arête t--u
                si cout[u] > poids(t--u)
                       cout[u] := poids(t--u)
                       pred[u] := t
                       F.notifierDiminution(u)
                        
       retourner pred

Au début tous les sommets sont dans la file de priorité. La priorité est donnée par cout[.]. On retire un à un les sommets de la file de priorité. Le tableau pred[.] contient le prédécesseur d'un sommet dans l'arbre en construction. L'algorithme retourne le tableau pred qui représente l'arbre couvrant minimum.

Complexité[modifier | modifier le code]

Si on représente le graphe par une matrice d'adjacence alors la complexité est en  O(|S|^2)|S| est le nombre de sommets dans le graphe. Sinon, si on représente le graphe par une liste d'adjacence, nous donnons ici les complexités en fonction de l'implémentation de la file de priorité.

Implémentation de la file de priorité Complexité temporelle
Liste ou tableau  O(|A| \times |S|)
tas min binaire  O(|A| \times log|S|)
tas de Fibonacci  O(|A| + |S| \times log|S|)

|S| est le nombre de sommets dans le graphe et |A| est le nombre d'arcs dans le graphe.

Notes et références[modifier | modifier le code]

  1. « O jistém problému minimálním. (Z dopisu panu O. Borůvkovi) », sur dml.cz (consulté le 26 décembre 2015)
  2. R.C. Prim, « Shortest connection networks and some generalizations », Bell System Technical Journal, The, vol. 36,‎ , p. 1389-1401 (ISSN 0005-8580, DOI 10.1002/j.1538-7305.1957.tb01515.x, lire en ligne)
  3. Seth Pettie et Vijaya Ramachandran, « An Optimal Minimum Spanning Tree Algorithm », J. ACM, vol. 49,‎ , p. 16–34 (ISSN 0004-5411, DOI 10.1145/505241.505243, lire en ligne)
  4. (en) Robert Sedgewick et Kevin Daniel Wayne, Algorithms, Addison-Wesley Professional,‎ (ISBN 9780321573513, lire en ligne)
  5. (en) Kenneth Rosen, Discrete Mathematics and Its Applications 7th edition, McGraw-Hill Science,‎ (lire en ligne)
  6. D. Cheriton et R. Tarjan, « Finding Minimum Spanning Trees », SIAM Journal on Computing, vol. 5,‎ , p. 724-742 (ISSN 0097-5397, DOI 10.1137/0205051, lire en ligne)
  7. a et b (en) S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, Algorithms

Bibliographie[modifier | modifier le code]

Liens internes[modifier | modifier le code]