Topological Sorting (Kahn's Algorithm) 🎯

Welcome to this exciting lesson on Topological Sorting using Kahn's Algorithm! This powerful tool is a graph traversal technique used to find a linear ordering of the vertices in a directed acyclic graph (DAG) that is topologically sorted. Let's dive in! 🏊‍♂️

What is Topological Sorting? 📝

In simple terms, Topological Sorting is an ordering of vertices in a directed graph such that for every directed edge u -> v, vertex u comes before v in the ordering. This ordering is not possible for graphs with cycles, hence the requirement for a directed acyclic graph (DAG).

Why is it Important? 💡

Topological Sorting is essential in various real-world applications such as scheduling tasks, dependency resolution, and course selection. It helps in identifying dependencies and ensuring they are met in the correct order.

Understanding Kahn's Algorithm 📝

Kahn's Algorithm is an efficient method for topological sorting. It works by identifying vertices with no incoming edges (also known as source vertices) and processing them first. These vertices can be processed safely as they do not have any dependencies.

Steps of Kahn's Algorithm 📝

Initialize: Create an empty list for the sorted order, sorted_order, and a count for the number of vertices with no incoming edges, indegree_count.
Calculate Indegrees: Count the incoming edges for each vertex. A vertex with no incoming edges has an indegree of 0.
Sort Vertices: Sort the vertices based on their indegrees. Vertices with an indegree of 0 should be at the front of the list.
Process Vertices: Starting from the front of the sorted list, process each vertex with an indegree of 0. Decrease the indegree of each vertex that depends on the processed vertex. If a vertex's indegree becomes 0, add it to the front of the sorted list.
Check Cycle: If there is a vertex with a non-zero indegree and no more vertices with an indegree of 0, there is a cycle in the graph, and topological sorting is not possible.
Completion: Once all vertices have been processed, the sorted order is complete.

Code Examples 💡

Here are two examples in Python and Java to help you understand Kahn's Algorithm better.

Python Example ✅

python

from collections import defaultdict

def topological_sort(vertices, edges):
    indegrees = defaultdict(int)
    graph = defaultdict(list)

    for vertex, neighbor in edges:
        indegrees[vertex] += 1
        graph[neighbor].append(vertex)

    sorted_order = []

    zero_indegree_vertices = [vertex for vertex in vertices if indegrees[vertex] == 0]

    while zero_indegree_vertices:
        current_vertex = zero_indegree_vertices.pop()
        sorted_order.append(current_vertex)

        for neighbor in graph[current_vertex]:
            indegrees[neighbor] -= 1
            if indegrees[neighbor] == 0:
                zero_indegree_vertices.append(neighbor)

    return sorted_order

Java Example ✅

java

import java.util.*;

public class TopologicalSort {
    private Map<Integer, List<Integer>> graph;
    private Map<Integer, Integer> indegrees;

    public TopologicalSort(int[][] edges) {
        this.graph = new HashMap<>();
        this.indegrees = new HashMap<>();

        for (int[] edge : edges) {
            int vertex = edge[1];
            if (!indegrees.containsKey(vertex)) {
                indegrees.put(vertex, 0);
            }
            int neighbor = edge[0];
            if (!graph.containsKey(neighbor)) {
                graph.put(neighbor, new ArrayList<>());
            }
            graph.get(neighbor).add(vertex);
            indegrees.put(vertex, indegrees.getOrDefault(vertex, 0) + 1);
        }
    }

    public List<Integer> topologicalSort() {
        List<Integer> sortedOrder = new ArrayList<>();

        List<Integer> zeroIndegreeVertices = new ArrayList<>(indegrees.keySet());

        while (!zeroIndegreeVertices.isEmpty()) {
            int currentVertex = findMinIndegree(zeroIndegreeVertices);
            sortedOrder.add(currentVertex);
            zeroIndegreeVertices.remove(currentVertex);

            for (Integer neighbor : graph.get(currentVertex)) {
                indegrees.put(neighbor, indegrees.get(neighbor) - 1);
                if (indegrees.get(neighbor) == 0) {
                    zeroIndegreeVertices.add(neighbor);
                }
            }
        }

        if (sortedOrder.size() != indegrees.keySet().size()) {
            throw new IllegalStateException("Graph has a cycle");
        }

        return sortedOrder;
    }

    private int findMinIndegree(List<Integer> vertices) {
        int minIndegree = Integer.MAX_VALUE;
        int result = -1;

        for (Integer vertex : vertices) {
            if (indegrees.get(vertex) < minIndegree) {
                minIndegree = indegrees.get(vertex);
                result = vertex;
            }
        }

        return result;
    }
}

Quiz 💡

Happy coding and learning! 🚀