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

Question

给定下面的图，找到从顶点

返回到

（包括后边缘）的所有可能路径。

结果：

        [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 算法的最短路径问题时，Edges 非常有用。那么你确实需要边来模拟顶点之间的连接。但在这个任务中，边是多余的，每个顶点可以指向其他顶点。
邻接表不能是一个单独的数据结构。相反，每个顶点都必须知道它的邻居。 IE。每个顶点必须保存对相邻顶点集合的引用。
由于graph可以包含多个循环，因此结果需要用嵌套集合来表示。喜欢列表的列表
```
List<List<Vertex>>
```
。
contains()
```
 进行的 
```
```
List
```
检查成本非常高（O(n) 在最坏的情况下），并且列表无法关联元素。
```
Map
```
是一个更好的选择，因为映射允许在恒定时间内检索值并将多个键与相同的值关联起来（即一组顶点与单个顶点连接时的模型情况）。

请注意，循环

[1,2,3,2,1]

无效，因为有 多个顶点 被 访问了两次 。它是两个周期

1-2

和

2-3

的组合。如果您需要发现图表中的所有循环，则一次只能检测到一个循环，否则尝试恢复循环路径可能会失败，因为引用相互指向。只是因为您的解决方案只能跟踪单个路径，所以您在第二个周期中没有遇到麻烦

2->3->2

。 IE。循环中的所有顶点（除了一个）必须是唯一的，这将允许维护多个路径。

在下面的实现中，我特意提供了一种能够检测包含特定顶点的循环的方法，以及一种获取所有循环仅包含唯一顶点的方法。这样您就可以通过更改它们来进行操作，并确保 map 永远不包含循环的最后一段。 IE。只有条目

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

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

问题描述投票：0回答：1

1个回答

最新问题

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

问题描述 投票：0回答：1

1个回答

最新问题

问题描述投票：0回答：1