Shuai Zhang - 1 year ago 177
R Question

Find spanning tree using bfs in igraph

I would like to find a spanning tree in a graph using igraph function

`graph.bfs`
.
Could you show me how?

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

The result is :
`tmp\$order = 1 2 4 5 6 3`
and
`tmp\$father=0 1 4 1 1 2`

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

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

In this example, we have:

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

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

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

The edges of the tree are therefore:

``````order:  1 2 4 5 6 3
| | | | | |
father: 0 1 1 1 2 4.
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download