You need to enable JavaScript to run this app. Java基于邻接矩阵求解无权重DAG最长路径的实现方法
优惠活动
大模型
产品
解决方案
定价
更多

Java基于邻接矩阵求解无权重DAG最长路径的实现方法

无权DAG最长路径实现逻辑(基于拓扑排序,适配邻接矩阵输入)

基础认知澄清

  • 普通BFS仅适用于边权为1的单源最短路径求解,无法直接用于最长路径计算
  • DFS并非仅适用于树结构:DAG场景下DFS搭配记忆化缓存也可求解最长路径,但拓扑排序方案实现更稳定,节点量较大时不会出现递归栈溢出问题

你最初写的代码雏形存在几个基础问题:未指定数组初始化长度、未遍历所有节点做访问标记、没有基于邻接矩阵遍历邻接关系,无法直接运行。

核心实现步骤

约定邻接矩阵定义:adj[i][j] = 1表示存在从节点i指向节点j的有向边,adj[i][j] = 0表示无关联;输入的节点总数为n,邻接矩阵为n*n的二维数组。

  • 统计所有节点的入度,初始化入度数组inDegree,长度为n
    • 遍历邻接矩阵所有位置,若adj[i][j] = 1,则inDegree[j] += 1
  • 初始化队列,将所有入度为0的节点入队,作为拓扑遍历的起点
  • 初始化最长路径数组dist
    • 若最长路径按节点数量统计:dist数组初始值全为1(单个节点自身为一条长度为1的路径)
    • 若最长路径按边数量统计:dist数组初始值全为0
  • 按拓扑顺序遍历并松弛边
    • 依次从队列取出节点u,遍历邻接矩阵的第u行,找到所有满足adj[u][j] = 1的邻接节点j
    • 对每个邻接节点j,若dist[j] < dist[u] + 1,则更新dist[j] = dist[u] + 1
    • 将j的入度减1,若入度降至0,则将j加入队列
  • 遍历dist数组取最大值,即为整个DAG的最长路径长度

Java参考实现

import java.util.LinkedList;
import java.util.Queue;

public class DagLongestPath {
    /**
     * 求解无权DAG的最长路径长度
     * @param adj n*n二维邻接矩阵,adj[i][j]为1表示i到j有有向边
     * @param nodeCount 图中节点总数量
     * @return 最长路径的节点数
     */
    public static int longestPath(int[][] adj, int nodeCount) {
        // 边界处理
        if (nodeCount <= 0) {
            return 0;
        }
        // 入度数组
        int[] inDegree = new int[nodeCount];
        // 遍历邻接矩阵统计入度
        for (int i = 0; i < nodeCount; i++) {
            for (int j = 0; j < nodeCount; j++) {
                if (adj[i][j] == 1) {
                    inDegree[j]++;
                }
            }
        }
        // 拓扑排序队列,初始化入度为0的无前置依赖节点
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < nodeCount; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        // 初始化最长路径数组,按节点数统计则初始值为1
        int[] dist = new int[nodeCount];
        for (int i = 0; i < nodeCount; i++) {
            dist[i] = 1;
        }
        int maxLength = 1;
        // 拓扑遍历处理所有节点
        while (!queue.isEmpty()) {
            int currentNode = queue.poll();
            // 遍历当前节点的所有邻接节点
            for (int nextNode = 0; nextNode < nodeCount; nextNode++) {
                if (adj[currentNode][nextNode] == 1) {
                    // 松弛操作:更新邻接节点的最长路径值
                    if (dist[nextNode] < dist[currentNode] + 1) {
                        dist[nextNode] = dist[currentNode] + 1;
                    }
                    // 邻接节点入度减1,所有前置节点处理完成后入队
                    inDegree[nextNode]--;
                    if (inDegree[nextNode] == 0) {
                        queue.offer(nextNode);
                        // 更新全局最长路径值
                        if (dist[nextNode] > maxLength) {
                            maxLength = dist[nextNode];
                        }
                    }
                }
            }
        }
        return maxLength;
    }
}

注意:该实现默认输入为合法DAG(无环),如果图中存在环,拓扑遍历会提前终止,无法处理所有节点,可增加校验逻辑:若最终遍历的节点数小于nodeCount,则判定图非DAG,不适用该求解逻辑。

内容的提问来源于stack exchange,提问作者none_kak

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.05 01:24:03