Graphs

Question 1

What is the difference between BFS and DFS?

Answer 1

BFS explores level by level (queue), DFS goes deep first (stack).

Question 2

What data structure is used for BFS?

Answer 2

Queue

Question 3

What data structure is used for DFS?

Answer 3

Stack (or recursion).

Question 4

What is Dijkstra’s algorithm used for?

Answer 4

Finds shortest path in weighted graphs (O(V + E log V)).

Question 5

What is the difference between Prim’s and Kruskal’s algorithms?

Answer 5

: Prim’s for dense graphs, Kruskal’s for sparse graphs (both find MST).

Question 6

What is a topological sort, and when is it used?

Answer 6

Orders tasks when some must be done before others.

Question 7

What is the Bellman-Ford algorithm, and how does it differ from Dijkstra’s?

Answer 7

Bellman-Ford works with negative weights.

Question 8

What is Floyd-Warshall used for?

Answer 8

Finds shortest paths between all nodes (O(n³)).

Question 9

How can we detect cycles in a graph?

Answer 9

Use DFS or Union-Find.

Question 10

What is the difference between an adjacency matrix and an adjacency list?

Answer 10

Matrix uses O(V²) space; List is O(V + E).