Finding Articulation Points & Bridges in Undirected Graphs
Tags: computerscience, algorithms, datastructures, csharp
Published: 2020-02-26 05:03:32

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

## Resources:

1. [Video explanation of articulation points & bridges](https://www.youtube.com/watch?v=aZXi1unBdJA)
1. [Video explanation and implementation for articulation points](https://www.youtube.com/watch?v=2kREIkF9UAs)
1. [Video on bridges & blocks](https://www.youtube.com/watch?v=iGsxKUzW3cs)
1. [Articulation points implementation](https://github.com/mission-peace/interview/blob/master/src/com/interview/graph/ArticulationPoint.java)
1. [Bridges implementation](https://github.com/williamfiset/Algorithms/blob/master/src/main/java/com/williamfiset/algorithms/graphtheory/BridgesAdjacencyList.java)

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.
   1. 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:

![Articulation points and bridgs](https://dev-to-uploads.s3.amazonaws.com/i/a2b6382pk7aeiuelnawo.jpg)

Below are implementations for finding articulation points & bridges in undirected adjacency list & adjacency matrix representations of graphs:

{% gist https://gist.github.com/jbolton209/a546aa5c0e2ebfb9bf1a86c7df73a007 %}

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