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.
À 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.
Implémentation python de l’algorithme de Kruskal :
Je me suis basé sur un travail trouvé sur Github : Website github.com
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.
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
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 Website 128mots.com
