Topological Sort

Introduction

Topological Sorting for a Directed Acyclic Graph (DAG) is a linear ordering of its vertices such that for every directed edge u → v , vertex 𝑢 appears before 𝑣 in the ordering. It is only applicable to DAGs, as cycles prevent a valid order. The sorting begins with vertices that have no incoming edges (in-degree 0).

How Topological Sort Works?

Understand the Graph Structure

Topological Sort is applicable only to Directed Acyclic Graphs (DAGs). A DAG is a graph with directed edges and no cycles.
In a topological sort, you arrange the vertices in a linear order such that for every directed edge u → v, u comes before v in the ordering.

Initialize the Data Structures

You need two main things:

Visited Array: This keeps track of which nodes have been visited.
Stack: The stack stores nodes in the topological order.

Perform DFS (Depth-First Search)

Start a DFS from each unvisited node. The idea is to explore all the descendants of a node before returning to it.

For each node, do the following:

Mark the node as visited.
Explore all its unvisited neighbors (connected nodes).
Recursively apply DFS on each neighbor.

Add Node to Stack after DFS

After all the neighbors of a node have been visited, push the node onto the stack. This ensures that a node appears before its descendants in the topological order.

Repeat for All Nodes

Repeat the DFS for every unvisited node in the graph, ensuring that you cover all disconnected parts of the graph.

Retrieve the Topological Order

After performing DFS on all nodes, the stack will contain the nodes in the reverse topological order.
Pop all elements from the stack and the resulting order will be the topological sort of the graph.

Implementation of Topological Sort

//topologicalsort.cpp
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
void dfs(vector<bool> &visited, vector<vector<int>> &adj, int u, stack<int> &st)
{
visited[u] = true;
for (int &v : adj[u])
{
    if (!visited[v])
    {
        dfs(visited, adj, v, st);
    }
}
st.push(u);
}

vector<int> topologicalSort(vector<vector<int>> &adj)
{
stack<int> st;
vector<bool> visited(adj.size(), 0);
vector<int> ans(adj.size());
for (int i = 0; i < adj.size(); i++)
{
    if (!visited[i])
    {
        dfs(visited, adj, i, st);
    }
}
int i = 0;
while (!st.empty())
{
    ans[i++] = st.top();
    st.pop();
}
return ans;
}
int main()
{
int n = 6; 
vector<vector<int>> adj = {
    {2, 3},   // 0 → 2, 0 → 3
    {4},       // 1 → 4
    {1,3},       // 2 → 1,2->3
    {1},       // 3 → 1
    {},       //
    {1,4}         // 5->1,5->4
};

vector<int> result = topologicalSort(adj);

for (int node : result) {
    cout << node << " ";
}

return 0;
}

# topological_sort.py

def topological_sort_dfs(adj_list, num_vertices):
 """
 Topological sort using DFS approach
 
 Args:
     adj_list: Adjacency list representation of the graph
     num_vertices: Number of vertices in the graph
 
 Returns:
     List containing topological order of vertices
 """
 visited = [False] * num_vertices
 stack = []
 
 def dfs(vertex):
     visited[vertex] = True
     
     # Visit all adjacent vertices
     for neighbor in adj_list[vertex]:
         if not visited[neighbor]:
             dfs(neighbor)
     
     # Push current vertex to stack after visiting all neighbors
     stack.append(vertex)
 
 # Call DFS for all unvisited vertices
 for i in range(num_vertices):
     if not visited[i]:
         dfs(i)
 
 # Return vertices in topological order (reverse of stack)
 return stack[::-1]

def topological_sort_kahns(adj_list, num_vertices):
 """
 Topological sort using Kahn's algorithm (BFS approach)
 
 Args:
     adj_list: Adjacency list representation of the graph
     num_vertices: Number of vertices in the graph
 
 Returns:
     List containing topological order of vertices, empty if cycle exists
 """
 from collections import deque
 
 # Calculate indegree for each vertex
 indegree = [0] * num_vertices
 for u in range(num_vertices):
     for v in adj_list[u]:
         indegree[v] += 1
 
 # Initialize queue with vertices having 0 indegree
 queue = deque()
 for i in range(num_vertices):
     if indegree[i] == 0:
         queue.append(i)
 
 topo_order = []
 
 # Process vertices in BFS manner
 while queue:
     vertex = queue.popleft()
     topo_order.append(vertex)
     
     # Decrease indegree of adjacent vertices
     for neighbor in adj_list[vertex]:
         indegree[neighbor] -= 1
         if indegree[neighbor] == 0:
             queue.append(neighbor)
 
 # Check if all vertices are included (no cycle)
 if len(topo_order) != num_vertices:
     return []  # Graph has a cycle
 
 return topo_order

# Example usage
if __name__ == "__main__":
 # Example DAG
 num_vertices = 6
 adj_list = [
     [2, 3],    # 0 → 2, 3
     [4],       # 1 → 4
     [1, 3],    # 2 → 1, 3
     [1],       # 3 → 1
     [],        # 4 → none
     [1, 4]     # 5 → 1, 4
 ]
 
 print("Using DFS approach:")
 result_dfs = topological_sort_dfs(adj_list, num_vertices)
 print("Topological Order:", result_dfs)
 
 print("\nUsing Kahn's algorithm:")
 result_kahns = topological_sort_kahns(adj_list, num_vertices)
 if result_kahns:
     print("Topological Order:", result_kahns)
 else:
     print("Graph contains a cycle")

# Output: Topological Order: [5, 0, 2, 3, 1, 4]

// topological_sort.js

function topologicalSortDFS(adjList, numVertices) {
 /**
  * Topological sort using DFS approach
  * 
  * @param {Array} adjList - Adjacency list representation of the graph
  * @param {number} numVertices - Number of vertices in the graph
  * @returns {Array} - Array containing topological order of vertices
  */
 const visited = new Array(numVertices).fill(false);
 const stack = [];
 
 function dfs(vertex) {
     visited[vertex] = true;
     
     // Visit all adjacent vertices
     for (const neighbor of adjList[vertex]) {
         if (!visited[neighbor]) {
             dfs(neighbor);
         }
     }
     
     // Push current vertex to stack after visiting all neighbors
     stack.push(vertex);
 }
 
 // Call DFS for all unvisited vertices
 for (let i = 0; i < numVertices; i++) {
     if (!visited[i]) {
         dfs(i);
     }
 }
 
 // Return vertices in topological order (reverse of stack)
 return stack.reverse();
}

function topologicalSortKahns(adjList, numVertices) {
 /**
  * Topological sort using Kahn's algorithm (BFS approach)
  * 
  * @param {Array} adjList - Adjacency list representation of the graph
  * @param {number} numVertices - Number of vertices in the graph
  * @returns {Array} - Array containing topological order, empty if cycle exists
  */
 // Calculate indegree for each vertex
 const indegree = new Array(numVertices).fill(0);
 for (let u = 0; u < numVertices; u++) {
     for (const v of adjList[u]) {
         indegree[v]++;
     }
 }
 
 // Initialize queue with vertices having 0 indegree
 const queue = [];
 for (let i = 0; i < numVertices; i++) {
     if (indegree[i] === 0) {
         queue.push(i);
     }
 }
 
 const topoOrder = [];
 
 // Process vertices in BFS manner
 while (queue.length > 0) {
     const vertex = queue.shift();
     topoOrder.push(vertex);
     
     // Decrease indegree of adjacent vertices
     for (const neighbor of adjList[vertex]) {
         indegree[neighbor]--;
         if (indegree[neighbor] === 0) {
             queue.push(neighbor);
         }
     }
 }
 
 // Check if all vertices are included (no cycle)
 if (topoOrder.length !== numVertices) {
     return []; // Graph has a cycle
 }
 
 return topoOrder;
}

// Example usage
function main() {
 // Example DAG
 const numVertices = 6;
 const adjList = [
     [2, 3],    // 0 → 2, 3
     [4],       // 1 → 4
     [1, 3],    // 2 → 1, 3
     [1],       // 3 → 1
     [],        // 4 → none
     [1, 4]     // 5 → 1, 4
 ];
 
 console.log("Using DFS approach:");
 const resultDFS = topologicalSortDFS(adjList, numVertices);
 console.log("Topological Order:", resultDFS);
 
 console.log("\nUsing Kahn's algorithm:");
 const resultKahns = topologicalSortKahns(adjList, numVertices);
 if (resultKahns.length > 0) {
     console.log("Topological Order:", resultKahns);
 } else {
     console.log("Graph contains a cycle");
 }
}

main();

// Output: Topological Order: [5, 0, 2, 3, 1, 4]

Time Complexity

DFS Traversal:

The dfs function visits each node and explores all its outgoing edges.
For a graph with V vertices and E edges, the DFS traversal will visit each vertex once and explore each edge once.
The time complexity of DFS is O(V + E).

Topological Sort:

The topologicalSort function iterates over all the vertices and performs DFS on any unvisited vertex. Each DFS visit will add vertices to a stack and eventually form the topological order.
So, the overall time complexity for the entire topological sort process is O(V + E).

Time Complexity: O(V + E)

Space Complexity

Visited Array:

We maintain a visited array of size V, which takes O(V) space.

Adjacency List:

The adjacency list adj is of size V, and each list inside it holds edges for the corresponding vertex. The total space taken by the adjacency list is O(V + E).

Stack:

The stack stores the vertices as we process them in DFS. In the worst case, the stack will hold all V vertices at once. So, it requires O(V) space.

Result Array:

The ans array stores the topological order, which also takes O(V) space.

Space Complexity: O(V + E)