Q.1 Which of the following algorithms is commonly used to find a Minimum Spanning Tree?
Dijkstra’s algorithm
Prim’s algorithm
Floyd-Warshall algorithm
Bellman-Ford algorithm
Explanation - Prim’s algorithm is specifically designed to find the Minimum Spanning Tree of a weighted connected graph.
Correct answer is: Prim’s algorithm
Q.2 Kruskal’s algorithm is based on which approach?
Divide and Conquer
Greedy method
Dynamic Programming
Backtracking
Explanation - Kruskal’s algorithm selects the smallest edge at each step, a typical greedy approach.
Correct answer is: Greedy method
Q.3 What data structure is often used in Kruskal’s algorithm to detect cycles?
Stack
Queue
Union-Find (Disjoint Set)
Priority Queue
Explanation - Union-Find data structure is used in Kruskal’s algorithm to efficiently check for cycles when adding edges.
Correct answer is: Union-Find (Disjoint Set)
Q.4 The time complexity of Kruskal’s algorithm is mainly dominated by:
Sorting edges
Finding minimum edge
Updating adjacency list
Checking graph connectivity
Explanation - Kruskal’s algorithm requires sorting all edges, which dominates the runtime complexity O(E log E).
Correct answer is: Sorting edges
Q.5 Prim’s algorithm typically uses which data structure for efficient edge selection?
Stack
Heap/Priority Queue
Hash Table
Linked List
Explanation - A min-heap or priority queue is used in Prim’s algorithm to quickly select the smallest edge connecting the growing tree.
Correct answer is: Heap/Priority Queue
Q.6 Which of the following statements about MST is true?
MST contains cycles
MST has exactly (V-1) edges
MST has maximum weight
MST always includes all edges
Explanation - A spanning tree for a graph with V vertices always contains V-1 edges.
Correct answer is: MST has exactly (V-1) edges
Q.7 In Kruskal’s algorithm, if two edges have the same weight, what is the selection criteria?
Pick randomly
Pick edge with smaller vertices
Either can be picked
Pick based on DFS order
Explanation - If two edges have the same weight, either edge can be chosen as long as it does not form a cycle.
Correct answer is: Either can be picked
Q.8 What is the worst-case time complexity of Prim’s algorithm using adjacency matrix?
O(V^2)
O(E log V)
O(V log V)
O(E^2)
Explanation - When implemented with adjacency matrix, Prim’s algorithm has time complexity O(V^2).
Correct answer is: O(V^2)
Q.9 Which algorithm is more efficient for dense graphs in finding MST?
Kruskal’s
Prim’s (with adjacency matrix)
Floyd-Warshall
Bellman-Ford
Explanation - Prim’s algorithm with adjacency matrix performs better for dense graphs with many edges.
Correct answer is: Prim’s (with adjacency matrix)
Q.10 How many MSTs can a connected graph have?
Only 1
At most 2
Possibly multiple
None
Explanation - If edge weights are not unique, a graph can have multiple MSTs with the same total weight.
Correct answer is: Possibly multiple
Q.11 Which of the following problems can be solved using MST?
Shortest path
Network design
Traveling Salesman
Job Scheduling
Explanation - MST is commonly used in designing cost-effective network layouts such as telecommunication or road networks.
Correct answer is: Network design
Q.12 What does Kruskal’s algorithm do if adding an edge creates a cycle?
Keeps it
Removes cycle later
Ignores that edge
Restarts algorithm
Explanation - Kruskal’s algorithm discards edges that would create a cycle to maintain tree property.
Correct answer is: Ignores that edge
Q.13 In Prim’s algorithm, we always expand the tree from:
The largest weight edge
The smallest weight edge
A random vertex
Any leaf vertex
Explanation - Prim’s algorithm selects the minimum edge connecting a new vertex to the existing tree.
Correct answer is: The smallest weight edge
Q.14 The MST of a graph is unique if:
Graph is complete
All edge weights are distinct
Graph is sparse
Graph has Eulerian path
Explanation - When all edge weights are unique, the MST is guaranteed to be unique.
Correct answer is: All edge weights are distinct
Q.15 Which of the following is the output of Kruskal’s algorithm?
Shortest path
Minimum spanning tree
Maximum spanning tree
Topological ordering
Explanation - Kruskal’s algorithm specifically produces a Minimum Spanning Tree.
Correct answer is: Minimum spanning tree
Q.16 Which is faster for sparse graphs when implemented efficiently?
Prim’s with adjacency list + heap
Prim’s with adjacency matrix
Kruskal with union-find
Floyd-Warshall
Explanation - Kruskal’s algorithm with union-find is efficient for sparse graphs due to fewer edges.
Correct answer is: Kruskal with union-find
Q.17 What is the weight of MST of a graph?
Minimum possible weight of spanning trees
Maximum possible weight of spanning trees
Sum of all edges
Depends only on vertices
Explanation - By definition, MST has the least total edge weight among all spanning trees.
Correct answer is: Minimum possible weight of spanning trees
Q.18 If a graph has V vertices, how many edges will its spanning tree contain?
V
V+1
V-1
2V
Explanation - Every spanning tree contains exactly V-1 edges for V vertices.
Correct answer is: V-1
Q.19 Which algorithm uses edge-based greedy selection for MST?
Prim’s
Kruskal’s
Dijkstra’s
Warshall’s
Explanation - Kruskal’s algorithm sorts edges and picks the smallest non-cyclic edge at each step.
Correct answer is: Kruskal’s
Q.20 Which algorithm grows the MST one vertex at a time?
Kruskal’s
Prim’s
Bellman-Ford
Ford-Fulkerson
Explanation - Prim’s algorithm expands MST by adding the nearest vertex not yet in the tree.
Correct answer is: Prim’s
Q.21 In Kruskal’s algorithm, after sorting edges, how are they processed?
In increasing weight order
In decreasing weight order
Random order
By vertex number
Explanation - Edges are processed from smallest to largest weight in Kruskal’s algorithm.
Correct answer is: In increasing weight order
Q.22 Which graph property is necessary for MST to exist?
Graph must be connected
Graph must be directed
Graph must be acyclic
Graph must be complete
Explanation - A spanning tree only exists if the graph is connected.
Correct answer is: Graph must be connected
Q.23 What is the complexity of Kruskal’s algorithm using union-find with path compression?
O(E log V)
O(V^2)
O(EV)
O(E^2)
Explanation - Efficient union-find implementation gives Kruskal’s algorithm complexity O(E log V).
Correct answer is: O(E log V)
Q.24 Which of the following is NOT true about MST?
It connects all vertices
It minimizes total edge weight
It can contain cycles
It has V-1 edges
Explanation - MSTs are acyclic by definition since they are trees.
Correct answer is: It can contain cycles
Q.25 Which of the following is a real-world application of MST?
Building road networks
Sorting numbers
Data compression
CPU scheduling
Explanation - MST is used to design cost-efficient networks like roads, pipelines, or electrical wiring.
Correct answer is: Building road networks