DFS Depth First Search on Graph in DSA C# - Build from Scratch

DFS Depth First Search on Graph

📖 Scenario: You are exploring a small network of connected cities represented as a graph. Each city is a node, and roads between cities are edges. You want to visit all cities starting from a specific city using Depth First Search (DFS).

🎯 Goal: Build a program that performs DFS on a graph represented by an adjacency list. You will create the graph, set a starting city, implement DFS to visit all connected cities, and print the order of visited cities.

📋 What You'll Learn

Create a graph using a dictionary with city names as keys and lists of connected cities as values.

Create a variable to hold the starting city for DFS.

Implement DFS using recursion to visit cities.

Print the order of cities visited by DFS.

💡 Why This Matters

🌍 Real World

Graphs are used to model networks like roads, social connections, and computer networks. DFS helps explore all connected parts starting from one point.

💼 Career

Understanding DFS is fundamental for software engineers working with graph algorithms, network analysis, and solving problems like pathfinding and connectivity.

1

Create the graph as an adjacency list

Create a dictionary called graph with these exact entries: "A": new List { "B", "C" }, "B": new List { "A", "D", "E" }, "C": new List { "A", "F" }, "D": new List { "B" }, "E": new List { "B", "F" }, "F": new List { "C", "E" }.

DSA C#

// Create the graph dictionary with adjacency lists
// Your code here

Hint

Use a Dictionary<string, List<string>> to represent the graph. Each key is a city name, and the value is a list of connected cities.

2

Set the starting city for DFS

Create a string variable called startCity and set it to "A".

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Dictionary> graph = new Dictionary>
        {
            { "A", new List { "B", "C" } },
            { "B", new List { "A", "D", "E" } },
            { "C", new List { "A", "F" } },
            { "D", new List { "B" } },
            { "E", new List { "B", "F" } },
            { "F", new List { "C", "E" } }
        };

        // Create the startCity variable and set it to "A"
        // Your code here
    }
}

Hint

Just create a string variable named startCity and assign it the value "A".

3

Implement DFS to visit cities

Create a method called DFS that takes string city, Dictionary<string, List<string>> graph, and HashSet<string> visited. Use recursion to visit the city, add it to visited, and call DFS on each connected city not in visited. In Main, create a HashSet<string> called visited and call DFS(startCity, graph, visited).

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Dictionary> graph = new Dictionary>
        {
            { "A", new List { "B", "C" } },
            { "B", new List { "A", "D", "E" } },
            { "C", new List { "A", "F" } },
            { "D", new List { "B" } },
            { "E", new List { "B", "F" } },
            { "F", new List { "C", "E" } }
        };

        string startCity = "A";

        // Create a HashSet called visited
        // Call DFS(startCity, graph, visited)
    }

    // Create the DFS method here
    // Your code here
}

Hint

Use recursion to visit each city. Add the city to visited, print it, then call DFS on neighbors not yet visited.

4

Print the order of visited cities

Run the program to print the order of cities visited by DFS starting from startCity. The output should be the cities printed in the order they are visited.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Dictionary> graph = new Dictionary>
        {
            { "A", new List { "B", "C" } },
            { "B", new List { "A", "D", "E" } },
            { "C", new List { "A", "F" } },
            { "D", new List { "B" } },
            { "E", new List { "B", "F" } },
            { "F", new List { "C", "E" } }
        };

        string startCity = "A";

        HashSet visited = new HashSet();
        DFS(startCity, graph, visited);
    }

    static void DFS(string city, Dictionary> graph, HashSet visited)
    {
        visited.Add(city);
        Console.WriteLine(city);

        foreach (string neighbor in graph[city])
        {
            if (!visited.Contains(neighbor))
            {
                DFS(neighbor, graph, visited);
            }
        }
    }

    // No additional code needed here
}

Hint

Run the program. The console will print the cities in the order DFS visits them starting from "A".

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