生成树

此示例展示了如何使用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()。