基于无向图邻接矩阵，求含指定路径的最长简单路径的高效Python实现

首先明确核心：我们要找的是无向图中包含给定简单路径P的最长简单路径——因为简单路径不能重复顶点，P里的所有顶点已经被占用，后续扩展绝对不能再用。基础遍历方法效率低，主要是因为做了大量重复计算和无效遍历，下面是几个针对性的优化方向：

1. 预处理：砍掉无效分支 #

第一步就把P中的所有顶点标记为「已占用」，用集合或者布尔数组存起来（比如used = set(given_path)），后续扩展时直接O(1)判断顶点能不能用，避免每次都去扫P的列表。

另外，把输入的邻接矩阵转换成邻接表——邻接矩阵查邻接点要扫整个n阶矩阵，邻接表直接存每个顶点的相邻节点，遍历效率能提升一大截：

def adj_matrix_to_list(adj_matrix):
    adj_list = [[] for _ in range(len(adj_matrix))]
    for i, row in enumerate(adj_matrix):
        for j, is_connected in enumerate(row):
            if is_connected:
                adj_list[i].append(j)
    return adj_list

2. 拆分问题：化整为零 #

包含P的最长简单路径，本质就是「P前的最长扩展路径」+ P +「P后的最长扩展路径」——因为简单路径是线性的，不可能从P中间的顶点分叉扩展（否则会重复顶点）。所以我们可以把原问题拆成两个独立的子问题：

• 从P的起点S出发，只使用未被占用的顶点，找能向外延伸的最长路径（反向看就是从其他顶点到S的最长路径）
• 从P的终点T出发，只使用未被占用的顶点，找能向外延伸的最长路径

把这两部分和P拼接起来，就是我们要的最长路径，这样拆分后每个子问题的规模都比原问题小很多。

3. 记忆化搜索：避免重复计算 #

对于单端的扩展路径计算，递归+记忆化是很实用的优化方式——把已经计算过的顶点的最长扩展结果存起来，下次再遇到直接用，不用重复递归：

def longest_extension(start, adj_list, used):
    memo = {}  # 缓存：key=当前顶点，value=(最长路径长度, 路径列表)
    
    def dfs(current, visited):
        if current in memo:
            return memo[current]
        max_len = 1
        max_path = [current]
        # 遍历所有邻接点
        for neighbor in adj_list[current]:
            if neighbor not in used and neighbor not in visited:
                new_visited = visited.copy()
                new_visited.add(neighbor)
                sub_len, sub_path = dfs(neighbor, new_visited)
                if sub_len + 1 > max_len:
                    max_len = sub_len + 1
                    max_path = [current] + sub_path
        memo[current] = (max_len, max_path)
        return memo[current]
    
    # 初始已访问集合包含P的所有顶点，避免重复
    initial_visited = set(used)
    _, path = dfs(start, initial_visited)
    # 去掉路径中的start（因为P已经包含它了）
    return path[1:] if len(path) > 1 else []

4. 剪枝：提前终止无效搜索 #

在DFS过程中加入剪枝逻辑，能大幅减少不必要的递归：

• 记录当前找到的最长路径长度，如果当前路径长度加上剩余可用顶点的数量，已经小于这个最长长度，直接停止搜索
• 优先遍历度数高的顶点——度数高的顶点更可能延伸出更长的路径，能更快找到较长路径，更早触发剪枝

5. 小顶点规模下：位掩码DP #

如果未被P占用的顶点数量k很小（比如k≤20），可以用位掩码表示已访问的顶点，用动态规划来计算：

• dp[mask][v]表示访问了mask对应的顶点（二进制位标记），最后停在v时的最长路径长度
• 状态转移：对于每个mask和顶点v，遍历v的邻接点u，如果u不在mask中，就更新dp[mask | (1<<u)][u] = max(dp[mask | (1<<u)][u], dp[mask][v] + 1)

这种方法时间复杂度是O(k²×2ᵏ)，适合顶点数少的场景。

主流程示例 #

把上面的部分拼起来，主函数大概是这样：

def longest_path_contains_given(adj_matrix, given_path):
    used = set(given_path)
    adj_list = adj_matrix_to_list(adj_matrix)
    start = given_path[0]
    end = given_path[-1]
    
    # 计算前后扩展路径
    prefix = longest_extension(start, adj_list, used)
    suffix = longest_extension(end, adj_list, used)
    
    # 拼接结果
    return prefix + given_path + suffix

总结 #

核心优化逻辑就是：

1. 预处理减少无效操作（标记占用顶点、转邻接表）
2. 拆分问题降低复杂度（分两端扩展）
3. 用记忆化/DP避免重复计算
4. 剪枝砍掉不可能的分支

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