当前位置：首页 > news >正文

有向图查询所有环，非递归

news 来源：原创 2024/5/19 8:43:08

图：
在这里插入图片描述

有向图查询所有环，非递归：

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);}}
}