Reading time: 15 minutes | Coding time: 12 minutes
A cut edge
e = uv is an edge whose removal disconnects
Clearly such edges can be found in
O(m^2) time by trying to remove all edges in the graph. We can get to
O(m) based on the following two observations:
- All cut edges must belong to the DFS tree.
- A tree edge
v’s parent is a cut edge if and only if there are no edges in
v’s subtree that goes to
We need compute for each subtree, the lowest node in the DFS tree that a back edge can reach. This value can either be the depth of the other end point, or the discovery time. Hint: Depth First Search
- Worst case time complexity:
- Average case time complexity:
- Best case time complexity:
- Space complexity:
h[root] = 0 par[v] = -1 dfs (v): d[v] = h[v] color[v] = gray for u in adj[v]: if color[u] == white then par[u] = v and dfs(u) and d[v] = min(d[v], d[u]) if d[u] > h[v] then the edge v-u is a cut edge else if u != par[v]) then d[v] = min(d[v], h[u]) color[v] = black
where h[v] = height of vertex v in the DFS tree and d[v] = min(h[w] where there is at least vertex u in subtree of v in the DFS tree where there is an edge between u and w).
Cut edge denotes a critical edge that when removed, splits the graph into two components. It has real-world applications in the relation that cut edges may denote roads that need regular maintainence to ensure smooth traffic flow within an area.
Cut edges can, also, be seen as edges that needs to be removed to end up with strongly connected components.