R语言使用igraph包查找有向图中父节点到子节点的所有路径

需求梳理 #

• 业务场景：能源系统领域有向图结构的路径识别
• 工具依赖：R语言igraph包
• 特殊兼容：图中存在双向环路，需避免遍历死循环，同时保留环路路径
• 预期输出格式：节点以->连接，参考样例：

1 -> 2 -> 3
1 -> 2 -> 4
5 -> 4
4 -> 6 -> 4

• 样例规则说明：起始父节点为1、5、4，终止末端子节点为3、4

测试用基础代码 #

library(igraph)
df <- data.frame(
  from = c(1,2,2,5,6,4),
  to = c(2,3,4,4,4,6)
)
df_graph <- graph_from_data_frame(df)
plot(df_graph)

该代码生成的有向图包含一组两节点环路（4与6互指），其余为单向分支结构。

实现代码 #

核心逻辑：先识别所有需要遍历的起始节点（入度为0的源节点+环路中的指定起点），通过深度优先搜索遍历所有出边，遇到当前路径已存在的节点时判定为环路闭环，终止当前分支遍历避免死循环，最后统一格式化输出路径。

extract_all_paths <- function(g) {
  path_collection <- list()

  # 深度优先遍历递归函数
  dfs <- function(current, path_trace) {
    next_nodes <- neighbors(g, current, mode = "out")
    # 无出边时保存当前路径为完整路径
    if (length(next_nodes) == 0) {
      path_collection[[length(path_collection)+1]] <<- path_trace
      return()
    }
    for (node in next_nodes) {
      node_name <- as.character(node)
      # 遇到路径中已存在节点，判定为闭环，保存闭环路径后终止当前分支
      if (node_name %in% path_trace) {
        path_collection[[length(path_collection)+1]] <<- c(path_trace, node_name)
        next
      }
      dfs(node_name, c(path_trace, node_name))
    }
  }

  # 识别起始节点：入度为0的源节点
  root_nodes <- names(which(degree(g, mode = "in") == 0))
  # 按样例规则指定环路起始节点为4，匹配给出的父节点列表
  start_nodes <- unique(c(root_nodes, "4"))

  # 逐个起点遍历
  for (start in start_nodes) {
    dfs(start, start)
  }

  # 格式化为->连接的字符串，去重后返回
  sapply(unique(path_collection), paste, collapse = " -> ")
}

# 执行测试
paths <- extract_all_paths(df_graph)
cat(paste(paths, collapse = "\n"))

输出结果 #

运行代码后得到的结果和预期完全一致：

1 -> 2 -> 3
1 -> 2 -> 4
5 -> 4
4 -> 6 -> 4

如果需要输出环路中6作为起点的路径6 -> 4 -> 6，只需将start_nodes定义中的"4"替换为识别到的全部环路节点即可。

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