如何使用python igraph获取树的子树？

Question

我希望有一个用于此目的的简单函数（例如tree.subtree(vertex)），但即使在浏览文档很长时间后，我也找不到

在任何情况下，我都发现了以下解决方法：

subtree = tree.induced_subgraph(tree.subcomponent(vertex, mode='out'))

但这对我来说似乎效率低下，因为subcomponent()返回一个可从vertex访问的顶点列表，然后induced_subgraph()（re）从该顶点列表创建子树

还有其他想法吗？：）

Answer 1

我认为您正在寻找广度优先搜索，从您的根开始：

[vertices, layers, parents] = g.bfs(root)

可以组合顶点和父对象以获得新图形的边

但是，我认为这样做实际上不会更有效率： subcomponent将基于BFS，因此运行时间没有差异（O（| V |+| E |））。induced_subgraph将有一个运行时间O（| E |），因此这也与组合顶点和父对象的运行时间相同。大O表示法忽略的常量因子当然会有所不同，但您认为这些差异有多大