Algorithme de Prim et implémentation en Python

Voici un article sur l’algorithme de Prim et son implémentation en Python.

Comme l’algorithme de Kruskal,

l’algorithme de Prim est également un algorithme glouton. Cela commence par un arbre couvrant vide. L’idée est de conserver deux ensembles de sommets. Le premier groupe contient des sommets qui ont été inclus dans Minimum spaning tree (l’arbre mininmal couvrant) et l’autre groupe contient des sommets qui ne sont pas encore inclus.

Algorithme de Prim et implémentation en Python

À chaque étape, il considérera toutes les arêtes reliant les deux groupes et sélectionnera l’arête avec le poids le plus faible parmi ces arêtes. Après avoir sélectionné l’arête, il déplace l’autre extrémité de l’arête vers l’ensemble contenant l’arête.
L’idée de l’algorithme de Prim est très simple. Un arbre couvrant signifie que tous les sommets doivent être connectés.

Qu’est qu’un arbre couvrant pondéré, connecté et minimal (MST)?

L’arbre couvrant pondéré, connecté et minimal (MST) ou l’arbre couvrant le poids minimum pour les graphiques non orientés sont des arbres couvrant dont les poids sont inférieurs ou égaux aux poids des arbres couvrant les uns des autres. Le poids de l’arbre couvrant est la somme des poids attribués à chaque arête de l’arbre couvrant.

Algorithme de Prim et implémentation en Python
Programme technologie 6ème

Implémentation python de l’algorithme de Kruskal :

Je me suis basé sur un travail trouvé sur Github : https://github.com/this-is-shreya/networkx-graph-theory/blob/main/Minimum%20spanning%20tree%20using%20Kruskal%20algorithm.py

Le point intéressant et qu’il utilise la bibliothèque networkx : NetworkX est un progiciel Python utilisé pour créer, manipuler et étudier la structure, la dynamique et les fonctions de réseaux complexes.

https://networkx.org/

import networkx as nx
 
H= nx.Graph() 
H.add_edges_from([
                        (1,2), 
                        (1,3), 
                        (3,2), 
                        (1,6), 
                        (3,5),
                        (4,2),
                        (2,3),
                        (3,1),
                        (4,0)])
 
nx.draw(H, with_labels=True, font_weight='bold')

for i in range(4):
    (node1, node2)=list(H.edges)[i]
    H.add_edge(node1, node2)

    if nx.cycle_basis(H)!=[]:
        H.remove_edge(node1,node2)

b=list(H.edges(data='weight'))
min_weight=0
for i in range(len(b)):
    (src,dest,w)=b[i]
    min_weight=min_weight+int(1)
print("L'arbre couvrant minimal est ",min_weight)

Liens externes

https://fr.wikipedia.org/wiki/Python_(langage)

https://www.python.org/

Liens internes – Algorithme de Prim et implémentation en Python

https://128mots.com/index.php/en/2021/03/16/blocking-request-from-unknown-origin-jupyter/embed/#?secret=tfjqWZGh7C https://128mots.com/index.php/2021/05/03/comment-se-branche-un-voltmetre/embed/#?secret=2Y7GouAPDH https://128mots.com/index.php/2021/05/03/comment-se-branche-un-voltmetre/

https://128mots.com/index.php/category/internet/

https://128mots.com/index.php/2021/05/14/comment-peut-on-se-connecter-au-reseau-internet/

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *