如何用NetworkX查找图中指定节点出发的所有特定路径

我需要分析一个约20个节点的简单有向图，目标是找出从任意指定节点出发的所有最大简单路径——也就是无法再延长的简单路径（路径中无重复节点）。路径的终止条件为：终点节点要么没有出邻接节点，要么所有出邻接节点都已在当前路径中。

NetworkX自带的all_simple_paths方法必须指定终点，无法直接满足需求。以下是我的示例图代码：

import networkx as nx
import numpy as np
import matplotlib.pyplot as plt

nodes = [[0, 1], [1, 2], [2, 3], [1, 4], [3, 1], [0, 2]]

# 构建有向图
rl_graph = nx.DiGraph()
rl_graph.add_edges_from(nodes)

# 绘制图形
positions = {}
for idx, node in enumerate(rl_graph.nodes):
    phi = 2 * np.pi / len(rl_graph.nodes) * idx
    positions[node] = [np.cos(phi), np.sin(phi)]
nx.draw(rl_graph, pos=positions)
nx.draw_networkx_labels(rl_graph, positions)    
plt.show()

预期输出 #

• 从节点0出发的所有路径：

  0, 1, 2, 3
  0, 2, 3, 1
  0, 1, 4
  0, 2, 3, 1, 4
  

• 从节点1出发的所有路径：

  1, 4
  1, 2, 3
  

通过递归深度优先搜索（DFS）实现，遍历过程中记录当前路径和已访问节点，当遇到无法继续扩展的节点时，将当前路径加入结果集。

实现代码 #

import networkx as nx

def find_all_max_paths(graph, start):
    all_paths = []
    
    def dfs(current_node, path, visited):
        # 检查当前节点是否还有未访问的邻接节点
        has_unvisited = any(neighbor not in visited for neighbor in graph.neighbors(current_node))
        # 无法扩展时记录路径
        if not has_unvisited:
            all_paths.append(path.copy())
            return
        
        # 遍历所有未访问的邻接节点，继续递归
        for neighbor in graph.neighbors(current_node):
            if neighbor not in visited:
                dfs(neighbor, path + [neighbor], visited | {neighbor})
    
    # 初始化DFS：起点加入路径和已访问集合
    dfs(start, [start], {start})
    return all_paths

# 测试示例图
nodes = [[0, 1], [1, 2], [2, 3], [1, 4], [3, 1], [0, 2]]
rl_graph = nx.DiGraph()
rl_graph.add_edges_from(nodes)

# 输出从节点0出发的路径
print("从节点0出发的路径：")
for path in find_all_max_paths(rl_graph, 0):
    print(", ".join(map(str, path)))

# 输出从节点1出发的路径
print("\n从节点1出发的路径：")
for path in find_all_max_paths(rl_graph, 1):
    print(", ".join(map(str, path)))

代码说明 #

1. 递归逻辑：
   • 每次递归时，检查当前节点是否存在未访问的邻接节点。如果没有，说明路径已达最大长度，将其存入结果列表。
   • 若存在未访问节点，就对每个节点进行递归遍历，更新路径和已访问集合，确保路径始终是简单路径（无重复节点）。
2. 终止条件匹配：
   • 当节点没有出边时，自然无法扩展；当所有出边节点都已在路径中时，继续遍历会形成循环，因此终止。
3. 性能适配：
   • 对于20个节点的图，最坏情况时间复杂度为O(n!)，但实际中因图的结构和终止条件限制，运行效率足以满足需求。

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