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 ではないため、これは間違っています。
私の説明は正しいですか？間違っていたら正しい説明をお願いします。