Shuai Zhang - 9 months ago 83

R Question

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`

`graph.bfs`

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

`tmp$father=0 1 4 1 1 2`

Can I use the

`$father`

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

Source (Stackoverflow)