3

Hereを指定して、Graph 内のすべての Articulation Points を見つけるために説明したアルゴリズムを実行していました。

これは、アート ポイントを計算する関数です。

// A recursive function that find articulation points using DFS traversal
// u --> The vertex to be visited next
// visited[] --> keeps tract of visited vertices
// disc[] --> Stores discovery times of visited vertices
// parent[] --> Stores parent vertices in DFS tree
// ap[] --> Store articulation points
void Graph::APUtil(int u, bool visited[], int disc[],
                                      int low[], int parent[], bool ap[])
{
    // A static variable is used for simplicity, we can avoid use of static
    // variable by passing a pointer.
    static int time = 0;

    // Count of children in DFS Tree
    int children = 0;

    // Mark the current node as visited
    visited[u] = true;

    // Initialize discovery time and low value
    disc[u] = low[u] = ++time;

    // Go through all vertices aadjacent to this
    list<int>::iterator i;
    for (i = adj[u].begin(); i != adj[u].end(); ++i)
    {
        int v = *i;  // v is current adjacent of u

        // If v is not visited yet, then make it a child of u
        // in DFS tree and recur for it
        if (!visited[v])
        {
            children++;
            parent[v] = u;
            APUtil(v, visited, disc, low, parent, ap);

            // Check if the subtree rooted with v has a connection to
            // one of the ancestors of u
            low[u]  = min(low[u], low[v]);

            // u is an articulation point in following cases

            // (1) u is root of DFS tree and has two or more chilren.
            if (parent[u] == NIL && children > 1)
               ap[u] = true;

            // (2) If u is not root and low value of one of its child is more
            // than discovery value of u.
            if (parent[u] != NIL && low[v] >= disc[u])
               ap[u] = true;
        }

        // Update low value of u for parent function calls.
        else if (v != parent[u])
            low[u]  = min(low[u], disc[v]);
    }
}

今、私はこのコードのいくつかの行を理解するのに少し苦労しています。

if (parent[u] != NIL && low[v] >= disc[u])
               ap[u] = true;

上記のステートメントは、頂点「v」が頂点「u」の直接の子であるため、「v」または「v」自体から到達可能な頂点があり、「u」の後に発見された場合、それは意味することを意味しますか?バックエッジが存在すること。

さて、もう一つの声明は、

else if (v != parent[u])
     low[u]  = min(low[u], disc[v]);

この声明は私を大いに混乱させます。混乱しているのは、なぜここにあるのか、他のステートメントと同様に、「low[v]」の代わりに「disc[v]」が使用されていることです。私が推測するのは、ここの 'v' は既に発見されているためです。ここで "low[v]" を使用することはできません。これは、'u' からバック エッジを検索する際に、'v' の後継者も考慮することを本質的に意味するためです。ここの DFS ツリーでは、'v' は 'u's child ではないため、これは間違っています。

私の説明は正しいですか？間違っていたら正しい説明をお願いします。

4

1 に答える 1

3

まず、関節点の意味に注目してみましょう。これは、それを取り除くとグラフが分割されることを意味します。

3 点を結んだ単純なグラフ: ABC

Bが関節点であることは明らかです。点 A からディープ ファースト サーチを行うと、ディスク [A] < ディスク [B] < ディスク [C] が得られます。

low[B] <= disk[C]。ポイント c が以前に訪れたポイントに到達するためのパス(親からのパスを含まない) がないため、ポイント B はアーティキュレーションです。

parent[u] != NIL から、前のポイントがないため、最初のポイントは例外であることがわかります。

于 2013-06-02T02:04:42.223 に答える