您可以尝试以下代码

dt %>%
  group_by(From) %>%
  slice_min(To) %>%
  graph_from_data_frame() %>%
  ego(
    order = sum((m <- membership(components(.))) == m[names(m) == "1"]),
    nodes = "1",
    mode = "out"
  ) %>%
  pluck(1) %>%
    names() %>%
    as.numeric()

或者使用subcomponent更简单（如@clp）

dt %>%
  group_by(From) %>%
  slice_min(To) %>%
  graph_from_data_frame() %>%
  subcomponent(v = "1", mode = "out") %>%
  names() %>%
  as.integer()

其给出了

• 对于第一个新的更新数据

[1] 1 3

• 对于第二次更新的数据

[1] 1 2 5

假设有一个有序的 From 和 To 列表，这可能有效。
它首先按 From 分组，按 To 压缩，然后使用shift排除不匹配的 From-To 值。
如果缺少跳转（例如，To 3但 From 3缺失），则打印NULL

dt[, .(frst = first(To)), From][
  , if(all((frst %in% From)[1:(.N - 1)])){
      c(1, unique(frst[From == shift(frst, type = "lag", fill = T)]))}]
[1] 1 3 4 5 6

从Igraph和subcomponents()使用。
在ThomasisCoding的评论之后，我意识到graph_from_data_frame是通过名称创建图的。如果图很大（1E6），这是对内存（和时间）的浪费。还要注意graph_from_edgelist(as.matrix(...))要快得多。

dt2 <- setNames(aggregate(dt$To, list(dt$From), "min"), c("From", "To") )
g <- graph_from_edgelist(as.matrix(dt2), directed=TRUE) 
as.numeric(as_ids(subcomponent(g, 1, mode="out")))

第一次尝试

dt2 <- setNames(aggregate(dt$To, list(dt$From), "min"), c("From", "To") )
g <- graph_from_data_frame(dt2, directed=TRUE) 
as.numeric(as_ids(subcomponent(g, 1, mode="out")))

我似乎无法得到其他答案来处理某些表。例如，

library(data.table)
library(igraph)
library(purrr)

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

fPath1 <- function(dt) {
  setorder(dt, From, To)[, wt := fifelse(rleid(To)==1,1,Inf), From] %>%
    graph_from_data_frame() %>%
    set_edge_attr(name = "weight", value = dt[, wt]) %>%
    shortest_paths(min(dt[, From]), max(dt[, To])) %>%
    pluck(1) %>%
    unlist(use.names = FALSE)
}

fPath2 <- function(dt) {
  dt[, .SD[which.min(To)], From] %>%
    graph_from_data_frame() %>%
    shortest_paths(min(dt[, From]), max(dt[, To])) %>%
    pluck(1) %>%
    unlist(use.names = FALSE)
}

fPath3 <- function(dt) {
  dt[, .(frst = first(To)), From][
    , if(all((frst %in% From)[1:(.N - 1)])){
      c(1, unique(frst[From == shift(frst, type = "lag", fill = T)]))}]
}

fPath1(dt)
#> [1] 1 6
fPath2(dt)
#> Warning in shortest_paths(., min(dt[, From]), max(dt[, To])): At core/paths/
#> unweighted.c:368 : Couldn't reach some vertices.
#> integer(0)
fPath3(dt)
#> NULL

这个igraph解决方案似乎是基于更广泛的测试而工作的：

fPath4 <- function(dt) {
  g <- graph_from_data_frame(dt)
  E(g)$weight <- (dt$To - dt$From)^2
  as.integer(V(g)[shortest_paths(g, V(g)[1], V(g)[name == dt$To[nrow(dt)]])$vpath[[1]]]$name)
}

fPath4(dt)
#> [1] 1 4 6

一个连续的解决方案是可行的。复制一百万行 Dataframe 在我的系统上花了8秒。

n <- 1E6
df1 <- data.frame(from=sample(n), to=sample(n))
path <- c()
system.time(
for (i in seq(nrow(df1)) ){
  path[length(path) + 1] <- df1[i, "to"]   # avoid copying.
}
)
mean(path)
length(path)

输出。

[1] 500000.5
[1] 1000000

更新后，菲尔的最后一次编辑。第一步是简化输入（df）。

## Select min(To) by From.
if (nrow(df) > 0) { df2 <- setNames(aggregate(df$To, list(df$From), "min"), c("From", "To") )
} else              df2 <- df

将路径设置为第一个开始节点，然后追加结束节点

## Let tt is maximal outgoing node upto now.
path <- df2[1,1]
tt <- df2[1,1]
for (i in seq_len(nrow(df2))){
  if      (df2[i, 1] < tt) next
  else if (df2[i,1] == tt) { tt <- df2[i, 2]
                             path[length(path) + 1] <- df2[i, 2]
                           }
  else                     break
}
head(path)

输出量：

[1] 1 3 4 5 6 , df as in first example.
[1] 1 2 5     , df as in another example.