Java 求最长路径长度问题
时间: 2023-12-14 22:38:09 浏览: 52
在一个有向无环图中(DAG),求最长路径长度的问题可以使用拓扑排序和动态规划来解决。
具体步骤如下:
1. 对 DAG 进行拓扑排序,得到一个顶点的拓扑序列。
2. 初始化一个数组 dp,其中 dp[i] 表示以顶点 i 为终点的最长路径长度。
3. 遍历拓扑序列,对于每个顶点 i,遍历它的所有入边 (j, i),更新 dp[i] 为 max(dp[i], dp[j] + weight(j, i)),其中 weight(j, i) 表示从顶点 j 到顶点 i 的边权重。
4. 最终 dp 数组中的最大值即为最长路径长度。
Java 代码实现如下:
```java
import java.util.*;
public class LongestPath {
public static int longestPath(List<List<Integer>> graph, int n) {
int[] inDegree = new int[n]; // 入度数组
int[] dp = new int[n]; // 动态规划数组
// 计算入度数组
for (int i = 0; i < n; i++) {
for (int j : graph.get(i)) {
inDegree[j]++;
}
}
// 执行拓扑排序
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}
while (!queue.isEmpty()) {
int curr = queue.poll();
for (int next : graph.get(curr)) {
inDegree[next]--;
dp[next] = Math.max(dp[next], dp[curr] + 1);
if (inDegree[next] == 0) {
queue.offer(next);
}
}
}
// 找到最长路径长度
int maxPathLength = 0;
for (int i = 0; i < n; i++) {
maxPathLength = Math.max(maxPathLength, dp[i]);
}
return maxPathLength;
}
public static void main(String[] args) {
List<List<Integer>> graph = new ArrayList<>();
graph.add(Arrays.asList(1, 2));
graph.add(Arrays.asList(3));
graph.add(Arrays.asList(3));
graph.add(Collections.emptyList());
int n = 4;
System.out.println(longestPath(graph, n)); // 输出 2
}
}
```
在这个例子中,有向无环图如下所示:
```
0 -> 1 -> 3
\-> 2 -/
```
其中顶点 0 到顶点 3 的最长路径长度为 2。