无权重有向无环图(DAG)中覆盖最多节点的最长路径求解方案咨询

推荐采用拓扑排序+动态规划的组合方案实现需求，该方案时间复杂度为O(V+E)（V为节点数、E为边数），适配所有最长路径导出的场景，实现逻辑如下：

1. 预处理：输出DAG的拓扑排序序列 #

对目标DAG执行拓扑排序，确保处理任意节点时，其所有前驱节点都已完成计算，避免动态规划的依赖顺序问题。

2. 动态规划状态记录 #

定义两个存储结构：

• dp[u]：表示以节点u为终点的最长路径的长度，所有节点初始值设为1（单个节点自身构成长度为1的路径）
• pre[u]：列表类型，存储所有可使节点u获得最长路径的前驱节点，用于后续回溯完整路径

按拓扑排序的正序遍历每个节点u，遍历u的所有出边指向的邻接节点v，执行如下判断：

• 若dp[v] < dp[u] + 1：说明找到更长的到v的路径，更新dp[v] = dp[u] + 1，清空pre[v]原有值后将u加入pre[v]
• 若dp[v] == dp[u] + 1：说明找到另一条长度相同的到v的路径，直接将u追加到pre[v]中即可

3. 确定最长路径的基础参数 #

遍历所有节点的dp值，得到最大值max_len即为最长路径的长度；所有dp值等于max_len的节点，都是最长路径的终点。

4. 回溯导出所有最长路径 #

对每个最长路径的终点执行回溯：从终点出发，递归遍历pre数组中存储的前驱节点，直到遇到无前驱的起点节点，将回溯得到的逆序路径反转即可得到正序的最长路径，所有回溯结果即为全部长度相同的最长序列。

简单伪代码参考 #

# 拓扑排序函数（基于 Kahn 算法实现）
def topological_sort(graph, in_degree):
    q = deque([u for u in in_degree if in_degree[u] == 0])
    topo_order = []
    while q:
        u = q.popleft()
        topo_order.append(u)
        for v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                q.append(v)
    return topo_order

# 回溯生成所有路径
def backtrack(node, pre, path, result):
    path.append(node)
    if not pre[node]:
        result.append(path[::-1])
    else:
        for p in pre[node]:
            backtrack(p, pre, path.copy(), result)

过往方案的适配性说明 #

• 纯DFS实现如果没有做记忆化和路径去重，很容易出现重复计算、遗漏路径或者递归深度溢出的问题，仅适合极小规模的DAG
• Floyd-Warshall算法原生为全源最短路径设计，改造为最长路径后时间复杂度高达O(V^3)，仅能支撑节点数极少的场景，且记录全量最长路径的实现成本极高

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