r语言 - 说明BFS和dfs的意义

Question

我试图理解bfs和dfs的输出。我有很多3d点云，我正在执行注册，从中我想导出沿边缘的成对注册序列。这些成对注册依赖于从种子子样本开始的先前注册。

因此，我试图从种子边(或顶点)获得一个有序的边列表，以便成对比较可以通过树适当地传播。

我一直在尝试使用bfs和dfs，但无法理解输出来构建我的有序边列表。

库(igraph)

edges <- data.frame(
from = c(2,14,8,17,11,16,14,12,14,13,14,16,13,19,15,23,21,21,22,23,20,22),
to   = c(1,1,2,2,3,3,4,5,5,6,7,8,9,10,11,13,16,18,18,18,19,20),
dist  = c(1.7479352,4.1400081,0.9064689,0.5735992,0.7550112,1.3880579,1.6968155,
1.0064647,2.7119138,2.4033570,3.7260517,1.1921137,2.0857017,0.2903520,
1.4191598,0.6111305,1.5752026,1.3102844,0.5070067,0.6522495,0.3172266,
0.6373009
))
g <- graph.data.frame(edges, directed = F)
plot(g)

https://i.stack.imgur.com/I5xd0.png

然后我选择种子作为它们之间距离最大的一对，并运行bfs或dfs

seedPair <- edges[which.max(edges[,3]),1:2]
> seedPair
row col
2  14   1

简单起见，我直接输入顶点14作为根

path <- bfs(g, root = 14, father = T, rank = T)
> path
$root
[1] 14
$mode
[1] "out"
$order
+ 23/23 vertices, named, from 192f5fa:
[1] 20 19 22 10 18 23 21 13 16 6  9  8  3  2  11 17 1  15 14 4  5  7  12
$rank
2 14  8 17 11 16 12 13 19 15 23 21 22 20  1  3  4  5  6  7  9 10 18 
14 19 12 16 15  9 23  8  2 18  6  7  3  1 17 13 20 21 10 22 11  4  5 
$father
+ 23/23 vertices, named, from 192f5fa:
[1] 2  14 8  17 11 16 12 13 19 15 23 21 22 20 1  3  4  5  6  7  9  10 18

path <- dfs(g, root = 14, order = T, order.out = T, father = T)
> path
$root
[1] 13
$mode
[1] "out"
$order
+ 23/23 vertices, named, from 192f5fa:
[1] 20 19 10 22 18 23 13 6  9  21 16 8  2  17 1  14 4  5  12 7  3  11 15
$order.out
+ 23/23 vertices, named, from 192f5fa:
[1] 10 19 6  9  13 23 17 4  12 5  7  14 1  2  8  15 11 3  16 21 18 22 20
$father
+ 23/23 vertices, named, from 192f5fa:
[1] 2  14 8  17 11 16 12 13 19 15 23 21 22 20 1  3  4  5  6  7  9  10 18
$dist
NULL
$neimode
[1] "out"

看看mst，如果我从顶点14开始，这两个输出对我来说都没有意义。dfs对我来说更直观，更容易遵循边缘序列，但我也不明白为什么它将根返回为13，但实际上从节点20开始。

我将非常感谢任何帮助理解这些输出，或从种子位置获得有序边缘序列的替代方法。谢谢!

Answer 1

附录，包括顶点元数据

vertices <- seq(max(edges[1:2]))
g <- graph.data.frame(edges, vertices, directed = F)

或创建一个未命名的图

ug <- graph_from_edgelist(as.matrix(edges[,1:2]), directed = FALSE)
E(g)$dist   <- edges[,3]

当我跑。

edges <- data.frame(
from = c(2,14,8,17,11,16,14,12,14,13,14,16,13,19,15,23,21,21,22,23,20,22),
to   = c(1,1,2,2,3,3,4,5,5,6,7,8,9,10,11,13,16,18,18,18,19,20),
dist  = c(1.7479352,4.1400081,0.9064689,0.5735992,0.7550112,1.3880579,1.6968155,
1.0064647,2.7119138,2.4033570,3.7260517,1.1921137,2.0857017,0.2903520,
1.4191598,0.6111305,1.5752026,1.3102844,0.5070067,0.6522495,0.3172266,
0.6373009
))
g <- graph.data.frame(edges, directed = F)
V(g)$name <- seq(vcount(g))   # ! Reset node n to "n".
>g

结果图为。

IGRAPH 902edcd UN-- 23 22 -- 
+ attr: name (v/c), dist (e/n)
+ edges from 902edcd (vertex names):
[1] 1 --15 2 --15 1 --3  1 --4  5 --16 6 --16 2 --17 7 --18 2 --18 8 --19 2 --20 3 --6  8 --21 9 --22 5 --10 8 --11
[17] 6 --12 12--23 13--23 11--23 9 --14 13--14

运行dfs()。

path <- dfs(g, root = 14, order = TRUE, order.out = TRUE, father = TRUE)
>path

这个给了。

$root
[1] 13
$mode
[1] "out"
$order
+ 23/23 vertices, named, from e6365e8:
[1] 14 9  22 13 23 11 8  19 21 12 6  3  1  4  15 2  17 18 7  20 16 5  10
$order.out
+ 23/23 vertices, named, from e6365e8:
[1] 22 9  19 21 8  11 4  17 7  18 20 2  15 1  3  10 5  16 6  12 23 13 14
$father
+ 23/23 vertices, named, from e6365e8:
[1] 1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23
$dist
NULL
$neimode
[1] "out"

这与问题中的输出不同，原因是语句V(g)$name <- seq(vcount(g))。如果没有这个语句，V(g)[14]是20，因为数据帧逻辑。

下面的代码实现了一个简单的dfs()搜索。

visit <- function(g, v){
if (length(visited)>0L && !visited[v]) {
cat("order: ", v, 'n')
visited[v] <<- 1L
for (w in V(g)[.nei(v)]) visit(g, w)
cat("order.out: ", v, 'n')
}
}

# Call dfs()
visited <- rep(0L, gorder(g))
visit(g, 14)

根据文档，$order。out是一个数字向量，即顶点id，按照它们子树的completion的顺序。$order显示入口处的顶点id。

尝试一个简单的图，如make_ring(10)，来检查逻辑。

希望对你有帮助。