|WikiProject Computer science||(Rated Start-class)|
|WikiProject Mathematics||(Rated Start-class, Mid-priority)|
"The key fact is that a nonroot vertex v is a cut vertex (or articulation point) separating two biconnected components if and only if v's lowpoint is at least as large as v's depth". This is not correct.
For instance if the depth-first-search tree is like:
T | x / \ A B
i.e, T is a tree, x is a node (not the root), A and B are subtrees.
If there is a backward edge from a node of A to a node of T, then lowpoint(x) < depth(x) so according to the previous characterization, x can not be a cut vertex. But if there is no backward edge from B to T then x is actually a cut vertex (removing x separate B from T) so the characterization is not correct.
I think it should be : "a non-root vertex x is a cut vertex iff there is no son y of x such that lowpoint(y) >= depth(x)".
The C++ example seems misleading and complex to me, although it directly translates the . What about a shorter recursive pseudocode like this:
mark_lowpoint(node, parent, depth) if not visited[node]: if parent = root: ++root_children visited[node] := true min_depth_lowpoints := depth for n in neighbours[node] l := mark_lowpoint(node, depth+1) if l >= depth and node != root: articulation_point[node] := true min_depth_lowpoints := min(l, min_depth_lowpoints) lowpoint[node] := min_depth_lowpoints; return lowpoint[node] root_children := 0 articulation_point := [false, ...] visited := [false, ...] mark_lowpoint(root, ..., 0) if root_children >= 2: articulation_point[root] := true