我想用igraph函數graph.bfs在圖中找到生成樹。 你能告訴我如何？在igraph中使用bfs查找生成樹
PS：我嘗試使用從graph.bfs返回的值的$father信息，但結果令我困惑。這裏有一個例子：
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信息，以找到所有的生成樹？
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.
的order的i th元素是在遍歷預購i個節點的名稱（或索引）。
的father的i th元素是與索引i的節點的父節點的名稱（或索引） - 不是order的i個元素的。 order的i th元素的父級爲parent[order[i]]。這是我們需要定義邊緣的。因此
樹的邊緣：
order: 1 2 4 5 6 3
| | | | | |
father: 0 1 1 1 2 4.
看起來正確。但是，請你解釋一下「父向量是由節點索引的」嗎？我不明白。謝謝！ –
我試圖添加一些解釋。 –
我想我明白了。但這是一個糟糕的設計嗎？如果你沒有'$ order'，那麼'$ father'就沒用了。 –
爲了避免這樣的錯誤：在simple_vs_index 誤差（X，II，na_ok）：未知頂點選擇 我們需要改變爲代碼語句之一：
h <- graph(rbind(r$order, r$father[r$order, na_ok = TRUE])[,-1], directed=FALSE)
這允許NA存在於索引中。
我認爲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
爲什麼不使用'minimum.spanning.tree（）'？ –
我只想嘗試不同的方法來查找生成樹，而不僅僅是最小生成樹。 –