理解BFS/DFS输出：3D点云MST配准的有序边序列构建

问题背景 #

在3D点云最小生成树（MST）配准任务中，需要基于种子顶点生成可传递的成对配准有序边列表。使用igraph库的BFS/DFS方法时遇到以下问题：

• 以距离最大的边对应的顶点14为根节点运行BFS，遍历顺序不符合预期
• 运行DFS时，返回结果显示root为13，但实际起始节点看似是20，无法理解输出结构

核心原因分析 #

igraph中通过graph.data.frame创建图时，顶点的内部ID是按数据中出现的顺序分配的，而非用户自定义的顶点编号（如14、20等）。直接使用顶点编号作为root参数时，igraph会将其视为内部ID而非顶点名字，导致遍历逻辑混乱。同时，BFS/DFS的输出结果（如order、father）默认返回内部ID，而非自定义顶点编号，这是造成误解的关键。

解决方案 #

1. 解析igraph的BFS/DFS输出 #

先建立内部ID与自定义顶点名字的映射，再将输出结果转换为实际的顶点编号：

步骤1：查看顶点映射关系

library(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)

# 查看内部ID与自定义顶点名字的对应关系
vertex_map <- data.frame(
  internal_id = 1:vcount(g),
  vertex_name = V(g)$name
)
print(vertex_map)

步骤2：正确执行BFS并解析结果

# 找到顶点14对应的内部ID
root_internal <- which(V(g)$name == "14")

# 执行BFS
bfs_result <- bfs(g, root = root_internal, father = TRUE, rank = TRUE)

# 将内部ID转换为自定义顶点编号
bfs_order <- V(g)$name[bfs_result$order]
bfs_father <- ifelse(bfs_result$father == 0, NA, V(g)$name[bfs_result$father])

# 构建有序边列表（父节点->子节点）
bfs_edges <- data.frame(
  from = bfs_father[!is.na(bfs_father)],
  to = bfs_order[bfs_order != V(g)$name[root_internal]],
  stringsAsFactors = FALSE
)

cat("BFS遍历顺序：\n")
print(bfs_order)
cat("\nBFS生成的有序边列表：\n")
print(bfs_edges)

步骤3：正确执行DFS并解析结果

# 执行DFS
dfs_result <- dfs(g, root = root_internal, order = TRUE, order.out = TRUE, father = TRUE)

# 转换为自定义顶点编号
dfs_order <- V(g)$name[dfs_result$order]
dfs_father <- ifelse(dfs_result$father == 0, NA, V(g)$name[dfs_result$father])

# 构建有序边列表
dfs_edges <- data.frame(
  from = dfs_father[!is.na(dfs_father)],
  to = dfs_order[dfs_order != V(g)$name[root_internal]],
  stringsAsFactors = FALSE
)

cat("\nDFS遍历顺序：\n")
print(dfs_order)
cat("\nDFS生成的有序边列表：\n")
print(dfs_edges)

2. 替代方案：直接提取MST的层级边列表 #

如果只需要基于MST生成可传递的有序边，也可以直接从MST的父子关系中构建：

# 生成MST（你的edges已经是MST，这里仅演示通用方法）
mst_g <- minimum.spanning.tree(g, weights = E(g)$dist)

# 以顶点14为根，生成树的边列表
mst_edges <- as_edgelist(mst_g, names = TRUE)
# 可结合BFS/DFS顺序排序，确保可传递性

关键说明 #

• 始终明确igraph的内部ID与自定义顶点名字的区别，使用V(g)$name获取实际顶点编号
• BFS/DFS的father属性中，0表示根节点的父节点不存在，需转换为NA或忽略
• 生成的有序边列表遵循遍历顺序，可直接用于成对配准的传递计算

内容的提问来源于stack exchange，提问作者Blake