In a Depth-First Search (DFS) on a directed graph, an edge (u, v) is classified as a BACK EDGE if and only if:
A back edge connects vertex u to an ancestor v in the current DFS recursion stack. The presence of a back edge indicates a cycle in a directed graph.
Which graph traversal algorithm can be used to find the shortest path in an UNWEIGHTED graph from a single source vertex to all other vertices?
BFS explores vertices level by level in increasing distance order, guaranteeing shortest paths in terms of number of edges (unweighted graphs) in O(V + E) time.
Topological Sorting is possible if and only if the directed graph is:
Topological sorting orders vertices such that for every directed edge u -> v, u comes before v. This is possible if and only if the graph contains no directed cycles (DAG).
What is the time complexity of Kosaraju's algorithm for finding all Strongly Connected Components (SCCs) of a directed graph $G = (V, E)$?
Kosaraju's algorithm performs two DFS passes (one on G and one on the transpose graph $G^{T})$ and one stack operation, achieving linear time O(V + E).
In Tarjan's algorithm for Strongly Connected Components, what do low-link values (low[u]) represent?
In Tarjan's algorithm, low[u] is the lowest discovery time (disc[v]) reachable from u through its subtree in the DFS tree using at most one back edge.