L’utilisation de l’algorithme de Kruskal python correspond au poids minimum de l’algorithme de recherche de graphe connecté non orienté pondéré dans le spanning tree ou le minimum spanning tree.
Lien Wikipedia : Website fr.wikipedia.org
Qu’est-ce qu’un Spanning Tree?
L’arbre couvrant est un sous-ensemble du graphe G, tous les sommets du graphe G sont couverts avec le moins d’arêtes possible. Par conséquent, l’arbre couvrant n’a pas de cycles et ne peut donc pas être déconnecté.
Grâce à cette définition, nous pouvons conclure que chaque graphe G connecté et non orienté a au moins un arbre couvrant. Le graphe déconnecté n’a pas d’arbre couvrant car il ne peut pas s’étendre à tous ses sommets.
Un Spanning Tree est un arbre dans lequel certains éléments d’un arbre sont de type SpanningTree. Cela signifie que cet arbre est un arbre représentant tous les éléments contenus dans les arbres suivants:
Cet arbre s’appelle un nœud et représente les nœuds de la famille de nœuds. Le Spanning Tree est le nœud de l’arborescence qui représente la famille de nœuds. La famille de nœuds est définie par une série d’arbres, chacun constitué d’un ensemble de quatre nœuds différents. Les éléments (y compris les espaces) du nouvel élément n’ont aucune signification en tant que SpanningTree. Pour plus d’informations, consultez la section sur les arbres couvrant.
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 Kruskal
L’algorithme de Kruskal utilise la méthode gourmande pour trouver l’arbre qui couvre le plus petit coût. L’algorithme traite le graphique comme une forêt et traite chaque nœud qu’il possède comme une arborescence distincte. Un arbre n’est connecté à un autre arbre que si le coût est le plus bas parmi toutes les options disponibles et ne viole pas les attributs MST.
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 externes – Algorithme de Kruskal
Liens internes – Algorithme de Kruskal python
https://128mots.com/index.php/2021/03/16/tri-fusion-python/embed/#?secret=3jjT6bPEJ4 Website 128mots.com
