Logic behind Tarjan's Algorithm for finding articulating points

68 views Asked by At
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?

fig 1

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.

0

There are 0 answers