基于Pandas邻接矩阵求图中两节点间所有简单路径的方法咨询

嘿，我懂你想用Pandas邻接矩阵来获取两点间的所有简单路径——先聊聊你当前用itertools.permutations生成全排列再筛选的思路：逻辑上确实能行，但这个方法的效率太低了，只要节点数量超过五六个，全排列的数量会指数级暴涨，完全不适合实际场景。

更高效的做法是用深度优先搜索（DFS），毕竟简单路径的核心是「不重复访问节点」，DFS可以沿着有效边一步步探索，只生成有意义的路径，避免大量无效计算。下面是具体实现：

实现思路 #

1. 从起点开始，维护当前已访问的路径（确保没有重复节点）
2. 每次遍历当前节点的所有邻接节点（通过Pandas邻接矩阵判断）
3. 如果邻接节点不在当前路径中，就递归探索这个节点
4. 当到达终点时，把当前路径加入结果列表

代码实现 #

import pandas as pd

def find_all_simple_paths(df, start, end, current_path=None, paths=None):
    # 初始化默认参数
    if current_path is None:
        current_path = [start]
    if paths is None:
        paths = []
    
    current_node = current_path[-1]
    
    # 到达终点，记录路径
    if current_node == end:
        paths.append(current_path.copy())
        return paths
    
    # 遍历当前节点的所有邻接节点
    neighbors = df.columns[df.loc[current_node] != 0].tolist()  # 这里根据你的边取值规则调整，比如非NaN或非0
    for neighbor in neighbors:
        if neighbor not in current_path:
            current_path.append(neighbor)
            find_all_simple_paths(df, start, end, current_path, paths)
            current_path.pop()  # 回溯
    
    return paths

# 示例：构造邻接矩阵
nodes = ["A", "B", "C", "D"]
network = pd.DataFrame(
    [[0, 1, 1, 0],
     [0, 0, 1, 1],
     [0, 0, 0, 1],
     [0, 0, 0, 0]],
    index=nodes,
    columns=nodes
)

# 找A到D的所有简单路径
all_paths = find_all_simple_paths(network, "A", "D")
print(all_paths)
# 输出：[['A', 'B', 'D'], ['A', 'B', 'C', 'D'], ['A', 'C', 'D']]

关键说明 #

• 邻接节点判断：代码里用df.loc[current_node] != 0来筛选邻接节点，你需要根据自己的实际数据调整——比如如果你的边值是权重（非零）或者用True/False表示连通，只要把判断条件改成符合你数据逻辑的就行。
• 回溯机制：递归后用current_path.pop()移除当前节点，保证探索完一条分支后能回到上一层，继续探索其他邻接节点。
• 效率对比：和全排列方法比，DFS只沿着有效边走，不会生成那些完全不连通的排列组合，节点数量越多，性能优势越明显。

注意事项 #

• 如果你的图存在环，DFS因为记录了当前路径，不会重复访问节点，所以不会陷入无限循环。
• 如果节点数量非常多（比如几十上百个），两点间的简单路径可能会非常多，这时候要考虑是否真的需要所有路径，或者可以添加剪枝条件（比如限制路径最大长度）。

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