Articulation Points in Graph in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is an articulation point in a graph?

An articulation point is a vertex in a graph that, if removed along with its edges, increases the number of connected components. It is also called a cut vertex.

intermediate

Which algorithm is commonly used to find articulation points in a graph?

Tarjan's algorithm using DFS (Depth First Search) with discovery and low time arrays is commonly used to find articulation points efficiently.

intermediate

In Tarjan's algorithm, what does the 'low' value represent for a vertex?

The 'low' value of a vertex is the earliest discovery time reachable from that vertex or its descendants by following back edges.

intermediate

Why is the root of DFS tree an articulation point only if it has more than one child?

Because if the root has more than one child, removing it disconnects those children subtrees, increasing connected components. If it has one or zero children, removal does not disconnect the graph.

intermediate

What is the time complexity of finding articulation points using Tarjan's algorithm?

The time complexity is O(V + E), where V is the number of vertices and E is the number of edges, because it uses a single DFS traversal.

What happens if you remove an articulation point from a connected graph?

A The graph becomes a tree

B The graph remains connected

C The graph becomes disconnected or increases connected components

D Nothing changes

Removing an articulation point increases the number of connected components, disconnecting the graph.

In Tarjan's algorithm, which data structure is primarily used to explore the graph?

A Queue

B Depth First Search (DFS) recursion

C Breadth First Search (BFS)

D Stack

Tarjan's algorithm uses DFS recursion to explore vertices and compute discovery and low values.

What does a 'back edge' in DFS indicate?

A An edge to a child vertex

B An edge that forms a cycle with the root only

C An edge to a disconnected vertex

D An edge to a previously visited ancestor vertex

A back edge connects a vertex to an ancestor in the DFS tree, indicating a cycle.

Which condition identifies a vertex u as an articulation point when u is not the root?

A If low[v] >= disc[u] for any child v of u

B If disc[u] > low[v] for any child v of u

C If u has no children

D If u is connected to all vertices

If for any child v of u, low[v] >= disc[u], u is an articulation point because v or its descendants cannot reach an ancestor of u.

What is the initial value of discovery time for all vertices before DFS starts?

A -1 or undefined

B Infinity

C 0

D 1

Discovery times are initialized as -1 or undefined to mark unvisited vertices before DFS.

Explain how Tarjan's algorithm finds articulation points in a graph using DFS.

Think about how discovery and low values help detect if a vertex connects different parts of the graph.

Describe why the root of the DFS tree is treated differently when identifying articulation points.

Consider how removing the root affects connectivity compared to other vertices.