一个顶点,多个出口,有向有环图,碰到环的话遍历深度为1,给出能遍历出这张图所有可执行链路的java8代码,同时要求以顶点为开始以无后置连接的点为结束来进行输出
时间: 2023-11-28 20:49:21 浏览: 135
MSRC-9数据集 图神经网络
以下是能够遍历出所有可执行链路的Java 8代码:
```java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class DirectedAcyclicGraph {
private Map<Integer, List<Integer>> graph;
public DirectedAcyclicGraph(Map<Integer, List<Integer>> graph) {
this.graph = graph;
}
public List<List<Integer>> findAllPaths(int start) {
List<List<Integer>> paths = new ArrayList<>();
List<Integer> path = new ArrayList<>();
path.add(start);
findAllPaths(start, path, paths);
return paths;
}
private void findAllPaths(int current, List<Integer> path, List<List<Integer>> paths) {
if (!graph.containsKey(current)) {
paths.add(new ArrayList<>(path));
return;
}
for (int next : graph.get(current)) {
path.add(next);
findAllPaths(next, path, paths);
path.remove(path.size() - 1);
}
}
public static void main(String[] args) {
Map<Integer, List<Integer>> graph = new HashMap<>();
graph.put(1, List.of(2, 3));
graph.put(2, List.of(4));
graph.put(3, List.of(4));
graph.put(4, List.of(5, 6));
graph.put(5, List.of(7));
graph.put(6, List.of(7));
graph.put(7, List.of(8));
graph.put(8, List.of());
DirectedAcyclicGraph dag = new DirectedAcyclicGraph(graph);
List<List<Integer>> paths = dag.findAllPaths(1);
for (List<Integer> path : paths) {
if (graph.get(path.get(path.size() - 1)).isEmpty()) {
System.out.println(path);
}
}
}
}
```
这个代码使用递归的方式遍历所有路径。其中,`graph` 是一个有向无环图的邻接表表示,`findAllPaths` 方法接受一个起始顶点,返回从该顶点出发能够遍历到的所有路径。最后在 `main` 方法中,我们找到以无后置连接的点为结束的路径并输出。
阅读全文