-3

グラフが隣接行列で実装されている深さ優先検索を示すコードのこの部分から、グラフにサイクルがあるかどうかを検出する方法

   // ------------------------------------------------------------
    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
4

1 に答える 1

1

グラフをたどっている間、すでに訪れたノードを探し続ける必要があります。すでにアクセスされているノードに遭遇した場合は、ループが見つかりました。訪問したノードを取得せずにトラバーサルが終了した場合、グラフにループはありません。実装に関しては、まず試してみてください。問題が発生した場合は、問題を解決してください。

于 2013-04-24T17:07:16.747 に答える