loading...

Finding Articulation Points & Bridges in Undirected Graphs

jjb profile image JB Updated on ・3 min read

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:

Articulation points and bridgs

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!

Posted on by:

Discussion

pic
Editor guide