If you are unfamiliar with graphs, check out some of my earlier posts on them.
Resources:
 Video explanation of articulation points & bridges
 Video explanation and implementation for articulation points
 Video on bridges & blocks
 Articulation points implementation
 Bridges implementation
Takeaways:
 A component is a subgraph 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 cutedge.
 We can use depthfirst search (DFS) to find all the articulation points or bridges in a graph.

There are two rules for finding articulation points in undirected graphs:
 The root vertex in a graph is an articulation point if it has more than one child.
 Any other vertex
v
in the graph is an articulation point if it has a childu
that cannot reach any ancestors ofv
, without also visitingv
. This means that there is no backedge between
u
and any ancestor beforev
.
 This means that there is no backedge between

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 vertexy
it is connected to  we call this the lowlink value (y
is the lowlink vertex).  So during DFS, for every vertex
v
we visit we assign it an ID & a lowlink value. To start, we set both ID/lowlink 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/lowlink, then we will increment both by 1 for the next vertex).  For every vertex
u
, that is adjacent tov
, 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 lowlink 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 lowlink value of our adjacent vertexu
, thenv
is an articulation point. This is because it means
u
cannot reach one of it's ancestor vertices without also visiting/going viav
.
 This is because it means
 We maintain a discovery time (or ID) for each vertex

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 lowlink ofu
, 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 backedge present  and this means a bridge cannot exist
 A backedge means that a neighbour
w
ofu
could have an edge connecting tov
. Creating a cycle. Meaning ifedge(u,v)
is removed, thenu
still connects tov
viaedge(w,v)
.  If there is no backedge, or cycle, like described, then the ID of
v
will always be less than the lowlink ofu
if a bridge is present. And this means ifedge(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 isO(v)
. For an adjacency matrix, the time & space complexity would beO(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!
Top comments (0)