如何用Pandas+NetworkX生成含根节点与中间节点的所有简单路径

针对你的需求——为每一对父-子关系生成包含完整路径、深度的记录，同时单独处理根节点，以下分两种场景给出高效实现方案：

场景1：树结构（每个节点仅一个父节点） #

如果你的数据是树状结构（每个节点最多有一个父节点），用拓扑排序+动态规划的方法最适合10万行规模的数据，时间复杂度O(N)：

import networkx as nx
import pandas as pd

# 替换为你的实际数据加载逻辑
data = pd.read_csv("your_data.csv")  # 假设数据有parent、child两列

# 构建有向图
G = nx.DiGraph()
G.add_edges_from(data[['parent', 'child']].values)

# 找出所有根节点（入度为0的节点）
roots = [node for node in G.nodes() if G.in_degree(node) == 0]

result = []
# 记录每个节点的路径和深度
node_info = {}

# 处理根节点的单独记录
for root in roots:
    node_info[root] = {"path": [root], "depth": 0}
    result.append({
        "parent": None,
        "child": root,
        "path": [root],
        "depth": 0
    })

# 拓扑排序遍历节点（保证父节点先被处理）
for node in nx.topological_sort(G):
    if node in roots:
        continue
    # 树结构中每个节点只有一个父节点
    parent = next(G.predecessors(node))
    # 继承父节点的路径并扩展
    node_info[node] = {
        "path": node_info[parent]["path"] + [node],
        "depth": node_info[parent]["depth"] + 1
    }
    # 添加当前父-子边的记录
    result.append({
        "parent": parent,
        "child": node,
        "path": node_info[node]["path"],
        "depth": node_info[node]["depth"]
    })

# 转换为DataFrame输出
result_df = pd.DataFrame(result)
print(result_df)

场景2：DAG结构（节点可能有多个父节点） #

如果数据是有向无环图（一个节点可能有多个父节点，对应多条路径），同样用拓扑排序收集所有可能路径，确保每条父-子边都对应正确的路径：

import networkx as nx
import pandas as pd

# 加载数据
data = pd.read_csv("your_data.csv")

G = nx.DiGraph()
G.add_edges_from(data[['parent', 'child']].values)

roots = [node for node in G.nodes() if G.in_degree(node) == 0]

result = []
# 记录每个节点的所有可能路径
node_paths = {}

# 初始化根节点
for root in roots:
    node_paths[root] = [[root]]
    result.append({
        "parent": None,
        "child": root,
        "path": [root],
        "depth": 0
    })

# 拓扑排序遍历节点
for node in nx.topological_sort(G):
    if node in roots:
        continue
    all_paths = []
    # 遍历当前节点的所有父节点
    for parent in G.predecessors(node):
        if parent in node_paths:
            # 基于父节点的所有路径生成当前节点的路径
            for path in node_paths[parent]:
                new_path = path + [node]
                all_paths.append(new_path)
                # 添加当前父-子边的对应记录
                result.append({
                    "parent": parent,
                    "child": node,
                    "path": new_path,
                    "depth": len(new_path) - 1
                })
    node_paths[node] = all_paths

result_df = pd.DataFrame(result)
print(result_df)

为什么你之前的方法不适用？ #

• all_simple_paths：它的作用是输出从起点到终点的完整路径（通常到叶子节点），不会针对每条父-子边单独生成记录，无法满足你对每一对关系输出路径的需求。
• shortest_path/single_source_shortest_path：仅返回最短路径，会自动忽略更长的合法路径（比如你提到的1,3,5,4这类非最短路径）。

注意事项 #

• 10万行数据规模下，树结构的方案可以轻松处理；如果是DAG结构且路径数量较多，建议提前过滤冗余路径（如果业务允许），避免内存占用过高。
• 拓扑排序的方法天然适配层级扩展（不管是4层还是n层），无需修改核心逻辑。

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