如何修改DFS算法以查找图的最长导出路径（Longest Induced Path）

你当前的DFS代码无法正确找到最长导出路径（导出路径要求：路径中任意两个非连续的节点在原图中不存在直接边，且路径中无重复节点），现有输出出现重复节点且违反导出路径约束（比如路径[0,1,2,3,4,3,2,1,0]中0和4直接相连，但在路径中是非连续节点，不符合要求）。

现有代码的核心问题 #

• 全局vis数组标记节点为已访问后无法回溯，导致无法探索其他可能的路径组合
• 直接拼接子节点的dp路径会引入重复节点，且未检查新节点与路径中其他非相邻节点的边约束
• dp数组的设计未考虑导出路径的动态约束，仅单纯累加路径长度

修改方案（重点调整DFS函数） #

1. 替换全局vis为路径级访问集合：使用当前路径的已访问节点集合，递归回溯时可恢复状态，支持探索多条路径
2. 添加导出路径约束检查：新加入路径的邻居节点，必须满足两个条件：
   • 未在当前路径中出现过
   • 与当前路径中除当前节点外的所有节点都没有直接边
3. 动态跟踪最长路径：在递归过程中实时对比当前路径与全局最长路径，更新最长路径

修改后的完整代码 #

def dfs(node, adj, current_path, visited, longest_path):
    # 更新最长路径
    if len(current_path) > len(longest_path[0]):
        longest_path[0] = current_path.copy()
    
    # 遍历所有邻居
    for neighbor in adj[node]:
        # 检查邻居是否符合导出路径要求：未访问，且与路径中除当前节点外的所有节点无连接
        if neighbor not in visited:
            valid = True
            for node_in_path in current_path[:-1]:  # 排除当前节点（current_path最后一个是当前node）
                if neighbor in adj[node_in_path]:
                    valid = False
                    break
            if valid:
                # 回溯：加入路径和访问集合
                current_path.append(neighbor)
                visited.add(neighbor)
                dfs(neighbor, adj, current_path, visited, longest_path)
                # 回溯：移除路径和访问集合
                current_path.pop()
                visited.remove(neighbor)

def findLongestInducedPath(adj, n):
    longest_path = [[]]
    # 遍历每个节点作为起始点
    for start in range(n):
        current_path = [start]
        visited = set([start])
        dfs(start, adj, current_path, visited, longest_path)
    return longest_path[0]

# 测试用邻接表
adj = [[1, 4], [0, 2], [1, 3, 4], [2, 4], [0, 2, 3]]
final = findLongestInducedPath(adj, len(adj))
print("最长导出路径:", final)

代码关键点说明 #

• longest_path用列表包裹是为了在递归中修改其值（列表是可变对象，可在函数内部直接更新）
• 每次递归前检查邻居是否与当前路径中除了当前节点外的所有节点都无连接，严格满足导出路径的约束
• 回溯操作确保每个节点可以被多次加入不同的路径，遍历所有可能的合法导出路径

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