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加入队列
- 依次从队列取出节点u,遍历邻接矩阵的第u行,找到所有满足
- 遍历
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
相关产品推荐
相关产品推荐

