图：
有向图查询所有环，非递归：
import java.util.*;
public class CycleTest {
private final int V; // 顶点数
private final List<List<Integer>> adjList; // 邻接表
public CycleTest(int vertices) {
this.V = vertices;
this.adjList = new ArrayList<>(vertices);
for (int i = 0; i < vertices; i++) {
adjList.add(new LinkedList<>());
}
}
// 添加有向边
public void addEdge(int src, int dest) {
adjList.get(src).add(dest);
}
// 查找所有环
public List<List<Integer>> findAllCycles() {
List<List<Integer>> cycles = new ArrayList<>();
Stack<Integer> stack = new Stack<>();
Stack<Integer> pathStack = new Stack<>();
Stack<Integer> neighborPoint = new Stack<>();
Stack<Integer> levelStack = new Stack<>();
boolean[] visited = new boolean[V];
int level = 1;
for (int startVertex = 0; startVertex < V; startVertex++) {
if (visited[startVertex]) {
continue;
}
stack.push(startVertex);
pathStack.push(startVertex);
while (!stack.isEmpty() || !neighborPoint.isEmpty()) {
if (stack.isEmpty()) {
int l = levelStack.pop();
// 返回上一个邻接点搜索
Integer p = neighborPoint.pop();
stack.push(p);
while (pathStack.size() >= l) {
pathStack.pop();
}
pathStack.push(p);
level--;
}
int vertex = stack.pop();
List<Integer> neighbors = adjList.get(vertex);
for (int i = 0; i < neighbors.size(); i++) {
Integer neighbor = neighbors.get(i);
if (i == 0) {
if (!pathStack.contains(neighbor)) {
stack.push(neighbor);
pathStack.push(neighbor);
} else {
// 找到环
List<Integer> cycle = new ArrayList<>();
List<Integer> path = pathStack.stream().toList();
for(int j = path.size() - 1; j >= 0; j--) {
Integer p = path.get(j);
cycle.add(p);
visited[p] = true;
if (Objects.equals(p, neighbor)) {
break;
}
}
Collections.reverse(cycle);
cycles.add(cycle);
}
level++;
} else {
// 存储邻接点
neighborPoint.push(neighbor);
levelStack.push(level);
}
}
}
// 清除路径栈状态
pathStack.clear();
levelStack.clear();
level = 1;
}
return cycles;
}
public static void main(String[] args) {
CycleTest graph = new CycleTest(4);
graph.addEdge(0, 1);
graph.addEdge(1, 2);
graph.addEdge(2, 0);
graph.addEdge(1, 3);
graph.addEdge(3, 2);
List<List<Integer>> cycles = graph.findAllCycles();
System.out.println("Cycles in the directed graph:");
for (List<Integer> cycle : cycles) {
System.out.println(cycle);
}
}
}
结果：
