This third Algorithms set covers the graph algorithms that appear in almost every interview and exam: traversals, topological sorting, single-source and all-pairs shortest paths, and minimum spanning trees. Several questions ask you to trace an algorithm on a small graph, so work them out on paper before checking the answer.
How to practise: read each question and tap the option you think is correct. You will see right away whether you got it, along with a short explanation, and your score is tracked at the bottom of the screen. This set has 15 questions.
Topics covered in this set
- BFS and DFS traversal order and complexity
- Cycle detection and topological sort
- Dijkstra and its limits with negative edges
- Bellman-Ford and Floyd-Warshall
- Kruskal, Prim and union-find
- Spanning tree properties and Cayley's formula
Algorithms MCQs with answers and explanations
Q1. Which data structure does breadth-first search (BFS) use to decide which vertex to visit next?
a) Priority queue
b) Hash table
c) Stack
d) Queue
Q2. What is the time complexity of DFS on a graph with V vertices and E edges stored as an adjacency list?
a) O(V × E)
b) O(E log V)
c) O(V + E)
d) O(V²)
Q3. An undirected graph has edges A–B, A–C, B–D, B–E, C–F and E–F. Starting at A and visiting neighbours in alphabetical order, what is the BFS order?
a) A, B, C, D, E, F
b) A, C, F, E, B, D
c) A, B, D, E, F, C
d) A, B, C, E, D, F
Q4. An undirected graph has edges A–B, A–C, B–D, B–E, C–F and E–F. Starting at A and visiting neighbours in alphabetical order, what is the DFS order?
a) A, C, F, E, B, D
b) A, B, E, F, C, D
c) A, B, C, D, E, F
d) A, B, D, E, F, C
Q5. In an unweighted graph, which algorithm finds the path with the fewest edges from a source vertex to every other vertex?
a) Prim's algorithm
b) Kruskal's algorithm
c) BFS
d) DFS
Q6. During DFS of a directed graph, finding a back edge (an edge to an ancestor that is still on the recursion stack) means that the graph:
a) Has a negative edge
b) Is a tree
c) Contains a cycle
d) Is disconnected
Q7. A directed graph has edges A→B, A→C, B→D and C→D. How many valid topological orderings does it have?
a) 1
b) 4
c) 2
d) 3
Q8. A directed graph has edges A→B (4), A→C (1), C→B (2), B→D (1), C→D (5) and D→E (3). What is the shortest distance from A to E found by Dijkstra's algorithm?
a) 9
b) 8
c) 10
d) 7
Q9. Why can Dijkstra's algorithm give wrong answers when a graph has negative edge weights?
a) It runs out of memory
b) It treats a vertex's distance as final once the vertex is removed from the priority queue, and a later negative edge could still reduce it
c) It cannot store negative numbers
d) It only works on undirected graphs
Q10. What is the time complexity of Bellman-Ford on a graph with V vertices and E edges?
a) O(E log V)
b) O(V × E)
c) O(V + E)
d) O(V³)
Q11. Which algorithm computes shortest paths between all pairs of vertices in O(V³) time using dynamic programming over intermediate vertices?
a) Dijkstra
b) Prim
c) Kahn's algorithm
d) Floyd-Warshall
Q12. An undirected graph has edges A–B (1), C–D (2), A–C (3), B–C (4), B–D (5), C–E (6) and D–E (7). What is the total weight of its minimum spanning tree?
a) 15
b) 12
c) 11
d) 13
Q13. Which data structure lets Kruskal's algorithm check quickly whether adding an edge would create a cycle?
a) Disjoint-set (union-find)
b) Binary search tree
c) Trie
d) Stack
Q14. According to Cayley's formula, how many distinct spanning trees does the complete graph K₄ have?
a) 8
b) 16
c) 4
d) 12
Q15. A connected undirected graph has 10 vertices and 15 edges. How many edges does any spanning tree of this graph contain?
a) 14
b) 15
c) 10
d) 9
Quick revision notes
- BFS uses a queue and gives shortest paths in unweighted graphs; DFS uses a stack or recursion. Both are O(V + E) with adjacency lists.
- A back edge in directed DFS means a cycle; topological order exists only for DAGs (Kahn's algorithm or reverse DFS finish order).
- Dijkstra: O((V + E) log V) with a binary heap, no negative edges. Bellman-Ford: O(VE), detects negative cycles.
- Floyd-Warshall: all pairs, O(V³), dynamic programming over intermediate vertices.
- MST: Kruskal (sort edges + union-find) and Prim (grow from a vertex with a priority queue); a spanning tree has n − 1 edges; Kₙ has n^(n−2) spanning trees.
Frequently asked questions
Should I use Dijkstra or Bellman-Ford?
Use Dijkstra when all edge weights are non-negative because it is much faster. Use Bellman-Ford when negative edges are possible or when you need to detect a negative cycle.
When is Prim's algorithm better than Kruskal's?
Prim with a heap suits dense graphs stored as adjacency lists or matrices, while Kruskal suits sparse graphs where sorting the edge list is cheap. Both give a minimum spanning tree.
How should I practise graph algorithm questions?
Draw small graphs and trace each algorithm by hand, writing down the queue, stack or distance table after every step. Most exam questions test exactly this tracing.
Comments
Post a Comment