Graph Quiz

Which of the following is used to represent a graph efficiently when the graph is sparse?

• Adjacency Matrix

• Adjacency List

• Edge List

• Incidence Matrix

Which traversal technique uses a queue?

• DFS

• BFS

• Dijkstra’s

• Kruskal’s

Which of these algorithms is used to find the shortest path from a single source to all vertices?

• Prim’s

• Kruskal’s

• Dijkstra’s

• DFS

What data structure is used in DFS?

• Queue

• Stack

• Heap

• Priority Queue

Which algorithm is used for topological sorting?

• BFS

• DFS

• Kruskal

• Either BFS or DFS

Answer explanation

Topological sorting is applicable only to Directed Acyclic Graphs (DAGs), and both DFS and BFS can be used to perform it, but with different approaches.

🔹 1. Using DFS (Depth-First Search):

• This is the most common method.

• Perform DFS traversal and push each node onto a stack after visiting all its neighbors.

• Once all nodes are visited, pop from the stack to get the topological order.
  
  2. Using BFS (Kahn’s Algorithm):

  • BFS-based method using in-degrees of nodes.

  • Start with nodes having in-degree = 0, and repeatedly remove them while updating in-degrees of neighbors.

  • Works well for cycle detection too (if not all nodes are sorted, a cycle exists).

  ✅ Steps:

  1. Calculate in-degrees.

  2. Enqueue all nodes with in-degree 0.

  3. While queue is not empty:

     • Dequeue node and add it to result.

     • Decrease in-degree of its neighbors.

     • If in-degree of neighbor becomes 0, enqueue it.

What is the main difference between Kruskal’s and Prim’s algorithm?

• Prim’s uses greedy approach, Kruskal doesn’t

• Kruskal works on connected graphs only

• Kruskal selects edges globally, Prim’s grows from a node

• Prim’s is slower than Kruskal

Which of the following best describes the output of a topological sort?

• All edges in minimum weight

• Nodes in a linear order with all dependencies resolved

• Shortest paths from a single node

• All cycles in a graph

Explain when BFS and DFS would visit the same nodes in the same order.

Answer explanation

Sample answer:
In a graph that forms a linear chain (like a linked list), both BFS and DFS may visit nodes in the same order.

What condition must be true for topological sort to be valid on a graph?

Why do we use a priority queue in Dijkstra’s algorithm?

Answer explanation

To efficiently select the vertex with the smallest tentative distance at each step.