基于data.table的最小关联值路径高效查找方案问询

需求说明 #

给定按From和To升序排序的data.table，从初始节点1出发，每次选择当前节点对应的最小To值作为下一个节点，直到该节点不在From列中为止，返回完整路径向量。

示例与预期输出 #

• 示例1：

  dt1 <- data.table(From = c(1,1,1,1,2,2,2,2,3,3,3,4,4,5),
                    To = c(3,4,5,6,3,4,5,6,4,5,6,5,6,6))
  

  预期路径：c(1,3,4,5,6)

• 示例2：

  dt2 <- data.table(From = c(1, 1, 1, 1, 2, 2, 2, 2, 4, 4, 5), 
                    To = c(3, 4, 5, 6, 3, 4, 5, 6, 5, 6, 6))
  

  预期路径：c(1,3)

• 示例3：

  dt3 <- data.table(From = c(1,1,1,2,2,3,3,4,4),
                    To = c(2,3,4,5,6,4,7,8,9))
  

  预期路径：c(1,2,5)

方案一：data.table原生高效实现 #

利用data.table的键索引和去重特性，先构建每个From到最小To的映射表，再通过快速查找遍历路径，时间复杂度为O(k log n)（k为路径长度，n为节点数），适合十万级数据集。

library(data.table)

# 通用函数：从data.table生成最小To路径
get_min_path_dt <- function(dt, start = 1) {
  # 预处理：每个From保留最小To（原数据已排序，unique直接取第一个匹配项）
  min_map <- unique(dt, by = "From")
  setkey(min_map, From)  # 设置键，加速查找
  
  path <- c(start)
  current <- start
  
  while (current %in% min_map$From) {
    next_node <- min_map[.(current), To]
    if (is.na(next_node)) break
    path <- c(path, next_node)
    current <- next_node
  }
  
  return(path)
}

# 测试示例1
get_min_path_dt(dt1)  # [1] 1 3 4 5 6
# 测试示例2
get_min_path_dt(dt2)  # [1] 1 3
# 测试示例3
get_min_path_dt(dt3)  # [1] 1 2 5

方案二：igraph图遍历实现 #

将数据转换为有向图，利用图结构的邻居查找特性遍历最小路径，逻辑直观，适合后续扩展复杂图操作。

library(igraph)
library(data.table)

# 通用函数：用igraph生成最小To路径
get_min_path_igraph <- function(dt, start = 1) {
  # 预处理：每个From保留最小To
  min_edges <- unique(dt, by = "From")
  # 构建有向图
  g <- graph_from_data_frame(min_edges, directed = TRUE)
  
  path <- c(start)
  current <- start
  
  while (length(neighbors(g, current, mode = "out")) > 0) {
    # 取当前节点的最小出边邻居
    next_node <- min(neighbors(g, current, mode = "out"))
    path <- c(path, next_node)
    current <- next_node
  }
  
  return(path)
}

# 测试示例1
get_min_path_igraph(dt1)  # [1] 1 3 4 5 6
# 测试示例2
get_min_path_igraph(dt2)  # [1] 1 3
# 测试示例3
get_min_path_igraph(dt3)  # [1] 1 2 5

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