Finding Articulation Points & Bridges in Undirected Graphs

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

Resources:

1. Video explanation of articulation points & bridges
2. Video explanation and implementation for articulation points
3. Video on bridges & blocks
4. Articulation points implementation
5. Bridges implementation

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!