Bridges in Graph Tarjan's Algorithm in DSA Typescript - 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 or its descendants by following zero or more tree edges and then possibly one back edge.

advanced

Why do we compare low[v] > disc[u] to find a bridge between u and v?

If low[v] > disc[u], it means vertex v and its descendants 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 is the time complexity of Tarjan's algorithm for finding bridges?

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

What does a bridge in a graph do?

A Connects two disconnected graphs

B Decreases the number of connected components if removed

C Has no effect on connectivity

D Increases the number of connected components if removed

A bridge is an edge that, when removed, increases the number of connected components.

In Tarjan's algorithm, what is the purpose of the discovery time array?

A To count the number of edges

B To store the degree of each vertex

C To store the order in which vertices are visited in DFS

D To mark visited vertices

Discovery time records the order in which vertices are first visited during DFS.

What does it mean if low[v] <= disc[u] in Tarjan's algorithm?

A Edge (u, v) is not a bridge

B Edge (u, v) is a bridge

C Vertex v is not reachable

D Vertex u is a leaf

If low[v] <= disc[u], it means v or its descendants can reach u or its ancestors, so (u, v) is not a bridge.

Which traversal method does Tarjan's algorithm use?

A Depth-first search

B Dijkstra's algorithm

C Breadth-first search

D Prim's algorithm

Tarjan's algorithm uses depth-first search to explore the graph.

What is the time complexity of Tarjan's algorithm for bridges?

A O(E^2)

B O(V + E)

C O(V^2)

D O(log V)

Tarjan's algorithm runs in linear time relative to vertices and edges, O(V + E).

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 why an edge is considered a bridge in terms of graph connectivity and Tarjan's algorithm.

Focus on the meaning of low and discovery times in connectivity.