What is the time complexity of Kosaraju's algorithm for finding Strongly Connected Components (SCC) in a directed graph?
Kosaraju's algorithm uses 2 DFS passes (one on original graph, one on transposed graph), running in linear O(V + E) time.
Which of the following statements about testing whether a graph is bipartite are correct?
BFS or DFS can attempt a 2-coloring. A graph is bipartite iff it contains no odd cycle, and every edge must connect differently colored vertices. All three statements are correct.
How can you determine if a graph is Bipartite using Graph Traversal?
A graph is Bipartite if and only if it contains no odd-length cycles, verifiable using BFS 2-coloring in O(V + E) time.
Which statements about Prim's algorithm with a binary heap are correct for a connected graph?
With a binary heap, extract-min and decrease-key take O(log V). Across the graph this yields the standard O(E log V) bound for an adjacency-list implementation. All three statements are correct.
What is the time complexity of Prim's algorithm using a Binary Heap priority queue for a graph with V vertices and E edges?
Prim's algorithm with binary heap performs V extract-min operations O(V log V) and E key decreases O(E log V), yielding total time O(E log V).