在igraph中使用bfs查找生成树 [英] Find spanning tree using bfs in igraph

问题描述

我想使用igraph函数graph.bfs在图中找到生成树. 你能告诉我怎么做吗?

I would like to find a spanning tree in a graph using igraph function graph.bfs. Could you show me how?

PS:我尝试使用从graph.bfs返回的值的$father信息，但结果使我感到困惑.这是一个示例:

PS: I try to use the $father info of the returned value from graph.bfs, but the result confuses me. Here is an example:

g <- graph(c(1,2,2,6,1,4,4,6,5,6,1,5,5,3,3,4), directed=FALSE)
plot(g)

tmp <- graph.bfs(g, root=1, neimode='all', order=TRUE, father=TRUE,callback=f)

结果是: tmp$order = 1 2 4 5 6 3和tmp$father=0 1 4 1 1 2

我可以使用$father信息来查找所有生成树吗?

Can I use the $father info to find all the spanning tree?

推荐答案

father向量由节点索引，即，它与order的顺序不同.

The father vector is indexed by the nodes, i.e., it is not in the same order as order.

library(igraph)
g <- graph(c(1,2,2,6,1,4,4,6,5,6,1,5,5,3,3,4), directed=FALSE)
r <- graph.bfs(g, root=1, neimode='all', order=TRUE, father=TRUE)
h <- graph( rbind(r$order, r$father[r$order])[,-1], directed=FALSE )
plot(h)

在此示例中，我们有:

order:  1 2 4 5 6 3
father: 0 1 4 1 1 2.

order的第i个元素是遍历前顺序的第i个节点的名称(或索引).

The ith element of order is the name (or index) of ith node in the pre-traversal order.

father的i元素是具有索引i的节点的父级的名称(或索引)，而不是order的i元素的父级. order的第i个元素的父元素是parent[order[i]].这就是我们需要定义的边缘.

The ith element of father is the name (or index) of the parent of the node with index i -- not of the ith element of order. The parent of the ith element of order is parent[order[i]]. This is what we need to define the edges.

树的边缘因此是:

order:  1 2 4 5 6 3
        | | | | | |
father: 0 1 1 1 2 4.

这篇关于在igraph中使用bfs查找生成树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！