top | item 45335702 (no title) emih | 5 months ago Whoops, you got me. Fixed!At some point I relabeled the vertices to match the DFS order, but I must have forgotten to update this example. discuss order hn newest spankalee|5 months 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|5 months ago 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...
spankalee|5 months 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|5 months ago 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...
emih|5 months ago 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...
spankalee|5 months ago
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|5 months ago
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...