Topological Sort Using DFS in DSA C#

Mental Model

We visit each node and all its dependencies first, then add the node to the order. This way, nodes come after their prerequisites.

Analogy: Imagine you have tasks to do, but some tasks depend on others. You finish all tasks needed first before doing the dependent task, like stacking books where the bottom ones must be placed first.

Graph:
A -> B -> C
↑    ↑
D    E

We want an order where each arrow points from an earlier task to a later one.

Dry Run Walkthrough

Input: Graph with edges: A->B, B->C, A->C, D->A, E->B

Goal: Find an order to do tasks so that all dependencies come before the task itself.

Step 1: Start DFS from node D

Visited: D
Stack: []

Why: We start with a node that has no dependencies to explore its chain.

Step 2: From D, visit A

Visited: D, A
Stack: []

Why: A depends on D, so we visit A after D.

Step 3: From A, visit B

Visited: D, A, B
Stack: []

Why: B depends on A, so we visit B next.

Step 4: From B, visit C

Visited: D, A, B, C
Stack: []

Why: C depends on B, so we visit C last in this chain.

Step 5: C has no dependencies, add C to stack

Stack: [C]

Why: We add nodes after visiting all their dependencies.

Step 6: Back to B, add B to stack

Stack: [C, B]

Why: All dependencies of B are visited, so add B.

Step 7: Back to A, add A to stack

Stack: [C, B, A]

Why: All dependencies of A are visited, so add A.

Step 8: Back to D, add D to stack

Stack: [C, B, A, D]

Why: All dependencies of D are visited, so add D.

Step 9: Start DFS from E (not visited yet)

Visited: D, A, B, C, E
Stack: [C, B, A, D]

Why: E is independent, so we start DFS here.

Step 10: From E, visit B (already visited)

Stack: [C, B, A, D]

Why: B is already visited, so skip.

Step 11: Add E to stack

Stack: [C, B, A, D, E]

Why: All dependencies of E are visited, so add E.

Result:

Stack (reverse order): E -> D -> A -> B -> C

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class Graph
{
    private readonly Dictionary<char, List<char>> adjList = new();

    public void AddEdge(char from, char to)
    {
        if (!adjList.ContainsKey(from)) adjList[from] = new List<char>();
        if (!adjList.ContainsKey(to)) adjList[to] = new List<char>();
        adjList[from].Add(to);
    }

    public List<char> TopologicalSort()
    {
        var visited = new HashSet<char>();
        var stack = new Stack<char>();

        foreach (var node in adjList.Keys)
        {
            if (!visited.Contains(node))
                DFS(node, visited, stack);
        }

        var result = new List<char>();
        while (stack.Count > 0)
            result.Add(stack.Pop());

        return result;
    }

    private void DFS(char node, HashSet<char> visited, Stack<char> stack)
    {
        visited.Add(node); // mark node visited

        foreach (var neighbor in adjList[node])
        {
            if (!visited.Contains(neighbor))
                DFS(neighbor, visited, stack); // visit dependencies first
        }

        stack.Push(node); // add node after dependencies
    }
}

class Program
{
    static void Main()
    {
        var graph = new Graph();
        graph.AddEdge('A', 'B');
        graph.AddEdge('B', 'C');
        graph.AddEdge('A', 'C');
        graph.AddEdge('D', 'A');
        graph.AddEdge('E', 'B');

        var order = graph.TopologicalSort();
        Console.WriteLine(string.Join(" -> ", order));
    }
}

foreach (var node in adjList.Keys) { if (!visited.Contains(node)) DFS(node, visited, stack); }

Start DFS from each unvisited node to cover all graph parts

visited.Add(node);

Mark current node as visited to avoid revisiting

foreach (var neighbor in adjList[node]) { if (!visited.Contains(neighbor)) DFS(neighbor, visited, stack); }

Visit all dependencies of current node first

stack.Push(node);

Add node to stack after all dependencies are processed

Output

E -> D -> A -> B -> C

Complexity Analysis

Time: O(V + E) because we visit each node and edge once during DFS

Space: O(V) for visited set and recursion stack to track nodes

vs Alternative: Compared to Kahn's algorithm which uses queue and in-degree counts, DFS uses recursion and stack but both have similar time complexity

Edge Cases

Empty graph

Returns empty order without error

DSA C#

foreach (var node in adjList.Keys)

Graph with single node and no edges

Returns list with that single node

DSA C#

foreach (var node in adjList.Keys)

Graph with disconnected components

Processes each component separately and combines orders

DSA C#

foreach (var node in adjList.Keys)

When to Use This Pattern

When you need to order tasks with dependencies and detect a valid sequence, use DFS-based topological sort to process dependencies before dependents.

Common Mistakes

Mistake: Adding the node to the order before visiting its dependencies
Fix: Add the node to the stack only after all its neighbors are visited

Mistake: Not marking nodes as visited, causing infinite recursion
Fix: Use a visited set to track and skip already visited nodes

Summary

It finds an order of tasks so that each task comes after all tasks it depends on.

Use it when you have tasks with dependencies and want a valid sequence to complete them.

The key is to visit all dependencies first, then add the current task to the order.

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