Prim-Algorithmus in NetworkX (Beispiel Erklärung)

Introduction

The Prim algorithm is similar to Dijkstra's shortest path algorithm, which uses a greedy strategy. The algorithm starts by adding the edge with the smallest weight in the graph to the tree T, and then continuously adds the edge E (one endpoint of E is in T, the other is in G-When there are no qualified E, the algorithm ends, and T is a minimum spanning tree of G.

NetworkX is a Python software package for creating, operating complex networks, and learning the structure, dynamics, and functions of complex networks. This article implements the Prim algorithm using the networkx.Graph class.

Text

Code for the Prim algorithm

Prim

def prim(G, s):
 dist = {} # dist records the minimum distance to the node
 parent = {} # parent records the parent table of the minimum spanning tree
 Q = list(G.nodes()) # Q contains all nodes not covered by the generated tree
 MAXDIST = 9999.99 # MAXDIST represents positive infinity, that is, two nodes are not adjacent
 # Initialize data
 # Set the minimum distance of all nodes to MAXDIST, and set the parent to None
 for v in G.nodes():
  dist[v] = MAXDIST
  parent[v] = None
 # Set the distance to the starting node s to 0
 dist[s] = 0
 # Continuously extract the 'nearest' node from Q and add it to the minimum spanning tree
 # Stop the loop when Q is empty, the algorithm ends
 while Q:
  # Extract the 'nearest' node u and add u to the minimum spanning tree
  u = Q[0]
  for v in Q:
   if (dist[v] < dist[u]):
    u = v
  Q.remove(u)
  # Update the minimum distance of u's adjacent nodes
  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']
 # Algorithm ends, returns the minimum spanning tree in the form of a parent table
 return parent

Testdaten

von ~ bis	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

Testcode

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)

Laufende Ergebnisse

Diese Anleitung zu Prim-Algorithmus von NetworkX (Beispiel) ist alles, was der Redakteur Ihnen mitteilen kann. Ich hoffe, es kann Ihnen als Referenz dienen und ich hoffe, dass Sie die Anleitung weiterempfehlen.

Erklärung: Der Inhalt dieses Artikels wurde aus dem Internet übernommen und gehört dem Urheberrechtsinhaber. Der Inhalt wurde von Internetnutzern freiwillig beigesteuert und hochgeladen. Diese Website besitzt keine Eigentumsrechte und hat den Inhalt nicht manuell bearbeitet. Sie übernimmt auch keine rechtlichen Verantwortlichkeiten. Wenn Sie verdächtige urheberrechtliche Inhalte finden, senden Sie bitte eine E-Mail an: notice#w3Erklärung: Der Inhalt dieses Artikels wurde aus dem Internet übernommen und gehört dem Urheberrechtsinhaber. Der Inhalt wurde von Internetnutzern freiwillig beigesteuert und hochgeladen. Diese Website besitzt keine Eigentumsrechte und hat den Inhalt nicht manuell bearbeitet. Sie übernimmt auch keine rechtlichen Verantwortlichkeiten. Wenn Sie verdächtige urheberrechtliche Inhalte finden, senden Sie bitte eine E-Mail an: notice#w