NetworkX之Prim算法(实例讲解)

Introduction

L'algorithme Prim est similaire à l'algorithme de plus court chemin de Dijkstra, il utilise une stratégie greedy. L'algorithme commence par ajouter l'arc de poids minimal au arbre T, puis continue à ajouter l'arc E (E a un extrémité dans T, et l'autre dans G-Lorsque les E valides ne sont plus disponibles, l'algorithme se termine et T est alors un arbre couvrant minimal de G.

NetworkX est un paquet Python utilisé pour créer, manipuler des réseaux complexes et étudier la structure, la dynamique et les fonctions des réseaux complexes. Dans cet article, l'algorithme Prim est mis en œuvre à l'aide de la classe networkx.Graph.

Texte principal

Code de l'algorithme Prim

Prim

def prim(G, s):
 dist = {} # dist enregistre la distance minimale jusqu'aux nœuds
 parent = {} # parent enregistre le tableau des parents de l'arbre couvrant minimal
 Q = list(G.nodes()) # Q contient tous les nœuds non couverts par l'arbre couvrant
 MAXDIST = 9999.99 # MAXDIST représente le plus grand nombre, c'est-à-dire que les deux nœuds ne sont pas adjacents
 # Initialiser les données
 # Définir la distance minimale de tous les nœuds comme MAXDIST, et les parents comme None
 pour v dans G.nodes():
  dist[v] = MAXDIST
  parent[v] = None
 # Définir la distance à partir du point de départ s comme 0
 dist[s] = 0
 # Continuer à ajouter les nœuds 'le plus proche' de Q à l'arbre couvrant minimal
 # Arrêter la boucle lorsque Q est vide, l'algorithme est terminé
 while Q:
  # Retirer le nœud 'le plus proche' u et l'ajouter à l'arbre couvrant minimal
  u = Q[0]
  pour v dans Q:
   si (dist[v] < dist[u]):
    u = v
  Q.remove(u)
  # Mettre à jour la distance minimale des voisins adjacents de u
  pour v dans G.adj[u]:
   si (v dans Q) et (G[u][v]['weight'] < dist[v]):
    parent[v] = u
    dist[v] = G[u][v]['weight']
 # L'algorithme est terminé, renvoyant le plus petit arbre couvrant sous forme de tableau des parents
 return parent

Données de test

de ~ à	2	3	4	5	6	7	8
1	1.3	2.1	0.9	0.7	1.8	2.0	1.8
2		0.9	1.8	1.2	2.8	2.3	1.1
3			2.6	1.7	2.5	1.9	1.0
4				0.7	1.6	1.5	0.9
5					0.9	1.1	0.8
6						0.6	1.0
7							0.5

Code de test

import matplotlib.pyplot as plt
import networkx as nx
g_data = [(1, 2, 1.3), (1, 3, 2.1), (1, 4, 0.9), (1, 5, 0.7), (1, 6, 1.8), (1, 7, 2.0), (1, 8, 1.8), (2, 3, 0.9), (2, 4, 1.8), (2, 5, 1.2), (2, 6, 2.8), (2, 7, 2.3), (2, 8, 1.1), (3, 4, 2.6), (3, 5, 1.7), (3, 6, 2.5), (3, 7, 1.9), (3, 8, 1.0), (4, 5, 0.7), (4, 6, 1.6), (4, 7, 1.5), (4, 8, 0.9), (5, 6, 0.9), (5, 7, 1.1), (5, 8, 0.8), (6, 7, 0.6), (6, 8, 1.0), (7, 8, 0.5)
def draw(g):
 pos = nx.spring_layout(g)
 nx.draw(g, pos, \

   arrows=True, \

   with_labels=True, \

   nodelist=g.nodes(), \

   style='dashed', \

   edge_color='b', \

   width=, \
2, \

   node_color='y', \

   alpha=0.5)
 plt.show()
g = nx.Graph()
g.add_weighted_edges_from(g_data)
tree = prim(g, 1)
mtg = nx.Graph()
mtg.add_edges_from(tree.items())
mtg.remove_node(None)
draw(mtg)

Résultat de l'exécution

Cet article sur l'algorithme Prim de NetworkX (explication pratique) est tout ce que l'éditeur partage avec vous. J'espère que cela vous servira de référence et que vous continuerez à soutenir le tutoriel d'alarme.

Déclaration : Le contenu de cet article est issu du réseau, la propriété intellectuelle appartient aux auteurs respectifs, le contenu est apporté par les utilisateurs d'Internet de manière spontanée et est téléchargé, ce site ne détient pas de droits de propriété, n'a pas été traité par l'éditeur humain et n'assume aucune responsabilité juridique. Si vous trouvez du contenu suspect de violation de droits d'auteur, vous êtes invité à envoyer un e-mail à : notice#oldtoolbag.com (au moment de l'envoi d'un e-mail, veuillez remplacer # par @ pour signaler une plainte, et fournir des preuves pertinentes. Une fois vérifié, ce site supprimera immédiatement le contenu suspect de violation de droits d'auteur.