DFS Depth First Search on Graph in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind Depth First Search (DFS) on a graph?

DFS explores as far as possible along each branch before backtracking, visiting nodes deeply before moving to neighbors.

beginner

In DFS, what data structure is commonly used to keep track of nodes to visit next?

A stack is used, either explicitly or via recursion call stack, to remember nodes to visit next in DFS.

beginner

What is the purpose of a 'visited' set or array in DFS?

It prevents revisiting nodes, avoiding infinite loops and repeated work in graphs with cycles.

intermediate

How does DFS differ from Breadth First Search (BFS)?

DFS goes deep into a branch before backtracking, while BFS explores neighbors level by level.

intermediate

What is the time complexity of DFS on a graph with V vertices and E edges?

The time complexity is O(V + E) because each vertex and edge is visited once.

Which data structure is naturally used by DFS to remember nodes to visit?

A Hash Map

B Queue

C Stack

D Priority Queue

DFS uses a stack or recursion call stack to explore nodes deeply before backtracking.

What does DFS use to avoid visiting the same node multiple times?

A Visited set or array

B Priority queue

C Sorting nodes

D Random selection

A visited set or array keeps track of nodes already explored to prevent cycles.

What is the order of node visiting in DFS?

A Level by level

B Deep first, then backtrack

C Random order

D By node value

DFS explores as far as possible along a branch before backtracking.

What is the time complexity of DFS on a graph with V vertices and E edges?

A O(V + E)

B O(V^2)

C O(E^2)

D O(log V)

DFS visits each vertex and edge once, so time complexity is O(V + E).

Which traversal method explores neighbors level by level, unlike DFS?

A Dijkstra's Algorithm

B Depth First Search (DFS)

C Binary Search

D Breadth First Search (BFS)

BFS explores nodes level by level, while DFS goes deep first.

Explain how DFS works on a graph and why a visited set is important.

Think about how you explore a maze by going deep and marking visited paths.

Describe the difference between DFS and BFS in graph traversal.

Imagine exploring a tree by going down one branch fully vs exploring all neighbors first.