Algoritmo Prim en NetworkX (explicación de ejemplo)

Introducción

El algoritmo Prim es similar al algoritmo de camino más corto de Dijkstra, utiliza una estrategia greedy. El algoritmo comienza agregando al árbol T la arista de peso más pequeño, luego continuamente agregando la arista E (E tiene un extremo en T, el otro en G-T (T no contiene aristas E que cumplan con las condiciones, el algoritmo termina y en ese momento T es un árbol generador mínimo de G.

NetworkX es un paquete de Python utilizado para crear, operar redes complejas y aprender la estructura, dinámica y función de las redes complejas. Este artículo utiliza la clase networkx.Graph para implementar el algoritmo Prim.

Texto

Código del algoritmo Prim

Prim

def prim(G, s):
 dist = {} # dist registra la distancia mínima a los nodos
 parent = {} # parent registra la tabla de padres del árbol generador mínimo
 Q = list(G.nodes()) # Q contiene todos los nodos no cubiertos por el árbol generador
 MAXDIST = 9999.99 # MAXDIST representa el infinito positivo, es decir, los nodos no están adyacentes
 # Inicializar datos
 # Establecer la distancia mínima de todos los nodos en MAXDIST y establecer el padre en None
 for v in G.nodes():
  dist[v] = MAXDIST
  parent[v] = None
 # Establecer la distancia a la nodo de inicio s en 0
 dist[s] = 0
 # Continuar sacando el nodo 'más cercano' de Q y agregarlo al árbol generador mínimo
 # Detener el ciclo cuando Q esté vacío, finalizando el algoritmo
 while Q:
  # Sacar el nodo 'más cercano' u y agregarlo al árbol generador mínimo
  u = Q[0]
  for v in Q:
   if (dist[v] < dist[u]):
    u = v
  Q.remove(u)
  # Actualizar la distancia mínima de los vecinos adyacentes de 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']
 # Algoritmo finalizado, regresando el árbol generador mínimo en forma de tabla de padres
 devolver padre

Datos de prueba

Código de prueba

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)
dibujar(mtg)

Resultado de la ejecución

Este artículo sobre el algoritmo Prim de NetworkX (explicación con ejemplo) es todo lo que el editor comparte con ustedes, espero que les sea útil y esperamos que todos nos apoyen y alentemos el tutorial.

Declaración: El contenido de este artículo se ha obtenido de la red, es propiedad del autor original, el contenido se ha contribuido y subido por los usuarios de Internet, este sitio no posee los derechos de propiedad, no ha sido editado por humanos y no asume responsabilidad alguna por ellos. Si encuentra contenido sospechoso de infracción de derechos de autor, por favor envíe un correo electrónico a: notice#oldtoolbag.com (al enviar un correo electrónico, por favor reemplace # con @ para denunciar y proporcionar evidencia. Una vez confirmado, este sitio eliminará inmediatamente el contenido sospechoso de infracción de derechos de autor.)