Topological Sort Using DFS in DSA C - Build from Scratch

Topological Sort Using DFS

📖 Scenario: You are managing tasks in a project where some tasks must be done before others. This order is important to finish the project correctly.We will use a method called Topological Sort to find the right order of tasks using Depth-First Search (DFS).

🎯 Goal: Build a program in C that uses DFS to perform a topological sort on a directed graph representing tasks and their dependencies.The program will print the tasks in the order they should be done.

📋 What You'll Learn

Create a graph using adjacency lists with 6 tasks numbered 0 to 5

Add edges to represent dependencies between tasks

Use a DFS function to explore tasks

Perform topological sort using DFS and store the order

Print the tasks in topological order

💡 Why This Matters

🌍 Real World

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

💼 Career

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

1

Create the graph data structure

Create an adjacency list graph with 6 vertices using an array of pointers to linked lists. Define a struct Node with an int vertex and a Node* next. Create an array graph of size 6 initialized to NULL.

DSA C

# Define struct Node and create an array graph of size 6 initialized to NULL
# Your code here

Hint

Use a struct to represent each node in the adjacency list. Initialize the graph array with NULLs.

2

Add edges to the graph

Write a function addEdge that takes two integers src and dest and adds an edge from src to dest in the graph. Then add these edges: 5->2, 5->0, 4->0, 4->1, 2->3, 3->1.

DSA C

# Write addEdge function and add edges 5->2, 5->0, 4->0, 4->1, 2->3, 3->1
# Your code here

Hint

Insert new nodes at the head of the adjacency list for each source vertex.

3

Implement DFS and topological sort logic

Create a visited array of size 6 initialized to 0. Create an array stack of size 6 and an integer top initialized to -1. Write a recursive function dfs that takes an integer v, marks it visited, recursively visits all adjacent vertices, then pushes v onto stack. In main, call dfs for all vertices from 0 to 5 if not visited.

DSA C

# Add visited array, stack, top variable
# Write dfs function
# Call dfs for all vertices in main
# Your code here

Hint

Use DFS to visit all neighbors before pushing the current vertex onto the stack.

4

Print the topological order

After DFS completes, print the vertices in stack from top down to 0 separated by spaces to show the topological order.

DSA C

# Print the vertices in stack from top to 0 separated by spaces
# Your code here

Hint

Print the stack from the top index down to 0 to get the correct order.

Practice

1. What is the main purpose of using DFS in Topological Sort on a Directed Acyclic Graph (DAG)?

easy

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

B. To find the shortest path between two nodes

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 to dependency order

   This ensures nodes appear after all their dependencies, which is the goal of topological sorting.

3. Final Answer:

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

4. Quick Check:

   DFS orders nodes respecting dependencies [OK]

Hint: DFS ensures dependencies come before nodes in topological order [OK]

Common Mistakes:

• Confusing topological sort with shortest path
• Thinking DFS detects cycles in undirected graphs here
• Mixing connected components with topological order

2. Which of the following is the correct way to mark a node as visited in a DFS-based topological sort in C?

easy

A. visited(node) = true;

B. visited[node] = 1;

C. visited[node] == true;

D. visited[node] = false;

Solution

1. Step 1: Understand C syntax for arrays

   In C, arrays use square brackets to access elements, so visited[node] is correct.

2. Step 2: Assigning visited status

   Assigning 1 marks the node as visited; '==' is comparison, not assignment; 'false' would mark unvisited.

3. Final Answer:

   visited[node] = 1; -> Option B

4. Quick Check:

   Use visited[node] = 1 to mark visited [OK]

Hint: Use visited[node] = 1 to mark visited in C arrays [OK]

Common Mistakes:

• Using parentheses instead of brackets for arrays
• Using '==' instead of '=' for assignment
• Assigning false instead of true/1 to mark visited

3. What is the output order of nodes after performing DFS-based topological sort on this graph?

Edges:
0 -> 1
0 -> 2
1 -> 3
2 -> 3

Assume nodes are pushed to stack after visiting all neighbors and stack is printed top to bottom.

medium

A. [0, 2, 1, 3]

B. [3, 2, 1, 0]

C. [0, 1, 2, 3]

D. [3, 1, 2, 0]

Solution

1. Step 1: Perform DFS starting from node 0

   Visit 0, then neighbors 1 then 2 (edge order). From 1 to 3, from 2 to 3 (visited).

2. Step 2: Push nodes to stack after visiting neighbors

   Push 3, then 1, then 3 already visited, then 2, then 0. Stack top to bottom: [3, 1, 2, 0].

3. Final Answer:

   [3, 1, 2, 0] -> Option D

4. Quick Check:

   Stack top to bottom after DFS = [3, 1, 2, 0] [OK]

Hint: Push nodes after neighbors; output is stack top to bottom [OK]

Common Mistakes:

• Pushing nodes before visiting neighbors
• Confusing order of neighbors visited
• Printing stack bottom to top instead of top to bottom

4. Identify the error in this DFS-based topological sort code snippet in C:

void dfs(int node) {
  visited[node] = 1;
  for (int i = 0; i < adj[node].size(); i++) {
    int nbr = adj[node][i];
    if (!visited[nbr])
      dfs(nbr);
  }
  stack.push(node);
}

medium

A. Stack push should be before recursive calls

B. Missing base case for cycle detection

C. Using adj[node].size() is invalid in C

D. visited array should be initialized to 2 instead of 1

Solution

1. Step 1: Check syntax for adjacency list size in C

   adj[node].size() is C++ syntax; C does not support .size() method on arrays.

2. Step 2: Identify correct way to get adjacency list size in C

   In C, adjacency lists are usually arrays with separate size variables; .size() causes compile error.

3. Final Answer:

   Using adj[node].size() is invalid in C -> Option C

4. Quick Check:

   adj[node].size() is C++ only, not C [OK]

Hint: Use array length variables in C, not .size() method [OK]

Common Mistakes:

• Confusing C and C++ syntax for containers
• Ignoring cycle detection in topological sort
• Pushing nodes before recursive calls

5. Given a graph with edges:

5 -> 2
5 -> 0
4 -> 0
4 -> 1
2 -> 3
3 -> 1

Which of the following is a valid topological order using DFS-based topological sort?

hard

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

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

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

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

Solution

1. Step 1: Analyze prerequisites from edges

   (u -> v means u before v): 5 before 2 and 0; 4 before 0 and 1; 2 before 3; 3 before 1.

2. Step 2: Check each option for prerequisite order

   [4, 5, 2, 3, 1, 0]: 4 before 0 and 1, 5 before 2 and 0, 2 before 3, 3 before 1, all correct.

3. Final Answer:

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

4. Quick Check:

   All edges respected in order D [OK]

Hint: Check each edge u->v: u appears before v in order [OK]

Common Mistakes:

• Ignoring edge directions in order
• Placing dependent nodes before their prerequisites
• Assuming any order with all nodes is valid