DEV Community


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.


  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


  • 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!


Editor guide