Java 查找有向图中的所有循环，包括后边

你已经接近答案了.

为了在图形中显示detect a cycle，需要使用Depth first search算法.没错.

但您的解决方案中有几点需要改进:

• 对于这个任务，你不需要edges.因为你只能用vertices来模拟directed graph.Edges在处理加权图(即每条边都与一个值相关联)时非常有用，例如，需要使用Dijkstra或Bellman–Ford算法解决最短路径问题.然后你真的需要边来模拟顶点之间的连接.但在这个任务中，边是多余的，每一条vertex can point to other vertexes.
• Adjacency list不能是单独的数据 struct .相反，每个vertex必须知道它的neighbors.也就是说，每个vertex必须包含对adjacent vertices集合的引用.
• 由于graph可以包含multiple cycles，因此结果需要用嵌套集合表示.比如 list List<List<Vertex>>.
• 在List上进行contains()次判断是非常昂贵的(O(n) in the worse case)，而且列表无法关联元素.Map是一个更好的 Select ，因为map允许在恒定时间内检索值，并将多个关键点与相同的值关联(即，当一组顶点与单个顶点连接时的模型情况).

注意，循环[1,2,3,2,1]是无效的，因为有more than one vertex是visited twice.这是两个循环1-2和2-3的组合.如果需要找出图形中的所有循环，则一次只能检测一个循环，否则try 恢复循环路径可能会失败，因为引用彼此指向一个循环.只是因为在您的解决方案中，只能跟踪一条路径，所以第二个循环2->3->2没有遇到问题.也就是说，一个循环中的所有顶点(except one)必须是唯一的，这将允许维护多条路径.

在下面的实现中，我特意提供了一种能够检测包含特定顶点的循环的方法，以及一种获取所有循环的方法.这样你就可以通过改变它们来进行游戏，并确保map不应该包含循环的最后一段.也就是说，只有条目2->3会被添加到 map 中，但条目3->2不会，否则您可以创建一个无限循环.

下图的实现只使用了vertexes.深度优先搜索算法是iteratively实现的(尽管递归实现更容易，但递归在Java中有局限性，尤其是在处理大型数据集时，迭代方法更有效).

public class CyclicGraph {
    private Map<Integer, Vertex> vertexById = new HashMap<>();
    
    public void addVertex(int vertexId, int... neighbours) {
//        vertexById.putIfAbsent(vertexId, new Vertex(vertexId));
//        Vertex current = vertexById.get(vertexId); // does the same as the line below with one important distinction - new Vertex will be instantiated by `computeIfAbsent` only entry is not present
        Vertex current = vertexById.computeIfAbsent(vertexId, Vertex::new); // adding a vertex
        
        for (int next : neighbours) {
            Vertex neighbour = vertexById.computeIfAbsent(next, Vertex::new); // retrieving neighbour
            current.addNeighbour(neighbour);                                  // adding neighbour
        }
    }
    
    public List<List<Vertex>> getCyclesContainingVertex(int targetId) {
        Vertex target = vertexById.get(targetId);
        
        if (vertexById.get(targetId) == null) {
            return Collections.emptyList();
        }
        List<List<Vertex>> cycles = new ArrayList<>();
        
        Deque<Vertex> stack = new ArrayDeque<>();
        Set<Vertex> seen = new HashSet<>();
        Map<Vertex, Vertex> paths = new HashMap<>();
        
        stack.add(target);
        while (!stack.isEmpty()) {
            Vertex current = stack.pop();
            seen.add(current);
            for (Vertex neighbour : current.getNeighbours()) {
                if (seen.contains(neighbour) && neighbour.equals(target)) { // the cycle was found
                    // build cycle, don't add vertex to the stack and don't add new entry to the paths (it can prevent other cycles containing neighbour vertex from being detected)
                    cycles.add(buildCycle(paths, neighbour, current));
                } else if (!seen.contains(neighbour)) {
                    stack.add(neighbour);
                    paths.put(neighbour, current);
                    seen.add(neighbour);
                }
            }
        }
        return cycles;
    }
    
    public List<List<Vertex>> getAllCycles() {
        List<List<Vertex>> cycles = new ArrayList<>();
        Deque<Vertex> stack = new ArrayDeque<>();
        Set<Vertex> seen = new HashSet<>();
        
        for (Vertex next : vertexById.values()) {
            if (seen.contains(next)) continue;
            
            Map<Vertex, Vertex> paths = new HashMap<>();
            stack.add(next);
            while (!stack.isEmpty()) {
                Vertex current = stack.pop();
                seen.add(current);
                for (Vertex neighbour : current.getNeighbours()) {
                    if (seen.contains(neighbour)) { // the cycle was found
                        // build cycle, don't add vertex to the stack and don't add new entry to the paths (it can prevent other cycles containing neighbour vertex from being detected)
                        cycles.add(buildCycle(paths, neighbour, current));
                    } else {
                        stack.add(neighbour);
                        paths.put(neighbour, current);
                        seen.add(neighbour);
                    }
                }
            }
        }
        return cycles;
    }
    
    private List<Vertex> buildCycle(Map<Vertex, Vertex> paths, Vertex start, Vertex end) {
        Deque<Vertex> cycle = new ArrayDeque<>();
        Vertex current = end;
        while (current != null && !current.equals(start)) {
            cycle.addFirst(current);
            current = paths.get(current);
        }
        cycle.addFirst(start);
        return new ArrayList<>(cycle);
    }
    
    public void clear() {
        this.vertexById.clear();
    }
    
    private class Vertex {
        private int id;
        private Set<Vertex> neighbours = new HashSet<>();
        
        public Vertex(int id) {
            this.id = id;
        }
        
        public boolean addNeighbour(Vertex vert) {
            return neighbours.add(vert);
        }
        
        // getters, hashCode/equeals, toString()
    }
}

演示中使用的一个更复杂的图形示例，以及问题中提供的图形.

main()-演示

public static void main(String[] args) {
    CyclicGraph graph = new CyclicGraph();
    
    System.out.println("Graph described in the question (only cycles that include vertex 1):");
    graph.addVertex(1, 2);
    graph.addVertex(2, 1, 3);
    graph.addVertex(3, 1, 2);

    for (List<Vertex> cycle : graph.getCyclesContainingVertex(1)) {
        System.out.println(cycle);
    }
    
    graph.clear();
    System.out.println("\nMore elaborate Graph (all cycles):");
    
    graph.addVertex(1, 2);
    graph.addVertex(2, 1, 5);
    graph.addVertex(3, 1, 2);
    graph.addVertex(4, 1, 3);
    graph.addVertex(5, 3, 4);
    
    for (List<Vertex> cycle : graph.getAllCycles()) {
        System.out.println(cycle);
    }
}

Output

Graph described in the question (cycles that lead to 1):
[Vertex{ 1 }, Vertex{ 2 }] // 1 is reachable from 2
[Vertex{ 1 }, Vertex{ 2 }, Vertex{ 3 }] // 1 is reachable from 3

More elaborate Graph (all cycles):
[Vertex{ 1 }, Vertex{ 2 }] // 1 is reachable from 2
[Vertex{ 2 }, Vertex{ 5 }, Vertex{ 3 }] // 2 is reachable from 3
[Vertex{ 1 }, Vertex{ 2 }, Vertex{ 5 }, Vertex{ 3 }] // 1 is reachable from 3
[Vertex{ 3 }, Vertex{ 1 }, Vertex{ 2 }, Vertex{ 5 }, Vertex{ 4 }] // 3 is reachable from 4
[Vertex{ 1 }, Vertex{ 2 }, Vertex{ 5 }, Vertex{ 4 }] // 1 is reachable from 4