在igraph中使用bfs查找生成树。

Question

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

PS：我尝试使用 $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)

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

我可以使用 $father 如何找到所有的生成树？

Answer 1

父的信息，但结果让人困惑... father 向量以节点为索引，即它与 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.

这个... i第三元素 order 的名称（或索引）。i的第th个节点。

该 i第三元素 father 是节点的父节点的名称（或索引），索引为 i -- 不属于 i第三元素 order. 父体 i第三元素 order 是 parent[order[i]]. 这就是我们需要定义边缘的原因。

因此，树的边缘是。

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

Answer 2

为了避免出现以下错误： 在simple_vs_index(x, ii, na_ok)中出现错误 : 未知顶点被选中 我们需要将其中一条代码语句修改为:

h <- graph( rbind(r$order, r$father[r$order, na_ok = TRUE])[,-1], directed=FALSE )

这样可以让NA出现在索引中

Answer 3

我假设 order 是直接的。对于 father,

> r$order
6/6 vertices, from 29ab0f7:
[1] 1 2 4 5 6 3
> r$father
+ 6/6 vertices, from 29ab0f7:
[1] NA  1  4  1  1  2

• 节点1（标签1的节点）没有父亲-->NA。

• 节点2有节点1为父。

• 节点3有节点4作为父亲。

• 节点4以节点1为父。

• 节点5以节点1为父。

• 节点6的父亲是节点2*。

这里很容易出现星号表示的情况。"为什么节点6是节点2的父亲，而不是节点4？"。答案是，父亲不是定义为节点6所连接的横向序列中最近的元素，而是节点6所连接的横向序列中最早的元素.即节点6与节点2和节点4连接（节点2在横向序列中较早）。这里有一个例子可以让这个概念变得很明显

g <- sample_smallworld(1, 5, 5, 0.05)
plot(g)
r <- graph.bfs(g, root=1, neimode='all', order=TRUE, father=TRUE)

正如你所看到的，节点1是所有节点的父亲，因为它是横向序列中最早的，而且它与所有的节点相连。

$order
+ 5/5 vertices, from 0960d64:
[1] 1 2 3 4 5

$father
+ 5/5 vertices, from 0960d64:
[1] NA  1  1  1  1

Answer 4

我同意上面 "Vincent Zoonekynd "给出的答案。但是，它在我这里并不能原封不动地工作。所以我做了一些修改，以使其工作。以下是我的代码

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

它给出了一个新的矩阵 "h"，这个矩阵是基于原始图的最小生成树的