生成树

本示例展示了如何使用igraph.Graph.spanning_tree()从输入图生成生成树。有关寻找最小生成树的相关思想，请参见最小生成树。

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

首先，我们创建一个二维的 6x6 格子图。

g = ig.Graph.Lattice([6, 6], circular=False)

我们可以计算图的二维布局。

layout = g.layout("grid")

为了增加一点趣味性，我们重新排列顶点 ID 并计算新的布局。虽然这在这种情况下并不是非常有用，但它确实能使生成的生成树看起来更有趣 ;-)

random.seed(0)
permutation = list(range(g.vcount()))
random.shuffle(permutation)
g = g.permute_vertices(permutation)
new_layout = g.layout("grid")
for i in range(36):
    new_layout[permutation[i]] = layout[i]
layout = new_layout

我们现在可以生成一个生成树。

spanning_tree = g.spanning_tree(weights=None, return_tree=False)

最后，我们可以绘制图，并用高亮颜色显示生成树。我们遵循常规方法：首先设置一些美学选项，然后利用igraph.plot()和 matplotlib 来完成繁重的工作。

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

注意

要反转 y 轴，使树的根位于图的顶部，可以在调用plt.show()之前调用ax.invert_yaxis()。