Find cut edges in a graph
Sign up for FREE 1 month of Kindle and read all our books for free.
Get FREE domain for 1st year and build your brand new site
Reading time: 15 minutes  Coding time: 12 minutes
A cut edge e = uv
is an edge whose removal disconnects u
from v
.
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
uv
withu
asv
βs parent is a cut edge if and only if there are no edges inv
βs subtree that goes tou
or higher.
Strategy
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
Complexity
 Worst case time complexity:
Ξ(V+E)
 Average case time complexity:
Ξ(V+E)
 Best case time complexity:
Ξ(V+E)
 Space complexity:
Ξ(V)
Pseudocode
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 vu 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).
Applications

Cut edge denotes a critical edge that when removed, splits the graph into two components. It has realworld 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.