• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.



Let G = (V, E) be a connected, undirected graph. An articulation point of G is a vertex whose removal disconnects G. A bridge of G is an edge whose removal disconnects G. A biconnected component of G is a maximal set of edges such that any two edges in the set lie on a common simple cycle. A simple cycle is a cycle with no repeated vertex.

The concept of Articulation Point is explained in the video below. Please excuse my speech impediment while watching the video. Thank you for your patience.

IMPORTANT ANNOUNCEMENT: For the most accurate code please see the code below, rather than looking at the code discussed in the video, as I have later found a bug in the code discussed in the video. Basically the constraints discussed for "parents" apply to all ancestors as well. The corrected version is posted in this chapter, please see the code below the video.



Pseudocode:


GetArticulationPoints(i, d)
    visited[i] := true
    depth[i] := d
    low[i] := d
    childCount := 0
    isArticulation := false

    for each ni in adj[i] do
        if not visited[ni] then
            parent[ni] := i
            GetArticulationPoints(ni, d + 1)
            childCount := childCount + 1
            if low[ni] ≥ depth[i] then
                isArticulation := true
            low[i] := Min (low[i], low[ni])
        else if ni ≠ parent[i] then
            low[i] := Min (low[i], depth[ni])
    if (parent[i] ≠ null and isArticulation) or (parent[i] = null and childCount > 1) then
        Output i as articulation point


Working Solution:


Java code:


This is a Premium content.
Please subscribe to Algorithms course to access the code.




Python code:


This is a Premium content.
Please subscribe to Algorithms course to access the code.





Time Complexity:

Same as the DFS we are doing to compute Articulation points: O(E + V), where E = total number of edges in the given connected undirected graph, and V = total number of vertices in the given connected undirected graph.

More on Tarjan's Algorithm:



The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave