我正在通过解释的算法来查找图中的所有关节点,给定的Here。
这是计算艺术点的函数:
// 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]);
这句话让我很困惑。令人困惑的是,为什么在这里使用“disc[v]”而不是“low[v]”,就像其他陈述一样。我推断是因为这里的“v”已经被发现,我们不能在这里使用“low[v]”,因为这本质上意味着我们也考虑了“v”的后继者,在我们从“u”搜索后端时,这是错误的,因为'v'不会是'你在DFS树中的孩子。
我的解释正确吗?如果我错了,请给我正确的解释。