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.