Topological Sort in Graph

Welcome to our beginner's guide to Topological Sort in Graph Theory! Topological Sort is an essential algorithm used to order the vertices of a directed graph such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. Let's explore this important concept together!

Understanding the Problem Statement

Before delving into Topological Sort, let's understand the problem it addresses. Consider a scenario where tasks depend on one another; for example, in a project where certain tasks must be completed before others can begin. Such dependencies can be modeled using directed graphs, where nodes represent tasks and directed edges represent dependencies between tasks.

The goal of Topological Sort is to find a linear ordering of the vertices of the graph such that for every directed edge uv, the vertex u comes before the vertex v in the ordering. This ordering provides a sequence in which the tasks can be performed without violating any dependencies.

What is Topological Sort?

Topological Sort is an algorithm used to order the vertices of a directed graph in a linear sequence based on their dependencies. It helps in determining a valid sequence of tasks or events that respects all dependencies.

Topological Sort is primarily used in scenarios where there is a partial ordering among elements, such as scheduling tasks, resolving dependencies in software builds, and analyzing precedence constraints in job scheduling.

How does Topological Sort Work?

Topological Sort can be achieved using Depth-First Search (DFS) or Breadth-First Search (BFS) algorithms. The key idea is to visit the vertices of the graph in a particular order that respects the directed edges.

The algorithm follows these steps:

  1. Start with an empty result list to store the topological ordering.
  2. Perform a depth-first search (DFS) or breadth-first search (BFS) on the graph.
  3. During the traversal, visit each vertex and explore its neighbors.
  4. After visiting all neighbors of a vertex, add the vertex to the beginning of the result list.
  5. The final result list represents the topological ordering of the graph.

Topological Sort Example using BFS (Kahn's Algorithm)

Using Kahn's Algorithm for topological sorting on the following directed acyclic graph (DAG):


    50
    ↓   ↑
    234

Topological Sorting Steps:

  1. Identify vertices with no incoming edges. Initially, vertices 5 and 3.
  2. Enqueue 5 and 3 into the queue.
  3. Dequeue 5, add it to the topological order, and remove all outgoing edges.
  4. Topological Order: [5]
  5. Dequeue 3, add it to the topological order, and remove all outgoing edges.
  6. Topological Order: [5, 3]
  7. Now, vertex 2 has no incoming edges. Enqueue and dequeue 2, add to topological order.
  8. Topological Order: [5, 3, 2]
  9. Finally, vertex 0 and 4 have no incoming edges. Add them to the topological order.
  10. Topological Order: [5, 3, 2, 0, 4]
  11. The final topological order is [5, 3, 2, 0, 4].

Topological Sort Example using DFS

Demonstrating topological sorting using DFS on the same directed acyclic graph (DAG).


    50
    ↓   ↑
    234

Topological Sorting Steps:

  1. Perform DFS starting from each unvisited vertex. Begin with vertex 5.
  2. Visit vertex 5, then move to its unvisited neighbor 2.
  3. Visit vertex 2, then move to its unvisited neighbor 4.
  4. Vertex 4 has no unvisited neighbors. Add 4 to the result list.
  5. Topological Order: [4]
  6. Backtrack to vertex 2. Add 2 to the result list.
  7. Topological Order: [4, 2]
  8. Backtrack to vertex 5. Visit vertex 0.
  9. Vertex 0 leads to 3, which has no unvisited neighbors. Add 3 and then 0 to the result list.
  10. Topological Order: [4, 2, 3, 0]
  11. Finally, add 5 to the result list.
  12. Topological Order: [4, 2, 3, 0, 5]
  13. The final topological order is [4, 2, 3, 0, 5].
Example Application of Topological Sort

Let's consider a project management scenario where tasks are represented as vertices in a directed graph, and dependencies between tasks are represented as directed edges. By performing a Topological Sort on the graph, we can determine a valid sequence of tasks that respects all dependencies, ensuring that dependent tasks are completed before the tasks that depend on them.

Implementing Topological Sort in Code

Now, let's take a look at how we can implement Topological Sort in code. We'll provide examples in several programming languages to help you get started:


package codeKatha;

import java.util.*;

public class TopologicalSort {

    public List<Integer> topologicalSortDFS(Graph graph) {
    
        Stack<Integer> stack = new Stack<>();
        Set<Integer> visited = new HashSet<>();

        for (int vertex : graph.getVertices()) {
            if (!visited.contains(vertex)) {
                dfs(vertex, graph, stack, visited);
            }
        }

        List<Integer> result = new ArrayList<>();
        
        while (!stack.isEmpty()) {
            result.add(stack.pop());
        }
        return result;
    }

    private void dfs(int vertex, Graph graph, Stack<Integer> stack, Set<Integer> visited) {
    
        visited.add(vertex);
        
        for (int neighbor : graph.getNeighbors(vertex)) {
        
            if (!visited.contains(neighbor)) {
                dfs(neighbor, graph, stack, visited);
            }
        }
        
        stack.push(vertex);
    }

    public List<Integer> topologicalSortBFS(Graph graph) {
    
        Queue<Integer> queue = new LinkedList<>();
        Map<Integer, Integer> inDegree = new HashMap<>();

        // Calculate in-degrees of all vertices
        for (int vertex : graph.getVertices()) {
            inDegree.put(vertex, 0);
        }
        for (int vertex : graph.getVertices()) {
            for (int neighbor : graph.getNeighbors(vertex)) {
                inDegree.put(neighbor, inDegree.get(neighbor) + 1);
            }
        }

        // Enqueue vertices with in-degree 0
        for (int vertex : inDegree.keySet()) {
            if (inDegree.get(vertex) == 0) {
                queue.add(vertex);
            }
        }

        List<Integer> result = new ArrayList<>();
        
        // Perform BFS
        while (!queue.isEmpty()) {
        
            int vertex = queue.poll();
            result.add(vertex);
            
            for (int neighbor : graph.getNeighbors(vertex)) {
            
                inDegree.put(neighbor, inDegree.get(neighbor) - 1);
                
                if (inDegree.get(neighbor) == 0) {
                    queue.add(neighbor);
                }
            }
        }

        return result.size() == graph.getVertices().size() ? result : new ArrayList<>(); // Graph contains a cycle
    }
}

#include <iostream>
#include <stack>
#include <vector>
#include <unordered_set>
#include "Graph.h"

class TopologicalSort {
public:
    std::vector<int> topologicalSortDFS(Graph& graph) {
    
        std::stack<int> stack;
        std::unordered_set<int> visited;

        for (int vertex : graph.getVertices()) {
        
            if (visited.find(vertex) == visited.end()) {
                dfs(vertex, graph, stack, visited);
            }
        }

        std::vector<int> result;
        
        while (!stack.empty()) {
        
            result.push_back(stack.top());
            stack.pop();
        }
        return result;
    }

private:
    void dfs(int vertex, Graph& graph, std::stack<int>& stack, std::unordered_set<int>& visited) {
    
        visited.insert(vertex);
        
        for (int neighbor : graph.getNeighbors(vertex)) {
        
            if (visited.find(neighbor) == visited.end()) {
                dfs(neighbor, graph, stack, visited);
            }
        }
        stack.push(vertex);
    }

    std::vector<int> topologicalSortBFS(Graph& graph) {
        std::queue<int> queue;
        std::unordered_map<int, int> inDegree;

        // Calculate in-degrees of all vertices
        for (int vertex : graph.getVertices()) {
            inDegree[vertex] = 0;
        }
        for (int vertex : graph.getVertices()) {
            for (int neighbor : graph.getNeighbors(vertex)) {
                inDegree[neighbor]++;
            }
        }

        // Enqueue vertices with in-degree 0
        for (auto& pair : inDegree) {
            if (pair.second == 0) {
                queue.push(pair.first);
            }
        }

        std::vector<int> result;
        // Perform BFS
        while (!queue.empty()) {
        
            int vertex = queue.front();
            queue.pop();
            result.push_back(vertex);
            
            for (int neighbor : graph.getNeighbors(vertex)) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    queue.push(neighbor);
                }
            }
        }

        return result.size() == graph.getVertices().size() ? result : std::vector<int>{}; // Graph contains a cycle
    }
};

class TopologicalSort:
    def topological_sort_dfs(self, graph):
        stack = []
        visited = set()

        def dfs(vertex):
        
            visited.add(vertex)
            for neighbor in graph.get_neighbors(vertex):
                if neighbor not in visited:
                    dfs(neighbor)
            stack.append(vertex)

        for vertex in graph.get_vertices():
            if vertex not in visited:
                dfs(vertex)

        return stack[::-1]

    def topological_sort_bfs(self, graph):
    
        in_degree = {vertex: 0 for vertex in graph.get_vertices()}
        queue = collections.deque()

        for vertex in graph.get_vertices():
            for neighbor in graph.get_neighbors(vertex):
                in_degree[neighbor] += 1

        for vertex, degree in in_degree.items():
            if degree == 0:
                queue.append(vertex)

        result = []
        while queue:
            current_vertex = queue.popleft()
            result.append(current_vertex)
            for neighbor in graph.get_neighbors(current_vertex):
                in_degree[neighbor] -= 1
                if in_degree[neighbor] == 0:
                    queue.append(neighbor)

        if len(result) != len(graph.get_vertices()):
            return []

        return result



class TopologicalSort {
    topologicalSortDFS(graph

) {
        const stack = [];
        const visited = new Set();

        const dfs = (vertex) => {
            visited.add(vertex);
            for (let neighbor of graph.getNeighbors(vertex)) {
                if (!visited.has(neighbor)) {
                    dfs(neighbor);
                }
            }
            stack.push(vertex);
        };

        for (let vertex of graph.getVertices()) {
            if (!visited.has(vertex)) {
                dfs(vertex);
            }
        }

        return stack.reverse();
    }

    topologicalSortBFS(graph) {
    
        const inDegree = new Map();
        const queue = [];

        // Calculate in-degrees of all vertices
        for (let vertex of graph.getVertices()) {
            inDegree.set(vertex, 0);
        }
        for (let vertex of graph.getVertices()) {
            for (let neighbor of graph.getNeighbors(vertex)) {
                inDegree.set(neighbor, inDegree.get(neighbor) + 1);
            }
        }

        // Enqueue vertices with in-degree 0
        for (let [vertex, degree] of inDegree) {
            if (degree === 0) {
                queue.push(vertex);
            }
        }

        const result = [];
        // Perform BFS
        while (queue.length > 0) {
        
            const currentVertex = queue.shift();
            result.push(currentVertex);
            
            for (let neighbor of graph.getNeighbors(currentVertex)) {
            
                inDegree.set(neighbor, inDegree.get(neighbor) - 1);
                if (inDegree.get(neighbor) === 0) {
                    queue.push(neighbor);
                }
            }
        }

        return result.length === graph.getVertices().size ? result : []; // Graph contains a cycle
    }
}

Graph: Concept and Important Algorithms

1. Basics of Graph Data Structure
2. Breadth-First Search (BFS) in Graph
3. Depth-First Search (DFS) in Graph 
4. Topological Sort in Graph
5. Union-Find Algorithm in Graph
6. Prim's Algorithm in Graph 
7. Dijkstra's Algorithm in Graph
8. Kruskal's Algorithm in Graph

Congratulations! You've now learned the basics of Topological Sort in graph theory. Feel free to experiment with the provided code examples and explore further applications of Topological Sort in your projects.

Comments

Popular Posts on Code Katha

Java Interview Questions for 10 Years Experience

Spring Boot Interview Questions for 10 Years Experience

Sql Interview Questions for 10 Years Experience

Visual Studio Code setup for Java and Spring with GitHub Copilot

Spring Data JPA

Java interview questions - Must to know concepts

Data Structures & Algorithms Tutorial with Coding Interview Questions

Elasticsearch Java Spring Boot

Spring Boot Kafka Tutorial