Algoritmo Prim di NetworkX (esempio di spiegazione)

Introduzione

L'algoritmo Prim è simile all'algoritmo di percorso più corto di Dijkstra, utilizza una strategia greedy. All'inizio, aggiunge all'albero T l'arco con il peso più piccolo, quindi aggiunge continuamente l'arco con il peso più piccolo E (uno dei cui estremi è in T, l'altro in G-T). Quando non ci sono più E soddisfacenti, l'algoritmo termina e T diventa un albero minimo generato di G.

NetworkX è un pacchetto Python utilizzato per creare, manipolare reti complesse e studiare la struttura, la dinamica e le funzioni delle reti complesse. Questo documento utilizza la classe networkx.Graph per implementare l'algoritmo Prim.

Testo

Codice dell'algoritmo Prim

Prim

def prim(G, s):
 dist = {} # dist registra la distanza minima dal nodo
 parent = {} # parent registra la tabella dei genitori delbero minimo generato
 Q = list(G.nodes()) # Q contiene tutti i nodi non coperti dalbero generato
 MAXDIST = 9999.99 # MAXDIST rappresenta il numero infinito positivo, ovvero i nodi non sono adiacenti
 # Inizializzazione dei dati
 # Tutti i nodi hanno la distanza minima impostata su MAXDIST, il nodo padre è impostato su None
 for v in G.nodes():
  dist[v] = MAXDIST
  parent[v] = None
 # Imposta la distanza dal nodo iniziale s a 0
 dist[s] = 0
 # Continua a prendere il nodo più 'vicino' da Q e aggiungerlo all'albero di copertura minimo
 # Ferma il ciclo quando Q è vuoto, fine dell'algoritmo
 while Q:
  # Prendi il nodo più 'vicino' u e aggiungi u all'albero di copertura minimo
  u = Q[0]
  for v in Q:
   if (dist[v] < dist[u]):
    u = v
  Q.remove(u)
  # Aggiorna la distanza minima dei vicini di u
  for v in G.adj[u]:
   if (v in Q) and (G[u][v]['weight'] < dist[v]):
    parent[v] = u
    dist[v] = G[u][v]['weight']
 # Fine dell'algoritmo, restituito come tabella dei genitori il minimo albero di copertura
 return parent

dati di test

da ~ a	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

codice di 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)

Risultato di esecuzione

Questo è tutto il contenuto che l'autore ha condiviso con voi su 'NetworkX Prim Algorithm (Example Explanation)', spero possa essere di riferimento per voi, e spero che possiate sostenere fortemente il tutorial di urla.

Dichiarazione: il contenuto di questo articolo è stato raccolto da Internet, il diritto d'autore spetta ai rispettivi proprietari, il contenuto è stato contribuito e caricato dagli utenti di Internet, il sito web non detiene i diritti di proprietà, non è stato editato manualmente e non assume alcuna responsabilità legale correlata. Se trovi contenuti sospetti di copyright, sei invitato a inviare una e-mail a: notice#oldtoolbag.com (al momento dell'invio dell'e-mail, sostituisci # con @) per segnalare, fornendo prove pertinenti. Una volta verificata, il sito eliminerà immediatamente i contenuti sospetti di copyright.