▲ | spankalee 4 days ago | |
Nice. I'm liking the interactive diagrams! I noticed another small error. Step 15 of the Tarjan's algorithm diagram reads: > Since low[6] > 4, the edge is a bridge. I think it should read: > Since low[6] > low[4], the edge is a bridge. | ||
▲ | emih 4 days ago | parent [-] | |
That one is intentional. Note: a tree edge (u, v) is a bridge if and only if low[v] is strictly greater than the entry time of u. Here 4 is the entry time of that node. (For convenience I made sure that the node labels are just the DFS entry times.) Though maybe comparing both low values might also work, I'd have to think about that... |