Shuai Zhang Shuai Zhang - 2 months ago 25
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)


find spanning tree

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?

Answer

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 ith element of order is the name (or index) of ith node in the pre-traversal order.

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.

The edges of the tree are therefore:

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