×

Search anything:

# Find cut edges in a graph

#### Graph Algorithms depth first search cut edges Get this book -> Problems on Array: For Interviews and Competitive Programming

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.