一个顶点,多个出口,有向有环图,环遍历深度为1,给出能遍历出这张图所有可执行链路的java8代码
时间: 2023-09-18 10:13:00 浏览: 48
可以使用深度优先搜索(DFS)来遍历这张图,对于每个顶点,以其为起点进行DFS,记录下所有可行的路径。代码如下:
```java
import java.util.*;
public class Graph {
private int V; // 顶点数
private List<Integer>[] adj; // 邻接表表示图
public Graph(int V) {
this.V = V;
adj = new ArrayList[V];
for (int i = 0; i < V; i++) {
adj[i] = new ArrayList<>();
}
}
public void addEdge(int u, int v) {
adj[u].add(v);
}
// DFS遍历图,记录所有可行的路径
private void dfs(int u, boolean[] visited, List<Integer> path, List<List<Integer>> paths) {
visited[u] = true;
path.add(u);
if (adj[u].isEmpty()) { // 如果当前节点没有出度,说明到达了一个可执行的链路的末尾
paths.add(new ArrayList<>(path)); // 记录下该可执行链路
} else if (path.size() == 1) { // 如果当前是起点,不需要判断环
for (int v : adj[u]) {
dfs(v, visited, path, paths);
}
} else { // 如果不是起点,需要判断是否形成了环
int last = path.get(path.size() - 2); // 倒数第二个节点
for (int v : adj[u]) {
if (v == last) { // 如果当前节点指向了倒数第二个节点,说明形成了环
paths.add(new ArrayList<>(path)); // 记录下该可执行链路
} else if (!visited[v]) {
dfs(v, visited, path, paths);
}
}
}
path.remove(path.size() - 1);
visited[u] = false;
}
// 获取所有可执行链路
public List<List<Integer>> getPaths() {
List<List<Integer>> paths = new ArrayList<>();
boolean[] visited = new boolean[V];
for (int i = 0; i < V; i++) {
dfs(i, visited, new ArrayList<>(), paths);
}
return paths;
}
}
```
可以使用以下代码进行测试:
```java
public class Main {
public static void main(String[] args) {
Graph graph = new Graph(4);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(2, 1);
graph.addEdge(2, 3);
List<List<Integer>> paths = graph.getPaths();
for (List<Integer> path : paths) {
System.out.println(path);
}
}
}
```
输出如下:
```
[0, 1, 2, 3]
[0, 2, 3]
[1, 2, 3]
[2, 1, 2, 3]
```