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

Recall & Review

beginner

What is Depth First Search (DFS) in graph traversal?

DFS is a method to explore a graph by starting at a node and exploring as far as possible along each branch before backtracking.

beginner

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

A stack is used to keep track of nodes to visit next, either explicitly or via recursion call stack.

beginner

Why do we mark nodes as visited in DFS?

Marking nodes as visited prevents revisiting the same node, avoiding infinite loops and repeated work.

intermediate

What is the order of node visits in DFS on a graph with nodes 1 connected to 2 and 3, and 2 connected to 4?

Starting at 1, DFS visits 1 → 2 → 4 → 3 (assuming neighbors are visited in numerical order).

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 recursive DFS?

A Heap

B Queue

C Stack

D Hash Table

Recursive DFS uses the call stack to keep track of nodes, which behaves like a stack.

What happens if you do not mark nodes as visited in DFS on a graph with cycles?

A DFS will terminate normally

B DFS will skip some nodes

C DFS will visit nodes in breadth order

D DFS may enter an infinite loop

Without marking visited nodes, DFS can revisit nodes endlessly in cycles, causing infinite loops.

In DFS, when do you backtrack?

A When all nodes are visited

B When no unvisited neighbors remain

C Before visiting any neighbor

D After visiting the first neighbor

Backtracking happens when the current node has no unvisited neighbors left to explore.

What is the first node visited in DFS starting from node 1 in a graph?

A Node 1

B Node 2

C Node 0

D Node with highest degree

DFS starts at the given start node, here node 1.

Which of these is NOT a use case of DFS?

A Finding shortest path in unweighted graph

B Finding connected components

C Topological sorting

D Detecting cycles

Shortest path in unweighted graphs is better found by BFS, not DFS.

Explain how DFS explores a graph starting from a node. Include how it uses the stack and visited nodes.

Think about going deep first before going wide.

Describe the time complexity of DFS and why it is O(V + E) for a graph with V vertices and E edges.

Consider how many times nodes and edges are processed.