Skip to main content

Topological Sort (Geeks for Geeks)

1. What is Topological Sort?​

Topological Sort is a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge u -> v, vertex u comes before v in the ordering.

2. Algorithm for Topological Sort​

  1. Identify vertices with no incoming edges (indegree 0).
  2. Remove these vertices and their outgoing edges from the graph.
  3. Repeat steps 1 and 2 until all vertices are removed.
  4. If the graph has a cycle, topological sort is not possible.

3. How does Topological Sort work?​

  • It repeatedly removes nodes with no incoming edges, adding them to the sorted list.
  • It ensures that each node is processed only after all its dependencies are processed.

4. Problem Description​

Given a Directed Acyclic Graph (DAG), implement the Topological Sort algorithm to order the vertices.

5. Examples​

Example 1:

Input: Graph with edges [(5, 2), (5, 0), (4, 0), (4, 1), (2, 3), (3, 1)]
Output: [5, 4, 2, 3, 1, 0] or [4, 5, 2, 3, 1, 0]

Example 2:

Input: Graph with edges [(1, 2), (2, 3), (3, 4)]
Output: [1, 2, 3, 4]

Explanation of Example 1:

  • The graph can be visualized as:
5 → 2 → 3 → 1
5 → 0
4 → 0
4 → 1
  • One valid topological ordering is [5, 4, 2, 3, 1, 0].

6. Constraints​

  • The graph must be a Directed Acyclic Graph (DAG).

7. Implementation​

Python

from collections import defaultdict, deque

def topological_sort(vertices, edges):
    graph = defaultdict(list)
    indegree = {i: 0 for i in range(vertices)}

    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    queue = deque([v for v in range(vertices) if indegree[v] == 0])
    topo_order = []

    while queue:
        node = queue.popleft()
        topo_order.append(node)
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    if len(topo_order) == vertices:
        return topo_order
    else:
        return []

C++

  #include <iostream>
  #include <vector>
  #include <queue>

  void topologicalSort(int vertices, const std::vector<std::pair<int, int>>& edges) {
  std::vector<int> indegree(vertices, 0);
  std::vector<std::vector<int>> graph(vertices);

  // Build the graph and compute indegrees of all vertices
  for (const auto& edge : edges) {
      graph[edge.first].push_back(edge.second);
      indegree[edge.second]++;
  }

  std::queue<int> q;
  // Enqueue all vertices with indegree 0
  for (int i = 0; i < vertices; i++) {
      if (indegree[i] == 0) {
          q.push(i);
      }
  }

  std::vector<int> topo_order;
  while (!q.empty()) {
      int node = q.front();
      q.pop();
      topo_order.push_back(node);

      // Reduce the indegree of the neighbors
      for (int neighbor : graph[node]) {
          indegree[neighbor]--;
          if (indegree[neighbor] == 0) {
              q.push(neighbor);
          }
      }
  }

  // Check if there was a cycle
  if (topo_order.size() == vertices) {
      for (int node : topo_order) {
          std::cout << node << " ";
      }
  } else {
      std::cout << "Cycle detected, topological sort not possible.";
  }
}

int main() {
  int vertices = 6;
  std::vector<std::pair<int, int>> edges = {{5, 2}, {5, 0}, {4, 0}, {4, 1}, {2, 3}, {3, 1}};
  topologicalSort(vertices, edges);
  return 0;
}

Java

import java.util.*;

public class TopologicalSort {
    public static List<Integer> topologicalSort(int vertices, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        int[] indegree = new int[vertices];
        for (int i = 0; i < vertices; i++) {
            graph.add(new ArrayList<>());
        }

        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            indegree[edge[1]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < vertices; i++) {
            if (indegree[i] == 0) {
                queue.add(i);
            }
        }

        List<Integer> topo_order = new ArrayList<>();
        while (!queue.isEmpty()) {
            int node = queue.poll();
            topo_order.add(node);
            for (int neighbor : graph.get(node)) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    queue.add(neighbor);
                }
            }
        }

        if (topo_order.size() == vertices) {
            return topo_order;
        } else {
            return Collections.emptyList(); // Cycle detected
        }
    }

JavaScript

 function topologicalSort(vertices, edges) {
      let graph = Array.from({ length: vertices }, () => []);
      let indegree = Array(vertices).fill(0);
  for (let [u, v] of edges) {
      graph[u].push(v);
      indegree[v]++;
  }

  let queue = [];
  for (let i = 0; i < vertices; i++) {
      if (indegree[i] === 0) {
          queue.push(i);
      }
  }

  let topoOrder = [];
  while (queue.length > 0) {
      let node = queue.shift();
      topoOrder.push(node);

      for (let neighbor of graph[node]) {
          indegree[neighbor]--;
          if (indegree[neighbor] === 0) {
              queue.push(neighbor);
          }
      }
  }

  return topoOrder.length === vertices ? topoOrder : []; // Return empty array if cycle detected
}

8. Complexity Analysis​

  • Time Complexity:

  • Best case: O(V+E)O(V + E)

  • Average case: O(V+E)O(V + E)

  • Worst case: O(V+E)O(V + E)

  • Space Complexity: O(V+E)O(V + E) (for the graph representation and auxiliary data structures)

9. Advantages and Disadvantages​

Advantages:

  • Provides a linear ordering of vertices in a DAG.
  • Useful in scenarios such as task scheduling, resolving symbol dependencies in linkers, etc.

Disadvantages:

  • Not applicable if the graph contains cycles.
  • Requires graph to be a DAG.

10. References​