Neural Sync Active

Week 9: Depth-First Search (DFS)

Registry Synced

Week 9: Depth-First Search (DFS)

1734 words

9 min read

Reading compass

Now · 1. Motivation: Exploring a Graph

Week 9: Depth-First Search (DFS)

BSCS1001 — IIT Madras BS Degree Prerequisite: Topic 15 (Recursion), Week 7 (Graphs) Cross-links: BSCS2002-PDSA (Week 8 — DFS)

1. Motivation: Exploring a Graph

You're at a station in a train network. You want to find all stations you can reach (the connected component). How do you explore systematically without getting lost? Depth-First Search (DFS) is the strategy:

Go to a neighboring station
From there, go to another neighbor (deeper)
When you can't go deeper, backtrack and try a different neighbor

Real-world analogy: Exploring a maze by always turning right. You go as deep as possible, then backtrack when you hit a dead end.

2. What is DFS?

DFS is a graph traversal algorithm that explores as far as possible along each branch before backtracking. (Diagram)

Key Features

Feature	Description
Recursive	Naturally expressed as a recursive procedure
Visited tracking	Must remember which nodes we've seen (to avoid cycles)
Backtracking	When no unvisited neighbors, return to previous node
Complete	Visits all reachable nodes

3. DFS Algorithm

Pseudocode


pseudo
Procedure DFS(graph, visited, i)
    // Mark current node as visited
    visited[i] = True
    // Explore all neighbors
    foreach j in columns(graph) {
        if (graph[i][j] == 1 AND not(isKey(visited, j))) {
            visited = DFS(graph, visited, j)
        }
    }
    return(visited)
End DFS

How to Use It


sql
// Initialize
visited = {}
// Start DFS from node 4
visited = DFS(graph, visited, 4)
// keys(visited) contains all nodes reachable from node 4
// If keys(visited) includes all nodes, the graph is connected

The Visited Dictionary

The visited dictionary tracks which nodes have been explored:

Key: Node index
Value: True (visited) Before DFS: visited = {} After DFS from node 4: visited = {4: True, 1: True, 2: True, ...}

4. DFS Tracing Example

Graph

(Diagram)

Adjacency Matrix


pseudo
        0  1  2  3  4  5  6  7  8  9  10
    0  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    1  [0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0]
    2  [0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0]
    3  [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    4  [0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0]
    5  [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
    6  [0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0]
    7  [0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0]
    8  [0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0]
    9  [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1]
    10 [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]

DFS Call Sequence

Starting from node 4:

Step	Current Node	Action	visited After
1	4	Visit 4, check neighbors	`{4: T}`
2	4→1	Neighbor 1 unvisited → recurse	`{4: T, 1: T}`
3	1→2	Neighbor 2 unvisited → recurse	`{4: T, 1: T, 2: T}`
4	2→5	Neighbor 5 unvisited → recurse	`{..., 5: T}`
5	5	No unvisited neighbors → backtrack to 2	`{...}`
6	2	No more unvisited neighbors → backtrack to 1	`{...}`
7	1→3	Neighbor 3 unvisited → recurse	`{..., 3: T}`
8	3	No unvisited neighbors → backtrack to 1	`{...}`
9	1	No more neighbors → backtrack to 4	`{...}`
10	4→6	Neighbor 6 unvisited → recurse	`{..., 6: T}`
11	6→7	Neighbor 7 → recurse	`{..., 7: T}`
12	7→8	Neighbor 8 → recurse	`{..., 8: T}`
13	8→9	Neighbor 9 → recurse	`{..., 9: T}`
14	9→10	Neighbor 10 → recurse	`{..., 10: T}`
15	10	No unvisited neighbors → backtrack all the way	`{...}`

Final visited: {4, 1, 2, 5, 3, 6, 7, 8, 9, 10} (all nodes reachable from 4)

The Recursive Call Stack


pseudo
DFS(graph, visited, 4)
  └─ DFS(graph, visited, 1)
       ├─ DFS(graph, visited, 2)
       │    └─ DFS(graph, visited, 5)
       │         └─ return
       │    └─ return
       └─ DFS(graph, visited, 3)
            └─ return
       └─ return
  └─ DFS(graph, visited, 6)
       └─ DFS(graph, visited, 7)
            └─ DFS(graph, visited, 8)
                 └─ DFS(graph, visited, 9)
                      └─ DFS(graph, visited, 10)
                           └─ return
                      └─ return
                 └─ return
            └─ return
       └─ return
  └─ return (final)

5. Connected Components

A graph is connected if every node can reach every other node. We can check this with DFS.


sql
Procedure IsConnected(graph)
    // Start DFS from node 0
    visited = {}
    visited = DFS(graph, visited, 0)
    // Check if all nodes were visited
    foreach i in rows(graph) {
        if (not(isKey(visited, i))) {
            return(False)    // Node i not reachable from 0
        }
    }
    return(True)
End IsConnected

Finding All Components


sql
Procedure FindAllComponents(graph)
    allVisited = {}
    components = []
    foreach i in rows(graph) {
        if (not(isKey(allVisited, i))) {
            // Start a new component from i
            componentVisited = {}
            componentVisited = DFS(graph, componentVisited, i)
            // Add this component's nodes to overall visited
            foreach v in keys(componentVisited) {
                allVisited[v] = True
            }
            components = components ++ [keys(componentVisited)]
        }
    }
    return(components)
End FindAllComponents

6. DFS vs BFS

Aspect	DFS (Depth-First)	BFS (Breadth-First)
Strategy	Go deep first, then backtrack	Explore all neighbors first, then go deeper
Data Structure	Stack (implicit via recursion)	Queue (explicit)
Implementation	Recursive naturally	Iterative (queue)
Path finding	Finds SOME path, not shortest	Finds SHORTEST path (fewest edges)
Memory	Less (only current path)	More (queue can grow wide)
Natural for	Tree traversal, topological sort	Shortest path, web crawling

7. Practice Questions

Basic Questions

Q1. What does DFS stand for and what does it do?

Show Answer

Depth-First Search — a graph traversal algorithm that explores as far as possible along each branch before backtracking. It visits all nodes reachable from the starting node. Q2. Why does DFS need a visited dictionary? Show Answer

Graphs can have cycles (you can go in circles). Without tracking visited nodes, DFS would loop forever, visiting the same nodes repeatedly. The visited dictionary ensures each node is processed only once. Q3. What does isKey(visited, j) check in the DFS pseudocode? Show Answer

It checks if node j has already been visited. If j is NOT in visited, it's unvisited and we should recursively explore it. If j IS in visited, we skip it to avoid cycles. Q4. How does DFS determine if a graph is connected? Show Answer

Start DFS from any node. After DFS finishes, check if all nodes are in the visited dictionary. If yes, the graph is connected (all nodes reachable from the start).

Intermediate Questions

Q5. Trace DFS on this graph starting from node 1:


pseudo
1 — 2 — 4
|    |
3 — 5

Show Answer

Step	Node	Action	visited
1	1	Visit 1	{1}
2	1→2	Neighbor 2 → recurse	{1, 2}
3	2→4	Neighbor 4 → recurse	{1, 2, 4}
4	4	No unvisited neighbors → backtrack	{1, 2, 4}
5	2→5	Neighbor 5 → recurse	{1, 2, 4, 5}
6	5→3	Neighbor 3 → recurse	{1, 2, 4, 5, 3}
7	3	No unvisited neighbors → backtrack	{1, 2, 4, 5, 3}
8	5	No more → backtrack to 2	{1, 2, 4, 5, 3}
9	2	No more → backtrack to 1	{1, 2, 4, 5, 3}
10	1	Done	{1, 2, 3, 4, 5}

All 5 nodes visited → graph is connected. Q6. What is backtracking in the context of DFS? Show Answer

Backtracking occurs when DFS reaches a node with no unvisited neighbors. The current recursive call returns, and the previous call resumes — effectively "backing up" to try other branches. This is automatic due to the recursive nature of DFS. Q7. How would you modify DFS to find a path between two nodes (not just reachability)? Show Answer


sql
Procedure FindPathDFS(graph, visited, current, target, path)
    visited[current] = True
    path = path ++ [current]

    if (current == target) {
        return(path)           // Found target!
    }

    foreach j in columns(graph) {
        if (graph[current][j] == 1 AND not(isKey(visited, j))) {
            result = FindPathDFS(graph, visited, j, target, path)
            if (result ≠ []) {
                return(result)  // Path found in this branch
            }
        }
    }

    return([])  // No path found from here
End FindPathDFS

Q8. Compare DFS and BFS. When would you use each?

Show Answer

Use DFS when: You need to explore all nodes, check connectivity, find any path (not necessarily shortest), or memory is limited.

Use BFS when: You need the shortest path (fewest edges), or the graph is very deep but narrow.

DFS uses a stack (recursion), BFS uses a queue.

Advanced Questions

Q9. Trace DFS on a graph with a cycle: 1→2→3→1. What prevents infinite looping?

Show Answer

Step	Node	Action	visited
1	1	Visit	{1}
2	1→2	Neighbor 2 unvisited → recurse	{1, 2}
3	2→3	Neighbor 3 unvisited → recurse	{1, 2, 3}
4	3→1	Neighbor 1 is visited! Skip	{1, 2, 3}
5	3	No more unvisited neighbors → backtrack	{1, 2, 3}

The visited check prevents infinite looping. Without it, DFS would go 1→2→3→1→2→3→... forever. Q10. What is the time complexity of DFS? Why? Show Answer

Time complexity: O(V + E) where V = vertices, E = edges.

Each vertex is visited exactly once (the visited check ensures this)
For each vertex, we examine all its outgoing edges (checking all columns)
Total: V vertices + E edge checks = O(V + E)

In matrix representation, we check ALL columns for each vertex, so it's O(V²). Q11. Write pseudocode to count the number of connected components in a graph. Show Answer


pseudo
Procedure CountComponents(graph)
    visited = {}
    componentCount = 0

    foreach i in rows(graph) {
        if (not(isKey(visited, i))) {
            // Found a new component
            componentCount = componentCount + 1
            visited = DFS(graph, visited, i)
        }
    }

    return(componentCount)
End CountComponents

Q12. What is the difference between DFS on a tree vs DFS on a graph?

Show Answer

In a tree: No cycles exist, so you don't strictly need a visited set (though it doesn't hurt). Every node has exactly one parent, so there's only one way to reach each node.

In a graph: Cycles can exist. You MUST use a visited set to avoid infinite looping. A node may be reachable via multiple paths.

DFS algorithm is the same for both — the visited tracking is what makes it work on general graphs.

📚 Cross-References

Course	Topic	Connection
BSCS2002 (PDSA)	Week 8 — Graph Traversal	DFS, BFS, applications
BSCS2002 (PDSA)	Week 9 — Recursion	Recursive algorithms

Next Topic: 17 — OOP: Encapsulation

Quiz Tip: End Term often asks you to trace DFS call sequences. Practice the "go deep, then backtrack" pattern! Join Discord PreviousRecursionNextOOP — Encapsulation & Abstraction