如何使用igraph生成并绘制小规模随机图的全部生成树？

你可以直接使用igraph内置的枚举生成树函数实现需求，5节点的小规模图完全没有性能压力，操作步骤如下：

• 第一步：调用all_spanning_trees()函数直接枚举全量生成树，返回结果是包含所有生成树igraph对象的列表，数量和你通过拉普拉斯余子式计算的11个完全匹配
• 第二步：复用原图的节点布局批量绘制所有生成树，保证节点位置和原图一致，方便对比结构

完整可运行代码如下：

library(igraph)
set.seed(2)
n <- 5   #  n=5
m <- 6   #  m=6
g <- erdos.renyi.game(n, p.or.m=m, type="gnm" , directed=FALSE, loops=FALSE)

# 验证生成树总数
lap_mat <- laplacian_matrix(g)   
print(paste("number of spanning trees by cofactor = ", det(lap_mat[-1,-1])))
# 输出11

# 枚举所有生成树
all_st <- all_spanning_trees(g)
print(length(all_st)) # 输出11，和计算结果一致

# 批量绘制原图+所有生成树
par(mfrow = c(3,4), mar = c(1,1,2,1))
fixed_layout <- layout.fruchterman.reingold(g)
# 绘制原图
plot(g, main = "Original graph", vertex.size = 40, layout = fixed_layout)
# 循环绘制11个生成树
for (i in seq_along(all_st)) {
  plot(all_st[[i]], main = paste("Spanning tree", i), vertex.size = 40, layout = fixed_layout)
}

注意：如果使用的是较低版本的igraph包，调用all_spanning_trees报错时，可以替换为旧版函数名spanning.trees运行。

内容的提问来源于stack exchange，提问作者Nick