# Find cut edges in a graph

#### graph algorithm depth first search cut edges

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:

1. All cut edges must belong to the DFS tree.
2. A tree edge uv with u as v’s parent is a cut edge if and only if there are no edges in v’s subtree that goes to u 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
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).

### Applications

• 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. #### Alexa Ryder

Hi, I am creating the perfect textual information customized for learning. Message me for anything.