Topological Sort

tutorials

Given a directed acyclic graph (DAG), write a program to perform Topological Sort. Topological sorting for a graph is a linear ordering of its vertices such that for every directed edge u → v, vertex u comes before v in the ordering. Topological sorting is only possible for Directed Acyclic Graphs (DAGs).

Input/Output Examples

plaintext
Example 1:
Input: 
5 - > 0
5 - > 2
4 - > 0
4 - > 1
2 - > 3
3 - > 1
Output:  5 4 2 3 1 0

Explanation: 
One possible topological ordering of the vertices is 
5 - > 4 - > 2 - > 3 - > 1 - > 0
 
Example 2: 
Input: 
6 - > 1
6 - > 3
5 - > 1
5 - > 2
3 - > 4
4 - > 2
 
Output: 6 5 3 4 2 1
Explanation: 
One possible topological ordering of the vertices is 
6 - > 5 - > 3 - > 4 - >2 - >1

Approach to Implement Topological Sort

  1. Graph Representation:
    • We represent a graph using an adjacency list, where each node points to a list of its adjacent nodes (neighbors).
    • The graph must be a Directed Acyclic Graph (DAG) for topological sorting to be valid.
  2. Depth First Search (DFS) Approach:
    • We can perform topological sorting using DFS. The idea is to process each vertex and mark it as visited, then recursively visit all of its neighbors.
    • When all neighbors of a node have been processed, we add the node to the result stack. This ensures that each node is placed after all its dependencies (i.e., nodes pointing to it) in the ordering.
  3. Stack-Based Approach:
    • We use a stack to store the topological order. When a node has been fully processed (all its neighbors have been visited), it is pushed onto the stack.
    • After completing the DFS traversal of all nodes, we can pop the elements from the stack to get the topological order.
  4. Edge Cases:
    • If the graph contains a cycle, topological sorting is not possible (but for this problem, the graph is assumed to be a DAG).

C++ Program to Implement Topological Sort

cpp
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

// Function to perform DFS and store topological sort in stack
void topologicalSortUtil(int node, vector<int> adj[], vector<bool>& visited, stack<int>& Stack) {
    visited[node] = true;

    // Recursively visit all the neighbors of the current node
    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            topologicalSortUtil(neighbor, adj, visited, Stack);
        }
    }

    // Push the current node to the stack after all its neighbors are processed
    Stack.push(node);
}

// Function to perform topological sorting
void topologicalSort(int V, vector<int> adj[]) {
    stack<int> Stack;
    vector<bool> visited(V, false);

    // Perform DFS on all vertices
    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            topologicalSortUtil(i, adj, visited, Stack);
        }
    }

    // Print the topological sort by popping elements from the stack
    while (!Stack.empty()) {
        cout << Stack.top() << " ";
        Stack.pop();
    }
    cout << endl;
}

int main() {
    // Number of vertices
    int V = 6;

    // Create an adjacency list for the graph
    vector<int> adj[V];

    // Adding directed edges (DAG)
    adj[5].push_back(0);
    adj[5].push_back(2);
    adj[4].push_back(0);
    adj[4].push_back(1);
    adj[2].push_back(3);
    adj[3].push_back(1);

    // Perform Topological Sort
    cout << "Topological Sort of the graph: ";
    topologicalSort(V, adj);

    return 0;
}

Java Program to Implement Topological Sort

java
import java.util.*;

// Topological Sort using DFS in a Directed Acyclic Graph (DAG)
public class TopologicalSort {

    // Function to perform DFS and store topological sort in stack
    private static void topologicalSortUtil(int node, List<List<Integer>> adj, boolean[] visited, Stack<Integer> stack) {
        visited[node] = true;

        // Recursively visit all the neighbors of the current node
        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor]) {
                topologicalSortUtil(neighbor, adj, visited, stack);
            }
        }

        // Push the current node to the stack after all its neighbors are processed
        stack.push(node);
    }

    // Function to perform topological sorting
    public static void topologicalSort(int V, List<List<Integer>> adj) {
        Stack<Integer> stack = new Stack<>();
        boolean[] visited = new boolean[V];

        // Perform DFS on all vertices
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                topologicalSortUtil(i, adj, visited, stack);
            }
        }

        // Print the topological sort by popping elements from the stack
        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Number of vertices
        int V = 6;

        // Create an adjacency list for the graph
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }

        // Adding directed edges (DAG)
        adj.get(5).add(0);
        adj.get(5).add(2);
        adj.get(4).add(0);
        adj.get(4).add(1);
        adj.get(2).add(3);
        adj.get(3).add(1);

        // Perform Topological Sort
        System.out.print("Topological Sort of the graph: ");
        topologicalSort(V, adj);
    }
}

Python Program to Implement Topological Sort

python
# Function to perform DFS and store topological sort in stack
def topological_sort_util(node, adj, visited, stack):
    visited[node] = True

    # Recursively visit all the neighbors of the current node
    for neighbor in adj[node]:
        if not visited[neighbor]:
            topological_sort_util(neighbor, adj, visited, stack)

    # Push the current node to the stack after all its neighbors are processed
    stack.append(node)

# Function to perform topological sorting
def topological_sort(V, adj):
    stack = []
    visited = [False] * V

    # Perform DFS on all vertices
    for i in range(V):
        if not visited[i]:
            topological_sort_util(i, adj, visited, stack)

    # Print the topological sort by popping elements from the stack
    while stack:
        print(stack.pop(), end=" ")
    print()

# Example usage
if __name__ == "__main__":
    # Number of vertices
    V = 6

    # Create an adjacency list for the graph
    adj = [[] for _ in range(V)]

    # Adding directed edges (DAG)
    adj[5].append(0)
    adj[5].append(2)
    adj[4].append(0)
    adj[4].append(1)
    adj[2].append(3)
    adj[3].append(1)

    # Perform Topological Sort
    print("Topological Sort of the graph:", end=" ")
    topological_sort(V, adj)
  • Time Complexity: O(V + E) where V is the number of vertices and E is the number of edges. Each vertex and edge is processed once during the traversal.
  • Space Complexity: O(V) for the stack used in the DFS and the visited array
tools

DSA

Related Articles