Prim Algorithm in NetworkX (Example Explanation)

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 (E has one endpoint in T, and the other in G-When there is no E that meets the conditions, 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 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, i.e., 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, returning the minimum spanning tree in the form of a parent table
 return parent

Test Data

From ~ to	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

Test Code

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)

Running Result

This article on NetworkX Prim algorithm (instance explanation) is all the content that the editor shares with everyone. I hope it can be a reference for everyone, and I also hope everyone will support and cheer for the tutorial.

Declaration: The content of this article is from the network, the copyright belongs to the original author. The content is contributed and uploaded by Internet users spontaneously, this website does not own the copyright, does not edit the content manually, and does not assume relevant legal liability. If you find any content suspected of copyright infringement, please send an email to: notice#w3Please send an email to codebox.com (replace # with @ when sending email) to report violations, and provide relevant evidence. Once verified, this site will immediately delete the content suspected of infringement.