Minimum Spanning Trees

This example shows how to generate a minimum spanning tree from an input graph using igraph.Graph.spanning_tree(). If you only need a regular spanning tree, check out Spanning Trees.

import random
import igraph as ig
import matplotlib.pyplot as plt

We start by generating a grid graph with random integer weights between 1 and 20:

g = ig.Graph.Lattice([5, 5], circular=False)["weight"] = [random.randint(1, 20) for _ in]

We can then compute a minimum spanning tree using igraph.Graph.spanning_tree(), making sure to pass in the randomly generated weights.

mst_edges = g.spanning_tree(["weight"], return_tree=False)

We can print out the minimum edge weight sum

print("Minimum edge weight sum:", sum([mst_edges]["weight"]))

# Minimum edge weight sum: 136
Minimum edge weight sum: 201

Finally, we can plot the graph, highlighting the edges that are part of the minimum spanning tree.["color"] = "lightgray"[mst_edges]["color"] = "midnightblue"["width"] = 1.0[mst_edges]["width"] = 3.0

fig, ax = plt.subplots()
minimum spanning trees

Total running time of the script: (0 minutes 0.586 seconds)

Gallery generated by Sphinx-Gallery