Topological sorting is possible for which class of graphs?
Topological sorting orders vertices linearly such that for every directed edge u -> v, u comes before v. This is strictly valid only for Directed Acyclic Graphs (DAGs).
What is the time complexity of Topological Sort on a DAG with V vertices and E edges using Kahn's algorithm (indegree-based)?
Kahn's algorithm initializes in-degrees in O(V + E), processes each vertex once, and decrements edge in-degrees in O(E), yielding O(V + E) total time.
Which algorithm is used to find the Minimum Spanning Tree (MST) of a connected, weighted, undirected graph by greedily picking the smallest edge that does not form a cycle?
Kruskal's algorithm sorts all edges by weight and repeatedly adds the lightest edge that does not create a cycle (using Disjoint Set Union / Find-Set).
What is the time complexity of Kruskal's algorithm on a graph with V vertices and E edges using Union-Find with path compression?
Sorting edges dominates Kruskal's time complexity, taking O(E log E). Since E <= $V^2$, log $E = O(log V)$, giving O(E log V).
Prim's algorithm for finding a Minimum Spanning Tree (MST) is most similar in structure to which single-source shortest path algorithm?
Both Prim's and Dijkstra's algorithms maintain a visited set and greedily select the minimum key/distance vertex using a Priority Queue.