Bridges in Graph Tarjan's Algorithm in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a bridge in a graph?

A bridge is an edge in a graph that, if removed, increases the number of connected components. It means the edge is critical for keeping the graph connected.

intermediate

What is the main idea behind Tarjan's algorithm for finding bridges?

Tarjan's algorithm uses a depth-first search (DFS) to assign discovery times and low values to each vertex. An edge is a bridge if the low value of the connected vertex is greater than the discovery time of the current vertex.

intermediate

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

The 'low' value of a vertex is the earliest discovery time reachable from that vertex by following the DFS tree edges and at most one back edge.

intermediate

Why do we compare low[v] > disc[u] to find a bridge in Tarjan's algorithm?

If low[v] > disc[u], it means vertex v cannot reach any ancestor of u without using the edge (u, v). So, removing (u, v) disconnects the graph, making it a bridge.

beginner

What data structures are commonly used in Tarjan's algorithm for bridges?

Arrays or lists to store discovery times (disc), low values (low), a visited set or array, and adjacency lists to represent the graph.

What happens if you remove a bridge edge from a graph?

A The graph becomes a tree

B The graph remains connected

C The graph becomes disconnected

D The graph becomes cyclic

Removing a bridge edge increases the number of connected components, so the graph becomes disconnected.

In Tarjan's algorithm, what does the discovery time represent?

A The order in which vertices are visited in DFS

B The number of edges connected to a vertex

C The shortest distance from the start vertex

D The number of connected components

Discovery time is the time when a vertex is first visited during DFS.

Which condition identifies an edge (u, v) as a bridge in Tarjan's algorithm?

A low[v] > disc[u]

B low[u] > disc[v]

C disc[u] > disc[v]

D low[u] == low[v]

If low[v] > disc[u], edge (u, v) is a bridge.

What is the role of the 'low' array in Tarjan's algorithm?

A Marks visited vertices

B Tracks the earliest visited vertex reachable

C Stores the parent of each vertex

D Counts the number of edges

The 'low' array stores the earliest discovery time reachable from a vertex.

Which graph traversal method does Tarjan's algorithm use?

A Dijkstra's Algorithm

B Breadth-First Search (BFS)

C Prim's Algorithm

D Depth-First Search (DFS)

Tarjan's algorithm uses DFS to explore the graph.

Explain how Tarjan's algorithm finds bridges in a graph using discovery and low values.

Think about how DFS helps track back edges and earliest reachable ancestors.

Describe what a bridge is in a graph and why it is important to find them.

Consider bridges as critical connections that keep parts of the graph linked.