按时间加权 有向图 关键路径 java 代码
时间: 2023-11-27 10:04:22 浏览: 53
为了计算一个按时间加权有向图的关键路径,可以使用 Java 语言来实现 DAG(有向无环图)算法。
以下是示例代码:
```
import java.util.*;
public class DAG {
private int V;
private LinkedList<Integer> adj[];
private int[] indegree;
DAG(int v) {
V = v;
adj = new LinkedList[v];
indegree = new int[V];
for (int i = 0; i < v; i++) {
adj[i] = new LinkedList();
indegree[i] = 0;
}
}
void addEdge(int v, int w) {
adj[v].add(w);
indegree[w]++;
}
void topologicalSort() {
Stack<Integer> stack = new Stack<>();
int[] dist = new int[V];
Arrays.fill(dist, Integer.MIN_VALUE);
dist[0] = 0;
for (int i = 0; i < V; i++)
if (indegree[i] == 0)
stack.push(i);
while (!stack.isEmpty()) {
int u = stack.pop();
for (int i = 0; i < adj[u].size(); i++) {
int v = adj[u].get(i);
if (dist[u] + 1 > dist[v])
dist[v] = dist[u] + 1;
if (--indegree[v] == 0)
stack.push(v);
}
}
System.out.println("The length of the critical path is " + dist[V-1]);
}
public static void main(String args[]) {
DAG dag = new DAG(6);
dag.addEdge(0, 1);
dag.addEdge(0, 2);
dag.addEdge(1, 3);
dag.addEdge(2, 3);
dag.addEdge(3, 4);
dag.addEdge(3, 5);
dag.topologicalSort();
}
}
```
这段代码通过入度和拓扑排序的方式计算了关键路径的长度。在这个示例中,我们有一个图(0,1,2,3,4,5)和一些有向边。
输出为: The length of the critical path is 3
意思是从顶点 0 到顶点 5 的关键路径长度是 3。
相关推荐
![py](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)