## DEV Community is a community of 891,187 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

JB

Posted on • Updated on

# Finding Articulation Points & Bridges in Undirected Graphs

If you are unfamiliar with graphs, check out some of my earlier posts on them.

## Resources:

Takeaways:

• A component is a sub-graph that is not connected to the rest of the graph.
• An articulation point is a vertex that when removed (along with it's edges) creates more components in the graph.
• Another name for articulation point is cut vertex.
• A bridge is an edge that when removed creates more components in the graph.
• Another name for a bridge is cut-edge.
• We can use depth-first search (DFS) to find all the articulation points or bridges in a graph.
• There are two rules for finding articulation points in undirected graphs:

1. The root vertex in a graph is an articulation point if it has more than one child.
2. Any other vertex `v` in the graph is an articulation point if it has a child `u` that cannot reach any ancestors of `v`, without also visiting `v`.
• This means that there is no back-edge between `u` and any ancestor before `v`.
• How do we apply DFS and follow the above two rules?

• We maintain a discovery time (or ID) for each vertex `v` in the graph. We also keep track of the earliest vertex `y` it is connected to - we call this the low-link value (`y` is the low-link vertex).
• So during DFS, for every vertex `v` we visit we assign it an ID & a low-link value. To start, we set both ID/low-link to be the same integer that we will increment by 1 each time we visit a new vertex. (For example: root vertex will get 0 assigned to it for ID/low-link, then we will increment both by 1 for the next vertex).
• For every vertex `u`, that is adjacent to `v`, we will recursively call our DFS routine.
• When our DFS finds no more adjacent vertices to visit, the stack begins to unwind. As it unwinds, we will update our low-link value for each adjacent vertex (to represent the earliest ancestor it is connected to).
• If we find that the ID (visited time) of the current vertex `v` is `<=` the low-link value of our adjacent vertex `u`, then `v` is an articulation point.
• This is because it means `u` cannot reach one of it's ancestor vertices without also visiting/going via `v`.
• Finding bridges is very similar to finding articulation points. The main changes to the algorithm are:

• We no longer need to keep track of how many children the root vertex has.
• Instead of checking if the ID of `v` is `<=` the low-link of `u`, we just check if it's `<`.
• We only check if it's less than, because if the values are the same then there is a back-edge present - and this means a bridge cannot exist
• A back-edge means that a neighbour `w` of `u` could have an edge connecting to `v`. Creating a cycle. Meaning if `edge(u,v)` is removed, then `u` still connects to `v` via `edge(w,v)`.
• If there is no back-edge, or cycle, like described, then the ID of `v` will always be less than the low-link of `u` if a bridge is present. And this means if `edge(u,v)` is removed, `u` and all it's adjacent vertices will become disconnected from the graph - forming another component (and increasing the number of components in the graph).
• Time complexity is `O(v + e)` for an adjacency list. Space complexity is `O(v)`. For an adjacency matrix, the time & space complexity would be `O(v^2)`.

• Below is an example of an undirected graph with articulation points and bridges: Below are implementations for finding articulation points & bridges in undirected adjacency list & adjacency matrix representations of graphs:

As always, if you found any errors in this post please let me know!