Graph Algorithms Solved MCQs With Answers

By: Prof. Dr. Fazal Rehman | Last updated: May 2, 2025

1. How many vertices are there in a complete graph with n vertices?
(A) (n × (n – 1))⁄2
(B) (n × (n + 1))⁄2
(C) n + 1
(D) none of these

2. We use Dijkstra’s Algorithm to …
(A) non-weighted non-negative
(B) weighted non-negative
(C) weighted positive
(D) non-weighted positive

3. What is the total time bound of Prim’s algorithm?
(A) O(m + n log n)
(B) O(m log n)
(C) O(n log n)
(D) none of these

4. What will be the sum of degrees of all vertices in an undirected graph with n vertices and e edges?
(A) 2e
(B) 2ne
(C) ne
(D) none of these

5. Which data structure is used for implementing Dijkstra’s shortest path algorithm on an unweighted graph so that it runs linearly?
(A) tree
(B) queue
(C) stack
(D) heap

6. In a queue, which method is applied for storing data?
(A) LIFO
(B) FIFO
(C) both
(D) none of these

7. We use a circular linked list for stack as well as for …
(A) binary tree
(B) queue
(C) heap
(D) array

8. What is the minimum number of spanning trees in a connected graph?
(A) 1
(B) 2
(C) 3
(D) none of these

9. How does Quick Sort partition an array?
(A) double element
(B) pivot element
(C) couple element
(D) none of these

10. Why is graph traversal more difficult than tree traversal?
(A) because tree has root
(B) because tree is binary
(C) because tree is undefined
(D) all of these

11. Which of the following means computing the reachability of all the vertices?
(A) transitive hull
(B) safest path
(C) minimum distance
(D) maximum distance

12. An unweighted, connected or disconnected graph is a ____
(A) weighted graph
(B) unweighted graph
(C) simple graph
(D) none of these