DFS Depth First Search on Graph in DSA C#

Mental Model

DFS explores as far as possible along each branch before backtracking. It dives deep into one path before trying another.

Analogy: Imagine exploring a maze by always taking the first unexplored path you see until you hit a dead end, then backtracking to try other paths.

Graph adjacency list:
0 -> [1, 2]
1 -> [2]
2 -> [0, 3]
3 -> [3]
Start at node 2 ↑

Dry Run Walkthrough

Input: Graph with edges: 0->1, 0->2, 1->2, 2->0, 2->3, 3->3; start DFS at node 2

Goal: Visit all nodes reachable from node 2 in depth-first order

Step 1: Start DFS at node 2, mark 2 visited

Visited: {2}
Stack: [2]
Traversal order: 2

Why: We begin exploring from node 2

Step 2: From node 2, visit neighbor 0, mark 0 visited

Visited: {2, 0}
Stack: [2, 0]
Traversal order: 2 -> 0

Why: Explore first neighbor of 2 deeply

Step 3: From node 0, visit neighbor 1, mark 1 visited

Visited: {2, 0, 1}
Stack: [2, 0, 1]
Traversal order: 2 -> 0 -> 1

Why: Go deeper from 0 to 1

Step 4: From node 1, neighbor 2 already visited, backtrack to 0

Visited: {2, 0, 1}
Stack: [2, 0]
Traversal order: 2 -> 0 -> 1

Why: No new nodes from 1, backtrack

Step 5: From node 0, neighbor 2 already visited, backtrack to 2

Visited: {2, 0, 1}
Stack: [2]
Traversal order: 2 -> 0 -> 1

Why: No new nodes from 0, backtrack

Step 6: From node 2, visit neighbor 3, mark 3 visited

Visited: {2, 0, 1, 3}
Stack: [2, 3]
Traversal order: 2 -> 0 -> 1 -> 3

Why: Explore next neighbor of 2

Step 7: From node 3, neighbor 3 already visited, backtrack to 2

Visited: {2, 0, 1, 3}
Stack: [2]
Traversal order: 2 -> 0 -> 1 -> 3

Why: No new nodes from 3, backtrack

Step 8: All neighbors of 2 visited, DFS complete

Visited: {2, 0, 1, 3}
Stack: []
Traversal order: 2 -> 0 -> 1 -> 3

Why: Traversal finished

Result:

Traversal order: 2 -> 0 -> 1 -> 3

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class Graph
{
    private readonly int _vertices;
    private readonly List<int>[] _adjacencyList;

    public Graph(int vertices)
    {
        _vertices = vertices;
        _adjacencyList = new List<int>[vertices];
        for (int i = 0; i < vertices; i++)
        {
            _adjacencyList[i] = new List<int>();
        }
    }

    public void AddEdge(int src, int dest)
    {
        _adjacencyList[src].Add(dest);
    }

    public void DFS(int start)
    {
        bool[] visited = new bool[_vertices];
        Stack<int> stack = new Stack<int>();
        stack.Push(start); // push start node

        while (stack.Count > 0)
        {
            int node = stack.Pop(); // pop top node
            if (!visited[node])
            {
                Console.Write(node + " "); // visit node
                visited[node] = true; // mark visited

                // push neighbors in reverse order for correct DFS order
                for (int i = _adjacencyList[node].Count - 1; i >= 0; i--)
                {
                    int neighbor = _adjacencyList[node][i];
                    if (!visited[neighbor])
                    {
                        stack.Push(neighbor); // push unvisited neighbor
                    }
                }
            }
        }
    }
}

class Program
{
    static void Main()
    {
        Graph graph = new Graph(4);
        graph.AddEdge(0, 1);
        graph.AddEdge(0, 2);
        graph.AddEdge(1, 2);
        graph.AddEdge(2, 0);
        graph.AddEdge(2, 3);
        graph.AddEdge(3, 3);

        graph.DFS(2);
    }
}

stack.Push(start); // push start node

initialize stack with start node to begin DFS

int node = stack.Pop(); // pop top node

get current node to visit from stack

if (!visited[node])

check if node is not visited to avoid repeats

Console.Write(node + " "); // visit node

record visiting node in traversal order

visited[node] = true; // mark visited

mark node as visited to prevent revisiting

for (int i = _adjacencyList[node].Count - 1; i >= 0; i--)

iterate neighbors in reverse to maintain DFS order with stack

if (!visited[neighbor])

push only unvisited neighbors to stack

stack.Push(neighbor); // push unvisited neighbor

add neighbor to stack for future visit

Output

2 0 1 3 

Complexity Analysis

Time: O(V + E) because each vertex and edge is visited once in DFS

Space: O(V) for the visited array and stack in worst case

vs Alternative: Compared to BFS which uses a queue, DFS uses a stack and explores deeper paths first; both have similar time but different traversal orders

Edge Cases

Empty graph (no vertices)

DFS does nothing as there are no nodes to visit

DSA C#

stack.Push(start); // push start node

Graph with isolated nodes

DFS visits only nodes reachable from start node

DSA C#

if (!visited[node])

Graph with self-loop (node 3 -> 3)

Self-loop does not cause infinite loop due to visited check

DSA C#

if (!visited[neighbor])

When to Use This Pattern

When you need to explore all connected parts of a graph deeply before backtracking, use DFS because it naturally follows paths to their end before trying alternatives.

Common Mistakes

Mistake: Not marking nodes as visited before pushing neighbors causes repeated visits and infinite loops.
Fix: Mark nodes as visited immediately after popping from stack before pushing neighbors.

Summary

DFS visits nodes by going deep along each path before backtracking.

Use DFS when you want to explore all nodes reachable from a start node deeply or check connectivity.

The key insight is to use a stack and mark nodes visited to avoid cycles and repeated visits.

Practice

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

easy

A. Visit nodes in order of their distance from the start node

B. Visit all neighbors of a node before moving deeper

C. Explore as far as possible along each branch before backtracking

D. Randomly visit nodes until all are visited

Solution

1. Step 1: Understand DFS traversal

   DFS explores a graph by going deep into one branch before backtracking to explore others.

2. Step 2: Compare with other traversal methods

   BFS visits neighbors first, but DFS goes deep first.

3. Final Answer:

   Explore as far as possible along each branch before backtracking -> Option C

4. Quick Check:

   DFS = deep exploration first [OK]

Hint: DFS means go deep first, then backtrack [OK]

Common Mistakes:

• Confusing DFS with BFS
• Thinking DFS visits neighbors first
• Assuming DFS visits nodes by distance

2. Which of the following is the correct way to start a DFS traversal in C# using recursion on a graph represented by adjacency list Dictionary<int, List<int>> graph?

easy

A. void DFS(int node, HashSet<int> visited) { if (visited.Contains(node)) return; visited.Add(node); foreach (var neighbor in graph[node]) DFS(neighbor, visited); }

B. void DFS(int node) { visited.Add(node); foreach (var neighbor in graph[node]) DFS(neighbor); }

C. void DFS(int node, List<int> visited) { if (visited.Contains(node)) return; visited.Add(node); foreach (var neighbor in graph[node]) DFS(neighbor, visited); }

D. void DFS(int node, HashSet<int> visited) { visited.Add(node); foreach (var neighbor in graph) DFS(neighbor, visited); }

Solution

1. Step 1: Check parameters and visited tracking

   void DFS(int node, HashSet<int> visited) { if (visited.Contains(node)) return; visited.Add(node); foreach (var neighbor in graph[node]) DFS(neighbor, visited); } uses HashSet to track visited nodes and prevents revisiting.

2. Step 2: Verify iteration over neighbors

   void DFS(int node, HashSet<int> visited) { if (visited.Contains(node)) return; visited.Add(node); foreach (var neighbor in graph[node]) DFS(neighbor, visited); } correctly iterates over neighbors of the current node from the graph dictionary.

3. Final Answer:

   void DFS(int node, HashSet<int> visited) { if (visited.Contains(node)) return; visited.Add(node); foreach (var neighbor in graph[node]) DFS(neighbor, visited); } -> Option A

4. Quick Check:

   Correct recursion with visited check [OK]

Hint: Use HashSet to track visited nodes in DFS recursion [OK]

Common Mistakes:

• Not checking if node is visited before recursion
• Using List instead of HashSet for visited (slow lookup)
• Iterating over graph keys instead of neighbors

3. Given the graph adjacency list:

var graph = new Dictionary {
  {1, new List<int>{2, 3}},
  {2, new List<int>{4}},
  {3, new List<int>{4}},
  {4, new List<int>()}
};

List<int> visited = new List<int>();
DFS(1, visited); // DFS as defined in option C above
Console.WriteLine(string.Join(", ", visited));

What is the output?

medium

A. 1, 2, 3, 4

B. 1, 2, 4, 3

C. 1, 3, 4, 2

D. 1, 4, 2, 3

Solution

1. Step 1: Start DFS from node 1

   Visit 1, mark visited. Neighbors: 2, 3.

2. Step 2: Visit neighbor 2 first

   Visit 2, then its neighbor 4. 4 has no neighbors, backtrack.

3. Step 3: Backtrack to 1 and visit neighbor 3

   Visit 3, then neighbor 4 (already visited, skip).

4. Step 4: Order of visited nodes

   Visited nodes in order: 1, 2, 4, 3.

5. Final Answer:

   1, 2, 4, 3 -> Option B

6. Quick Check:

   DFS order = 1,2,4,3 [OK]

Hint: DFS visits neighbors in order, backtracks after deepest node [OK]

Common Mistakes:

• Assuming BFS order instead of DFS
• Visiting node 3 before node 2
• Revisiting already visited nodes

4. Consider this DFS code snippet in C#:

void DFS(int node, HashSet<int> visited) {
  visited.Add(node);
  foreach (var neighbor in graph.Keys) {
    if (!visited.Contains(neighbor)) {
      DFS(neighbor, visited);
    }
  }
}

What is the main problem with this DFS implementation?

medium

A. It iterates over all graph nodes instead of neighbors of the current node

B. It does not add the current node to visited

C. It uses List instead of HashSet for visited nodes

D. It does not check if the node is null before recursion

Solution

1. Step 1: Analyze the foreach loop

   The loop iterates over all keys in the graph, not neighbors of the current node.

2. Step 2: Understand DFS neighbor traversal

   DFS should explore neighbors of the current node, not all nodes in the graph.

3. Final Answer:

   It iterates over all graph nodes instead of neighbors of the current node -> Option A

4. Quick Check:

   DFS must visit neighbors, not all nodes [OK]

Hint: Loop over neighbors, not all graph keys [OK]

Common Mistakes:

• Looping over graph.Keys instead of graph[node]
• Forgetting to add node to visited
• Not checking visited before recursion

5. You want to find if there is a path from node 1 to node 5 in this directed graph:

var graph = new Dictionary {
  {1, new List<int>{2, 3}},
  {2, new List<int>{4}},
  {3, new List<int>{4, 5}},
  {4, new List<int>{}},
  {5, new List<int>{}}
};

bool DFS(int current, int target, HashSet<int> visited) {
  if (current == target) return true;
  visited.Add(current);
  foreach (var neighbor in graph[current]) {
    if (!visited.Contains(neighbor)) {
      if (DFS(neighbor, target, visited)) return true;
    }
  }
  return false;
}

var visited = new HashSet<int>();
bool result = DFS(1, 5, visited);
Console.WriteLine(result);

What will be printed?

hard

A. Runtime exception

B. False

C. Compilation error

D. True

Solution

1. Step 1: Start DFS from node 1 looking for 5

   Visit 1, neighbors 2 and 3.

2. Step 2: Explore neighbor 2

   From 2, visit 4. 4 has no neighbors, backtrack.

3. Step 3: Explore neighbor 3

   From 3, neighbors are 4 and 5. 4 visited, then 5 found matches target.

4. Step 4: DFS returns true when target found

   DFS returns true and prints True.

5. Final Answer:

   True -> Option D

6. Quick Check:

   Path exists from 1 to 5 [OK]

Hint: DFS returns true immediately when target found [OK]

Common Mistakes:

• Assuming no path because 5 is not direct neighbor
• Not returning true when target found
• Forgetting to mark visited nodes