Graphs: Representation and Traversals

Question 1

How can a graph be represented in memory?

Answer 1

Using adjacency lists (efficient for sparse graphs) or adjacency matrices (efficient for dense graphs).

Question 2

What is Breadth-First Search (BFS)?

Answer 2

Explores the graph level by level using a queue. Suitable for shortest path in unweighted graphs.

Question 3

What is Depth-First Search (DFS)?

Answer 3

Explores the graph deeply before backtracking, often implemented with recursion or a stack.

Question 4

What is the time complexity of BFS and DFS?

Answer 4

Both have O(V + E) time complexity for a graph with V vertices and E edges.

Question 5

What is a visited array used for in graph traversal?

Answer 5

To track already visited nodes and prevent infinite loops in cyclic graphs.