C# Program to Implement DFS (Depth-First Search)

A C# program to implement DFS uses a recursive method that visits a node, marks it visited, and then recursively visits all its unvisited neighbors, like void DFS(int node) { visited[node] = true; foreach(var neighbor in graph[node]) { if(!visited[neighbor]) DFS(neighbor); } }.

Examples

InputGraph: 0->1, 0->2, 1->2, 2->0, 2->3, 3->3; Start node: 2

OutputVisited nodes in order: 2 0 1 3

InputGraph: 0->1, 1->2, 2->3; Start node: 0

OutputVisited nodes in order: 0 1 2 3

InputGraph: 0->; Start node: 0

OutputVisited nodes in order: 0

How to Think About It

To implement DFS, think of starting at a node, marking it as visited, then exploring each connected node that hasn't been visited yet by calling the same process again. This repeats until all reachable nodes are visited.

Algorithm

1

Start at the given node and mark it as visited.

2

For each neighbor of the current node, check if it is visited.

3

If a neighbor is not visited, recursively perform DFS on that neighbor.

4

Repeat until all reachable nodes are visited.

Code

csharp

using System;
using System.Collections.Generic;

class Program {
    static List<int>[] graph;
    static bool[] visited;

    static void DFS(int node) {
        visited[node] = true;
        Console.Write(node + " ");
        foreach (var neighbor in graph[node]) {
            if (!visited[neighbor]) DFS(neighbor);
        }
    }

    static void Main() {
        int n = 4;
        graph = new List<int>[n];
        for (int i = 0; i < n; i++) graph[i] = new List<int>();

        graph[0].Add(1);
        graph[0].Add(2);
        graph[1].Add(2);
        graph[2].Add(0);
        graph[2].Add(3);
        graph[3].Add(3);

        visited = new bool[n];
        Console.Write("Visited nodes in order: ");
        DFS(2);
    }
}

Output

Visited nodes in order: 2 0 1 3 

Dry Run

Let's trace the DFS starting from node 2 on the example graph.

1

Start DFS at node 2

Mark node 2 visited, print 2.

2

Visit neighbors of node 2

Neighbors are 0 and 3. Node 0 not visited, call DFS(0).

3

DFS at node 0

Mark node 0 visited, print 0. Neighbors: 1, 2. Node 1 not visited, call DFS(1). Node 2 already visited.

4

DFS at node 1

Mark node 1 visited, print 1. Neighbor: 2 already visited.

5

Back to node 2 neighbors

Next neighbor is 3, not visited, call DFS(3).

6

DFS at node 3

Mark node 3 visited, print 3. Neighbor: 3 already visited.

Step	Current Node	Visited Array	Output
1	2	[false, false, true, false]	2
2	0	[false, false, true, false]	2
3	0	[true, false, true, false]	2 0
4	1	[true, false, true, false]	2 0
5	1	[true, false, true, false]	2 0 1
6	3	[true, true, true, false]	2 0 1
7	3	[true, true, true, true]	2 0 1 3

Why This Works

Step 1: Mark node visited

We use visited[node] = true to avoid visiting the same node multiple times.

Step 2: Print current node

Printing the node shows the order in which nodes are visited during DFS.

Step 3: Recursive call for neighbors

For each neighbor, if not visited, we call DFS again to explore deeper nodes.

Alternative Approaches

Iterative DFS using stack

csharp

using System;
using System.Collections.Generic;

class Program {
    static List<int>[] graph;

    static void DFSIterative(int start) {
        int n = graph.Length;
        bool[] visited = new bool[n];
        Stack<int> stack = new Stack<int>();
        stack.Push(start);

        while (stack.Count > 0) {
            int node = stack.Pop();
            if (!visited[node]) {
                visited[node] = true;
                Console.Write(node + " ");
                foreach (var neighbor in graph[node]) {
                    if (!visited[neighbor]) stack.Push(neighbor);
                }
            }
        }
    }

    static void Main() {
        int n = 4;
        graph = new List<int>[n];
        for (int i = 0; i < n; i++) graph[i] = new List<int>();

        graph[0].Add(1);
        graph[0].Add(2);
        graph[1].Add(2);
        graph[2].Add(0);
        graph[2].Add(3);
        graph[3].Add(3);

        Console.Write("Visited nodes in order: ");
        DFSIterative(2);
    }
}

Uses a stack instead of recursion, which can avoid stack overflow on very deep graphs.

DFS with adjacency matrix

csharp

using System;

class Program {
    static int[,] graph;
    static bool[] visited;

    static void DFS(int node) {
        visited[node] = true;
        Console.Write(node + " ");
        for (int i = 0; i < graph.GetLength(0); i++) {
            if (graph[node, i] == 1 && !visited[i]) DFS(i);
        }
    }

    static void Main() {
        int n = 4;
        graph = new int[n, n] {
            {0,1,1,0},
            {0,0,1,0},
            {1,0,0,1},
            {0,0,0,1}
        };
        visited = new bool[n];
        Console.Write("Visited nodes in order: ");
        DFS(2);
    }
}

Uses a matrix to represent edges, which is simpler for dense graphs but uses more memory.

Complexity: O(V + E) time, O(V) space

Time Complexity

DFS visits each vertex and edge once, so the time is proportional to the number of vertices plus edges.

Space Complexity

Space is needed for the visited array and recursion stack, both proportional to the number of vertices.

Which Approach is Fastest?

Recursive and iterative DFS have similar time complexity; iterative avoids recursion overhead but may be less intuitive.

Approach	Time	Space	Best For
Recursive DFS	O(V + E)	O(V)	Simplicity and readability
Iterative DFS	O(V + E)	O(V)	Avoiding recursion stack overflow
Adjacency Matrix DFS	O(V^2)	O(V^2)	Dense graphs with many edges