如何在DAG中筛选从起始节点出发的完整路径？

嘿，作为Python新手能想到从邻居角度判断路径终点，方向完全没错！其实在有向无环图（DAG）里，你要找的“完整路径”就是那些**到达没有出边节点（出度为0）**的路径——这类节点就是DAG的终止节点，没有后续可以继续走的邻居。

下面给你两种实用的实现思路，结合NetworkX来完成需求：

方法一：先获取所有路径，再过滤终止路径 #

如果你已经有了find_all_paths函数（或者直接用NetworkX内置的nx.all_simple_paths），可以先拿到所有从起始节点出发的路径，再筛选出最后一个节点是终止节点的路径：

import networkx as nx

# 构建你的DAG
glavnaLista = [(6, 7), (6, 15), (15, 16), (16, 21), (15, 9), (9, 13), (13, 4), (4, 1), (1, 5)]
G = nx.DiGraph()
G.add_edges_from(glavnaLista)

# 用NetworkX内置函数获取所有从6出发的简单路径
all_paths = list(nx.all_simple_paths(G, source=6))

# 过滤：只保留最后一个节点出度为0的路径（终止节点）
complete_paths = [path for path in all_paths if G.out_degree(path[-1]) == 0]

print(complete_paths)
# 输出结果：[[6, 7], [6, 15, 16, 21], [6, 15, 9, 13, 4, 1, 5]]

这里的核心是G.out_degree(node)方法：它会返回节点的出边数量，等于0就意味着这个节点没有后续邻居，是路径的终点。

方法二：遍历过程中直接判断终止，避免多余计算 #

如果你的DAG规模较大，先生成所有路径再过滤可能会浪费资源。我们可以用深度优先搜索（DFS）的思路，在遍历路径时就检查当前节点是不是终止节点，是的话直接保存路径，否则继续遍历邻居：

import networkx as nx

glavnaLista = [(6, 7), (6, 15), (15, 16), (16, 21), (15, 9), (9, 13), (13, 4), (4, 1), (1, 5)]
G = nx.DiGraph()
G.add_edges_from(glavnaLista)

def find_complete_paths(graph, start_node):
    complete_paths = []
    # 用栈存储当前正在遍历的路径，初始路径是起始节点本身
    stack = [[start_node]]
    
    while stack:
        current_path = stack.pop()
        last_node = current_path[-1]
        
        # 判断当前节点是否为终止节点（出度为0）
        if graph.out_degree(last_node) == 0:
            complete_paths.append(current_path)
            continue
        
        # 遍历当前节点的所有邻居，生成新路径继续探索
        for neighbor in graph.neighbors(last_node):
            new_path = current_path.copy()
            new_path.append(neighbor)
            stack.append(new_path)
    
    # 按路径长度排序，和你预期的输出顺序一致
    complete_paths.sort(key=len)
    return complete_paths

# 调用函数获取结果
result = find_complete_paths(G, 6)
print(result)
# 输出结果：[[6, 7], [6, 15, 16, 21], [6, 15, 9, 13, 4, 1, 5]]

这种方法不会生成那些没走到终点的中间路径，效率更高，也更贴合“只保留完整路径”的需求。

内容的提问来源于stack exchange，提问作者Gaming.ingrs