在定向图中查找所有周期，包括后边缘

Question

给定下面的图，找到从顶点1返回到1的所有可能路径，包括后边。

结果：

        [1,2,3,2,1]
        [1,2,1]
        [1,2,3,1]

我尝试使用 DFS 只能获得一个周期[1,2,3,2,1]。我不知道如何跟踪后边缘。

代码：

private static void dfsNow(Node vertex, HashMap<String, List<Node>> adjList,
                           HashSet<String> visited, HashSet<String> candidates,
                           ArrayList<String> res) {

    candidates.add(vertex.v);
    res.add(vertex.v);

    for(Node adj :  adjList.get(vertex.v)) {

        if(candidates.contains(adj.v)) {
           
            res.add(adj.v);
            System.out.println(vertex.v+":"+adj.v);
        } else {
            //adj.setParent(vertex); // build the trace back
            dfsNow( adj, adjList,visited,candidates,res);
        }
    }
    candidates.remove(vertex.v);
    visited.add(vertex.v);
}

Answer 1

你已经很接近答案了。

为了检测图形中的循环，您需要使用深度优先搜索算法。这是正确的。

但您的解决方案中有一些地方需要改进：

• 对于此任务，您不需要边缘。因为您可以仅使用顶点来建模有向图。当您处理加权图（即每条边都与一个值关联）并且需要解决例如使用 Dijkstra 或 Bellman-Ford 算法的最短路径问题时，边非常有用。那么你确实需要边来模拟顶点之间的连接。但在这个任务中，边是多余的，每个顶点都可以指向其他顶点。
• 邻接表不能是一个单独的数据结构。相反，每个顶点都必须了解其邻居。即每个顶点必须保存对相邻顶点集合的引用。
• 由于图可以包含多个循环，因此结果需要由嵌套集合表示。就像列表的列表List>。
• 对 List 进行 contains() 检查的成本非常高（O(n)在最坏的情况下），并且列表无法关联元素。 Map 是一个更好的选择，因为 Map 允许在恒定时间内检索值并将多个键与相同的值相关联（即一组顶点与单个顶点连接时的模型情况）。

请注意，循环[1,2,3,2,1]无效，因为有多个顶点被访问了两次。它是两个周期 1-2 和 2-3 的组合。如果您需要发现图表中的所有循环，则一次只能检测到一个循环，否则尝试恢复循环路径可能会失败，因为引用相互指向。只是因为您的解决方案只能跟踪单个路径，所以您不会在第二个循环 2->3->2 中遇到麻烦。即循环中的所有顶点（除了一个）必须是唯一的，这将允许维护多个路径。

在下面的实现中，我特意提供了一种能够检测包含特定顶点的循环的方法，以及一种获取仅包含唯一顶点的所有循环的方法。这样您就可以通过更改它们来进行尝试，并确保map永远不包含循环的最后一段。即只有条目 2->3 会被添加到映射中，但条目 3->2 不会，否则您可以创建无限循环。

下图的实现仅使用顶点。深度优先搜索算法以迭代方式实现（尽管递归实现更容易，但递归在 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);
    }
}

输出

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