java - 无向图中的环有什么性质？

Question

我试图理解这段用于检测循环的代码: http://algs4.cs.princeton.edu/41undirected/Cycle.java.html

因此，如果没有标记或找到顶点w，则继续运行dfs。如果找到并且它不等于 u...为什么我要在构造函数中传递 -1？

我对 else if (w != u) 感到困惑。为什么这会导致循环呢？

 public Cycle(Graph G) {
        if (hasSelfLoop(G)) return;
        if (hasParallelEdges(G)) return;
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];
        for (int v = 0; v < G.V(); v++)
            if (!marked[v])
                dfs(G, -1, v);
    }

private void dfs(Graph G, int u, int v) {
        marked[v] = true;
        for (int w : G.adj(v)) {

            // short circuit if cycle already found
            if (cycle != null) return;

            if (!marked[w]) {
                edgeTo[w] = v;
                dfs(G, v, w);
            }

            // check for cycle (but disregard reverse of edge leading to v)
            else if (w != u) {
                cycle = new Stack<Integer>();
                for (int x = v; x != w; x = edgeTo[x]) {
                    cycle.push(x);
                }
                cycle.push(w);
                cycle.push(v);
            }
        }
    }

Answer 1

该算法对图进行深度优先搜索，并标记遇到的任何顶点。使用先前访问的顶点 (u) 和当前访问的顶点 (v) 调用方法 dfs，其中 v 是 u 的后继者。如果 v 的下一个后继未标记 (if (!marked[w]))，则搜索将继续。否则我们发现了一个圆圈。

但是，如果存在双向的边，则此实现不会将其算作圆。 w 是 v 的邻居。如果它是 u 本身(v 的前身)，我们就会遇到这种情况。因此，代码检查情况是否不是(w != u)，即我们没有双向边，所以我们< em>确实找到了一个圆圈。