GetArticulationPoints(i, d)
visited[i] := true
depth[i] := d
low[i] := d
childCount := 0
isArticulation := false
for each ni in adj[i] do
if not visited[ni] then
parent[ni] := i
GetArticulationPoints(ni, d + 1)
childCount := childCount + 1
if low[ni] ≥ depth[i] then
isArticulation := true
low[i] := Min (low[i], low[ni])
else if ni ≠ parent[i] then
low[i] := Min (low[i], depth[ni])
if (parent[i] ≠ null and isArticulation) or (parent[i] = null and childCount > 1) then
Output i as articulation point
In the algorithm if we find a back edge we minimize our low-time with low[i] := Min (low[i], depth[ni])
and not low[i] := Min (low[i], low[ni])
.
The explanation I've seen so far is that the back edge's low may be dependent on another node and when that node is removed we will no longer have access to it. My problem with this is the same can also happen with the child's low value. That value could be dependent on another node and when that node is removed we wont have access to it again.
Any better explanations to this? Why do we use two different minimization equations for the two kinds of edges?
I drew a graph and tried to see if the two equations make sense. I can't figure out why we use different equations for minimizing the low value of the different types of edges, because they can both be affected by removing some dependent node.