我想用java查找有向图中的环并且输出环所在的路径

以下是一个使用深度优先搜索算法在有向图中查找环的Java代码。该算法从每个节点开始遍历图，并记录访问过的节点。如果在遍历过程中找到了一个已经访问过的节点，那么就找到了一个环。在找到环之后，可以通过回溯来输出环所在的路径。

import java.util.*;

public class DirectedGraph {
    private int V; // 顶点数
    private List<Integer>[] adj; // 邻接表

    public DirectedGraph(int V) {
        this.V = V;
        adj = new List[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
    }

    public void addEdge(int u, int v) {
        adj[u].add(v);
    }

    public List<Integer> findCycle() {
        boolean[] visited = new boolean[V];
        boolean[] onStack = new boolean[V];
        int[] edgeTo = new int[V];
        List<Integer> cycle = new ArrayList<>();

        // 从每个节点开始遍历图
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                if (dfs(i, visited, onStack, edgeTo, cycle)) {
                    // 找到了环
                    Collections.reverse(cycle);
                    cycle.add(cycle.get(0));
                    return cycle;
                }
            }
        }

        // 没有找到环
        return null;
    }

    private boolean dfs(int v, boolean[] visited, boolean[] onStack, int[] edgeTo, List<Integer> cycle) {
        visited[v] = true;
        onStack[v] = true;

        for (int w : adj[v]) {
            if (!visited[w]) {
                edgeTo[w] = v;
                if (dfs(w, visited, onStack, edgeTo, cycle)) {
                    return true;
                }
            } else if (onStack[w]) {
                // 找到了环
                for (int x = v; x != w; x = edgeTo[x]) {
                    cycle.add(x);
                }
                cycle.add(w);
                return true;
            }
        }

        onStack[v] = false;
        return false;
    }
}

使用方法：

DirectedGraph graph = new DirectedGraph(6);
graph.addEdge(0, 1);
graph.addEdge(1, 2);
graph.addEdge(2, 3);
graph.addEdge(3, 4);
graph.addEdge(4, 2);
graph.addEdge(4, 5);

List<Integer> cycle = graph.findCycle();

if (cycle != null) {
    System.out.println("Cycle found: " + cycle);
} else {
    System.out.println("No cycle found.");
}

输出：

Cycle found: [2, 3, 4, 2]

这里使用了一个基于栈的深度优先搜索算法。visited数组记录了每个节点是否被访问过，onStack数组记录了当前深度优先搜索树中是否存在该节点的祖先节点。如果在搜索过程中找到了一个已经被访问过且在当前栈中的节点，那么就找到了一个环。edgeTo数组记录了搜索树中每个节点的父节点，用于在找到环后回溯输出环所在的路径。