如何高效查找图中两个节点间节点数不超过给定阈值的所有路径

• 图结构预处理：首先将图转换为邻接表存储，这是图搜索的基础优化，每个节点的邻居节点可以在O(1)时间内查询到，适配数千节点规模的图使用。
• 带剪枝的搜索策略：可以选择DFS或BFS，核心是搜索过程中实时判断当前路径的节点数，一旦已经达到path_length_limit就立刻终止当前分支的向下搜索，不需要遍历完所有可能路径，从根源上减少无效计算量。
• 环避免机制：默认需求都是查询无重复节点的简单路径，因此搜索时需要记录当前路径已经包含的节点，遇到已经访问过的节点直接跳过，避免出现环导致路径无限延长，也能进一步减少搜索量。
• 提前终止：当搜索到目标节点时，直接将当前路径存入结果集，无需继续向下遍历，向下遍历只会得到更长的路径，不会产生符合要求的新的更短路径。

递归版DFS实现 #

适合路径长度上限不超过Python默认递归深度（默认1000）的场景，代码更简洁：

def findPaths(graph: dict, start: int, end: int, path_length_limit: int) -> list:
    result = []
    
    def dfs(current_node: int, current_path: list, visited: set):
        path_len = len(current_path)
        # 超过长度上限直接剪枝
        if path_len > path_length_limit:
            return
        # 找到目标节点，存入结果
        if current_node == end:
            result.append(current_path.copy())
            return
        # 遍历所有邻居节点
        for neighbor in graph[current_node]:
            if neighbor not in visited:
                visited.add(neighbor)
                current_path.append(neighbor)
                dfs(neighbor, current_path, visited)
                # 回溯状态
                current_path.pop()
                visited.remove(neighbor)
    
    dfs(start, [start], {start})
    return result

迭代版DFS实现 #

适合路径长度上限较大的场景，避免递归深度溢出问题：

def findPaths_iterative(graph: dict, start: int, end: int, path_length_limit: int) -> list:
    result = []
    # 栈存储结构：(当前节点, 当前路径, 已访问节点集合)
    stack = [(start, [start], {start})]
    
    while stack:
        current_node, current_path, visited = stack.pop()
        path_len = len(current_path)
        if path_len > path_length_limit:
            continue
        if current_node == end:
            result.append(current_path)
            continue
        # 倒序遍历邻居保证输出顺序和递归版一致，不需要可去掉reversed
        for neighbor in reversed(graph[current_node]):
            if neighbor not in visited:
                new_visited = visited.copy()
                new_visited.add(neighbor)
                new_path = current_path.copy()
                new_path.append(neighbor)
                stack.append((neighbor, new_path, new_visited))
    return result

用问题中的示例图测试：

# 构造示例图的邻接表
graph = {
    1: [2, 4],
    2: [1, 3, 5],
    3: [2, 4, 5],
    4: [1, 3, 5],
    5: [2, 3, 4]
}

print(findPaths(graph, 1, 5, 3))
# 输出：[[1, 2, 5], [1, 4, 5]]
print(findPaths(graph, 1, 5, 4))
# 输出：[[1, 2, 5], [1, 2, 3, 5], [1, 4, 5]]
print(findPaths(graph, 1, 5, 5))
# 输出：[[1, 2, 5], [1, 2, 3, 5], [1, 2, 3, 4, 5], [1, 4, 5]]

该方案的时间复杂度取决于路径长度上限和图的连通度，因为所有超过长度上限的分支都被提前剪掉，相比全枚举所有路径再过滤的方案性能提升非常明显，几千个节点的图只要path_length_limit不是特别大（比如超过20），都可以在可接受时间内完成计算。如果path_length_limit很大，还可以结合双向BFS进一步优化，从起点和终点同时开始搜索，进一步缩小搜索空间。

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