使用Java进行图形环检测

Question

我正在研究有向无环图中的循环检测，并使用DFS实现了我的算法，以下是代码：

public class DFS {

    public static boolean hasCycle(Graph graph) {

        for (Vertex vertex : graph.getVertices()) {
            if (detectCycle(graph, vertex)) {
                return true;
            }
        }

        return false;

    }

    private static boolean detectCycle(Graph graph, Vertex root) {

        for (Vertex vertex : graph.getVertices()) {
            vertex.setBeingVisited(false);
            vertex.setVisited(false);
        }

        return DFS.dfs(graph, root);

    }

    private static boolean dfs(Graph graph, Vertex root) {
        root.setBeingVisited(true);

        for (Edge edge : root.getNeighbors()) {
            Vertex neighborVertex = edge.getEndPoint();
            if (neighborVertex.isBeingVisited()) {
                return true;
            } else if (!neighborVertex.isVisited()) {
                DFS.dfs(graph, neighborVertex);
            }
        }

        root.setVisited(true);
        root.setBeingVisited(false);
        return false;

    }

}

以下是测试类：

public class App {

    public static void main(String[] args) {
        Vertex a = new Vertex("A");
        Vertex b = new Vertex("B");
        Vertex c = new Vertex("C");
        Vertex d = new Vertex("D");
        Vertex e = new Vertex("E");

        Edge e1 = new Edge(a, b);
        Edge e2 = new Edge(a, c);
        a.addNeighbor(e1);
        a.addNeighbor(e2);

        Edge e3 = new Edge(b, d);
        b.addNeighbor(e3);

        Edge e4 = new Edge(c, e);
        c.addNeighbor(e4);

        Edge e5 = new Edge(d, a);
        d.addNeighbor(e5);

        List<Vertex> vertices = new ArrayList<>();
        vertices.add(a);
        vertices.add(b);
        vertices.add(c);
        vertices.add(d);
        vertices.add(e);

        Graph graph = new Graph(vertices);
        System.out.println(DFS.hasCycle(graph));
        if (DFS.hasCycle(graph)) {
            System.out.println("It does have a cycle!");
        } else {
            System.out.println("It doesn't have cycle!");
        }

    }

}

针对这个特定案例，结果应该打印出图形具有循环的信息，因为我们要处理的图形如下：

   >b --> d
  /       |
 a<-------
  \
   > c --> e

但是我的输出是错误的，就好像没有循环一样，我只是找不到我的实现中的错误。有人能帮忙吗？

- Pj-

Answer 1

你忽略了这行的目的：

DFS.dfs(graph, neighborVertex);

如果这个调用返回 true，那么该方法也应该返回 true。 编辑：应该像这样：

private static boolean dfs(Graph graph, Vertex root) {
    root.setBeingVisited(true);

    for (Edge edge : root.getNeighbors()) {
        Vertex neighborVertex = edge.getEndPoint();
        if (neighborVertex.isBeingVisited()) {
            return true;
        } else if (!neighborVertex.isVisited() && DFS.dfs(graph, neighborVertex)) {
            return true;
        }
    }

    root.setVisited(true);
    root.setBeingVisited(false);
    return false;
}

- ram

---

更改为 'if (neighborVertex.isBeingVisited()) { return true; } if (!neighborVertex.isVisited()) { return DFS.dfs(graph, neighborVertex); }' 使其正常工作！谢谢！！ - Pj-

@Pj- 实际上这并不正确，尽管它可能适用于您特定的示例。如果直接返回dfs返回的内容，则不会更新root的beingVisited和visited属性，这将导致其失败：一个简单的失败示例是a->b->c，并按顺序处理(b, a, c)：它将说它有循环。请正确阅读我的答案：仅当DFS.dfs(graph, neighborVertex)返回true时才返回true。如果为false，则继续处理其他邻居。我希望现在清楚了。 - ram

哦，对不起，您是说应该像这样：'if (!neighborVertex.isVisited()) { if (DFS.dfs(graph, neighborVertex)) { return true; } else { DFS.dfs(graph, neighborVertex); } }'？ - Pj-