Topological Sort Using DFS in DSA C# - Build from Scratch

Topological Sort Using DFS

📖 Scenario: Imagine you are managing tasks for a project. Some tasks must be done before others. You want to find an order to do all tasks so that every task is done only after all its prerequisites are done.

🎯 Goal: Build a program that uses Depth First Search (DFS) to find a valid order of tasks (topological sort) from given task dependencies.

📋 What You'll Learn

Create a dictionary to represent the graph of tasks and their dependencies

Use a helper dictionary to track visited tasks

Implement DFS to explore tasks and build the topological order

Print the tasks in a valid order after sorting

💡 Why This Matters

🌍 Real World

Topological sort is used in project management, build systems, and course scheduling where some tasks must happen before others.

💼 Career

Understanding topological sort and DFS is important for software engineers working on dependency resolution, task scheduling, and compiler design.

1

Create the task dependency graph

Create a dictionary called graph with these exact entries: "A" points to new List<string> { "C" }, "B" points to new List<string> { "C", "D" }, "C" points to new List<string> { "E" }, "D" points to new List<string> { "F" }, and "E" and "F" point to empty lists.

DSA C#

# Your code here

Hint

Use a Dictionary<string, List<string>> to store tasks and their dependent tasks.

2

Create a visited dictionary to track tasks

Add a dictionary called visited with keys as all tasks "A", "B", "C", "D", "E", and "F", all set to false.

DSA C#

using System;
using System.Collections.Generic;

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

        // Create visited dictionary
        // Your code here
    }
}

Hint

Use a Dictionary<string, bool> to mark if a task is visited or not.

3

Implement DFS to build topological order

Add a list called result to store the order. Then write a method DFS that takes a string task, marks it visited, recursively calls DFS on all neighbors from graph[task] if not visited, and finally adds task to result. In Main, call DFS for each task "A", "B", "C", "D", "E", and "F" if not visited.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static List result = new List();

    static void DFS(string task, Dictionary> graph, Dictionary visited)
    {
        // Your code here
    }

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

        Dictionary visited = new Dictionary
        {
            { "A", false },
            { "B", false },
            { "C", false },
            { "D", false },
            { "E", false },
            { "F", false }
        };

        // Call DFS for each task
        // Your code here
    }
}

Hint

Mark the task visited, call DFS on neighbors if not visited, then add the task to result. Call DFS for each task in Main.

4

Print the topological order

Print the tasks in result in reverse order separated by spaces using Console.WriteLine.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static List result = new List();

    static void DFS(string task, Dictionary> graph, Dictionary visited)
    {
        visited[task] = true;
        foreach (var neighbor in graph[task])
        {
            if (!visited[neighbor])
            {
                DFS(neighbor, graph, visited);
            }
        }
        result.Add(task);
    }

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

        Dictionary visited = new Dictionary
        {
            { "A", false },
            { "B", false },
            { "C", false },
            { "D", false },
            { "E", false },
            { "F", false }
        };

        DFS("A", graph, visited);
        DFS("B", graph, visited);
        DFS("C", graph, visited);
        DFS("D", graph, visited);
        DFS("E", graph, visited);
        DFS("F", graph, visited);

        // Print the result in reverse order
        // Your code here
    }
}

Hint

Reverse the result list and print all tasks separated by spaces.

Practice

1. What is the main purpose of using DFS in Topological Sort on a directed graph?

easy

A. To find the shortest path between two nodes

B. To visit nodes in a way that all dependencies come before the node itself

C. To detect cycles in an undirected graph

D. To count the number of connected components

Solution

1. Step 1: Understand DFS role in Topological Sort

   DFS visits nodes deeply, ensuring all nodes reachable from a node are visited before the node itself.

2. Step 2: Relate DFS order to dependencies

   In Topological Sort, nodes must appear after all their dependencies, which DFS achieves by post-order traversal.

3. Final Answer:

   To visit nodes in a way that all dependencies come before the node itself -> Option B

4. Quick Check:

   DFS ensures dependency order [OK]

Hint: DFS post-order gives correct dependency order [OK]

Common Mistakes:

• Confusing DFS with BFS for topological sorting
• Thinking DFS finds shortest paths
• Assuming DFS detects cycles in undirected graphs only

2. Which of the following C# code snippets correctly starts a DFS-based topological sort on all nodes in a graph represented as adjacency list Dictionary?

easy

A. for(int i=0; i

B. while(graph.Count > 0) DFS(graph.First().Key);

C. foreach(var node in graph.Keys) if(!visited[node]) DFS(node);

D. foreach(var node in graph.Values) DFS(node[0]);

Solution

1. Step 1: Identify correct iteration over nodes

   We must iterate over all keys (nodes) and call DFS only if not visited.

2. Step 2: Check each option's correctness

   foreach(var node in graph.Keys) if(!visited[node]) DFS(node); correctly iterates keys and checks visited. for(int i=0; i 0) DFS(graph.First().Key); modifies graph during iteration, unsafe. foreach(var node in graph.Values) DFS(node[0]); iterates values, not nodes.

3. Final Answer:

   foreach(var node in graph.Keys) if(!visited[node]) DFS(node); -> Option C

4. Quick Check:

   Iterate keys and check visited [OK]

Hint: Iterate graph keys, check visited before DFS [OK]

Common Mistakes:

• Iterating over graph.Values instead of Keys
• Assuming node indices are continuous from 0
• Modifying collection during iteration

3. What is the output of the following C# code performing topological sort using DFS on the graph edges: 5->2, 5->0, 4->0, 4->1, 2->3, 3->1?

var graph = new Dictionary {
  {5, new List<int>{2,0}},
  {4, new List<int>{0,1}},
  {2, new List<int>{3}},
  {3, new List<int>{1}},
  {0, new List<int>()},
  {1, new List<int>()}
};
var visited = new HashSet<int>();
var stack = new Stack<int>();
void DFS(int node) {
  visited.Add(node);
  foreach(var n in graph[node]) {
    if(!visited.Contains(n)) DFS(n);
  }
  stack.Push(node);
}
foreach(var node in graph.Keys) {
  if(!visited.Contains(node)) DFS(node);
}
var result = stack.ToArray();
Console.WriteLine(string.Join(", ", result));

medium

A. 4, 5, 0, 2, 3, 1

B. 5, 4, 2, 3, 1, 0

C. 5, 4, 0, 1, 2, 3

D. 4, 5, 0, 1, 2, 3

Solution

1. Step 1: Perform DFS and track stack push order

   Start DFS from 5: visit 2, then 3, then 1; push 1, 3, 2, then 0 from 5's other edge; push 5. Then DFS from 4: visit 0 and 1 already visited, push 4.

2. Step 2: Stack order and output

   Stack push order is 1, 3, 2, 0, 5, 4. Converting stack to array reverses order: 4, 5, 0, 2, 3, 1.

3. Final Answer:

   4, 5, 0, 2, 3, 1 -> Option A

4. Quick Check:

   DFS post-order reversed = topological order [OK]

Hint: Stack reversed after DFS gives topological order [OK]

Common Mistakes:

• Not reversing stack before output
• Visiting nodes in wrong order
• Ignoring nodes with no outgoing edges

4. The following C# DFS-based topological sort code throws a runtime error. What is the likely cause?

void DFS(int node) {
  visited.Add(node);
  foreach(var n in graph[node]) {
    if(!visited.Contains(n)) DFS(n);
  }
  stack.Push(node);
}
foreach(var node in graph.Keys) {
  DFS(node);
}

medium

A. No error; code runs correctly

B. NullReferenceException because graph is empty

C. Stack overflow due to infinite recursion from cycles

D. KeyNotFoundException because some nodes are missing in graph keys

Solution

1. Step 1: Analyze potential runtime errors in DFS

   When recursing to a neighbor n not present as a key in the graph (common for sink nodes), accessing graph[n] throws KeyNotFoundException.

2. Step 2: Outer loop issue

   Missing !visited check before DFS(node) causes duplicate stack pushes (logical error), not runtime error. Cycle detection needs separate recursion stack.

3. Final Answer:

   KeyNotFoundException because some nodes are missing in graph keys -> Option D

4. Quick Check:

   graph[n] for missing sink node key -> KeyNotFoundException [OK]

Hint: Include all nodes as keys with empty lists [OK]

Common Mistakes:

• Omitting sink/leaf nodes from graph keys
• Not initializing empty List<int>() for nodes with no outgoing edges
• Assuming all edge targets are automatically graph keys

5. Given a directed acyclic graph (DAG) with nodes representing tasks and edges representing dependencies, how can you modify the DFS-based topological sort to detect if the graph contains a cycle?

hard

A. Use an additional recursion stack set to track nodes in the current DFS path and detect back edges

B. Count the number of nodes visited and compare with total nodes after DFS

C. Run BFS instead of DFS to detect cycles

D. Sort nodes by their degree before DFS

Solution

1. Step 1: Understand cycle detection in DFS

   Use a recursion stack set to mark nodes currently in the DFS path. If a node is revisited while in this set, a cycle exists.

2. Step 2: Explain why other options fail

   Counting visited nodes doesn't detect cycles. BFS alone doesn't detect cycles in directed graphs. Sorting by degree doesn't help detect cycles.

3. Final Answer:

   Use an additional recursion stack set to track nodes in the current DFS path and detect back edges -> Option A

4. Quick Check:

   Recursion stack detects cycles in DFS [OK]

Hint: Track recursion stack to find back edges indicating cycles [OK]

Common Mistakes:

• Ignoring recursion stack for cycle detection
• Assuming BFS detects cycles in directed graphs
• Using node count to detect cycles