python-igraph 手册

用于从 Python 使用 igraph

最小生成树 ¶

最小生成树¶

本例展示了如何使用 spanning_tree() 从输入图生成最小生成树。如果您只需要一个常规生成树，请查看生成树。

我们首先生成一个具有 1 到 20 之间随机整数权重的网格图

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

# Generate grid graph with random weights
random.seed(0)

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

然后我们调用 spanning_tree()，确保传入随机生成的权重。

# Generate spanning tree
spanning_tree = g.spanning_tree(weights=None, return_tree=False)

最后，我们生成绘图并可视化生成树。我们还打印出 MST 中边的总和。

# Plot graph
g.es["color"] = "lightgray"
g.es[spanning_tree]["color"] = "midnightblue"
g.es["width"] = 0.5
g.es[spanning_tree]["width"] = 3.0

fig, ax = plt.subplots()
ig.plot(
    g,
    target=ax,
    layout=layout,
    vertex_color="lightblue",
    edge_width=g.es["width"]
)
plt.show()

# Print out minimum edge weight sum
print("Minimum edge weight sum:", sum(g.es[mst_edges]["weight"]))

最终的图看起来像这样

A visual representation of the spanning tree generated from a grid graph — 最小生成树边加粗显示。¶

…输出看起来像这样

Minimum edge weight sum: 136

注意

随机权重可能会因运行此代码的机器而异。