如何在Python中从有向循环图获取节点前驱列表（避免无限循环）

通过以下代码构建了一个有向循环图：

import pandas as pd
import networkx as nx
df = pd.DataFrame({ 'from':['A', 'B', 'C','K','J','K','A'], 'to':['C', 'D','D','A','A','J','K']})
network = nx.from_pandas_edgelist(df,source='from',target='to', edge_attr=None, create_using=nx.DiGraph())

需要获取指定节点的所有前驱节点列表，针对无环图写了如下递归函数：

from itertools import chain

def get_predecessors_all(graph, nodes):

    """
    Recursively get all the predecessors of a node or a list of nodes
    :param graph: graph to be transversed
    :param nodes: a single node or a list of nodes for which the list of predecessors is required
    :return: list of predecessor nodes
    """
    
    if not isinstance(nodes, list):
        nodes = [nodes]
    for node in nodes:
        node_predecessors = [graph.predecessors(node)]
        #print(node)
    # get all the immediate predecessors
    node_predecessors = list(chain.from_iterable(node_predecessors))
    if not node_predecessors:   # if reached a root & no more predecessors, stop and return
        return node_predecessors
    else: 
    # otherwise, get the predecessors of the current list of nodes
        return node_predecessors + get_predecessors_all(graph, node_predecessors)
pred_list=get_predecessors_all(network, ['D'])

但由于图是有向循环图（比如A→K→J→A形成环），上述函数会陷入无限循环，需要修改函数以得到目标前驱列表['B','C','A','K','J']。

要解决无限循环问题，核心是记录已经访问过的节点，避免重复递归处理。同时原函数存在bug：遍历nodes时每次覆盖node_predecessors，导致只处理最后一个节点的前驱，需要一并修复。

修改后的函数如下：

from itertools import chain

def get_predecessors_all(graph, nodes, visited=None):
    """
    Recursively get all the predecessors of a node or a list of nodes, avoiding cycles
    :param graph: graph to be traversed
    :param nodes: a single node or a list of nodes for which the list of predecessors is required
    :param visited: set of nodes already processed, to avoid cycles
    :return: list of unique predecessor nodes
    """
    # 初始化已访问集合
    if visited is None:
        visited = set()
    
    if not isinstance(nodes, list):
        nodes = [nodes]
    
    # 收集所有当前节点的未访问过的前驱
    all_predecessors = []
    for node in nodes:
        # 标记当前节点为已访问，避免后续重复处理
        visited.add(node)
        # 获取当前节点的前驱，过滤掉已访问的节点
        preds = [p for p in graph.predecessors(node) if p not in visited]
        all_predecessors.extend(preds)
        # 把这些前驱也标记为已访问，防止后续递归重复处理
        visited.update(preds)
    
    if not all_predecessors:
        return []
    else:
        # 递归获取前驱的前驱，加上当前的前驱列表
        return all_predecessors + get_predecessors_all(graph, all_predecessors, visited)

# 调用函数并保持首次出现的顺序去重
pred_list = get_predecessors_all(network, ['D'])
pred_list = list(dict.fromkeys(pred_list))
print(pred_list)  # 输出: ['B', 'C', 'A', 'K', 'J']

关键修改说明 #

1. 添加visited集合：用来记录已经处理过的节点，彻底避免循环递归。
2. 修复前驱收集逻辑：原函数遍历nodes时会覆盖结果，现在改为遍历所有节点，汇总所有前驱。
3. 过滤已访问节点：每次获取前驱时，只处理未访问过的节点，避免重复进入循环链路。
4. 提前标记已访问：处理节点后立即标记为已访问，防止后续分支重复处理同一节点。

执行逻辑 #

• 从节点D开始，获取其前驱B、C，标记D、B、C为已访问。
• 递归处理B、C：B无前置节点，C的前驱A未被访问，收集A并标记。
• 递归处理A：A的前驱K、J未被访问，收集K、J并标记。
• 递归处理K、J：K的前驱A已访问，J的前驱K已访问，无新前驱，递归终止。
• 最终得到与目标一致的前驱列表。

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