java - 从图中检测循环

Question

如何从显示深度优先搜索的这部分代码中检测图是否具有循环，并且该图是在邻接矩阵中实现的

   // ------------------------------------------------------------
    public void dfs() // depth-first search
    { // begin at vertex 0
        int k = 0;
        vertexList[0].wasVisited = true; // mark it
        displayVertex(0); // display it
        theStack.push(0); // push it
        while (!theStack.isEmpty()) // until stack empty,
        {
            // get an unvisited vertex adjacent to stack top
            int v = getAdjUnvisitedVertex(theStack.peek());
            int x = nAdjVisitedVertex(v);

            if (v == -1) // if no such vertex,
                theStack.pop();
            else // if it exists,
            {
                vertexList[v].wasVisited = true; // mark it
                displayVertex(v); // display it
                if (x == 2)
                    k++;

                theStack.push(v); // push it

            }
        } // end while
            // stack is empty, so we’re done
        for (int j = 0; j < nVerts; j++)
            // reset flags
            vertexList[j].wasVisited = false;

        if(k != 0)
            System.out.println("not a cycle");
        else
            System.out.println("cycle");

    } // end dfs

Answer 1

在遍历图时，您需要继续寻找已经访问过的节点。如果你遇到一个已经被访问过的节点，你就发现了一个循环。如果遍历完成而没有得到任何访问节点，则图中没有循环。关于实施，请先尝试，如果您遇到任何问题，请返回问题。