Kahn’s Algorithm

Kahn’s algorithm, also known as Kahn’s topological sorting algorithm, is an efficient algorithm used to sort directed acyclic graphs (DAGs) topologically. DAGs are graphs that contain directed edges between nodes but do not contain any cycles.

Topological sorting arranges nodes in a DAG so that every directed edge points from a node earlier in the sequence to a node later in the series. Topological sorting is helpful in many applications, including task scheduling, dependency resolution, and code compilation.

Algorithm

Kahn’s algorithm works by repeatedly selecting nodes with no incoming edges, removing them from the graph, and adding them to the sorted sequence. This process continues until all nodes have been added to the queue. The algorithm can be summarized in the following steps:

1. Initialize a list of nodes with no incoming edges, called S.
2. Initialize an empty list to hold the sorted nodes, called L.
3. While S is not empty, do the following: a. Remove a node n from S. b. Add n to L. c. For each node m with an edge e from n to m, remove the edge e from the graph. d. If m has no other incoming edges, add m to S.
4. If the graph still contains edges, it has at least one cycle then the algorithm terminates.

Pseudocode

function topologicalSort(graph):
    S = set of all nodes with no incoming edges
    L = empty list to hold the sorted nodes

    while S is not empty:
        remove a node n from S
        add n to L
        for each node m with an edge e from n to m:
            remove edge e from the graph
            if m has no other incoming edges, add m to S

    if graph still contains edges, then it must contain at least one cycle
    return L

Note that the graph should be represented as an adjacency list or matrix, where each node ‘n’ is associated with a list of nodes that has edges too. The set ‘S’ can be implemented as a queue, stack, or any other data structure that supports the efficient removal of elements.

Code

import java.util.*;

public class TopologicalSort {
    public static List<String> topologicalSort(Map<String, List<String>> graph) {
        // Step 1: Initialize S with nodes with no incoming edges
        Map<String, Integer> inDegrees = new HashMap<>();
        for (String node : graph.keySet()) {
            inDegrees.put(node, 0);
        }
        for (String node : graph.keySet()) {
            for (String neighbor : graph.get(node)) {
                inDegrees.put(neighbor, inDegrees.get(neighbor) + 1);
            }
        }
        Queue<String> S = new LinkedList<>();
        for (String node : inDegrees.keySet()) {
            if (inDegrees.get(node) == 0) {
                S.offer(node);
            }
        }

        // Step 2: Initialize an empty list to hold the sorted nodes
        List<String> L = new ArrayList<>();

        // Step 3: Remove nodes from S and add them to L
        while (!S.isEmpty()) {
            String node = S.poll();
            L.add(node);
            for (String neighbor : graph.get(node)) {
                inDegrees.put(neighbor, inDegrees.get(neighbor) - 1);
                if (inDegrees.get(neighbor) == 0) {
                    S.offer(neighbor);
                }
            }
        }

        // Step 4: Check if the graph contains cycles
        if (L.size() != graph.size()) {
            throw new IllegalArgumentException("Graph contains a cycle");
        }

        return L;
    }
}

function topologicalSort(graph) {
  // Step 1: Initialize S with nodes with no incoming edges
  const inDegrees = {};
  for (const node in graph) {
    inDegrees[node] = 0;
  }
  for (const node in graph) {
    for (const neighbor of graph[node]) {
      inDegrees[neighbor]++;
    }
  }
  const S = [];
  for (const node in inDegrees) {
    if (inDegrees[node] === 0) {
      S.push(node);
    }
  }

  // Step 2: Initialize an empty list to hold the sorted nodes
  const L = [];

  // Step 3: Remove nodes from S and add them to L
  while (S.length > 0) {
    const node = S.shift();
    L.push(node);
    for (const neighbor of graph[node]) {
      inDegrees[neighbor]--;
      if (inDegrees[neighbor] === 0) {
        S.push(neighbor);
      }
    }
  }

  // Step 4: Check if the graph contains cycles
  if (L.length !== Object.keys(graph).length) {
    throw new Error('Graph contains a cycle');
  }

  return L;
}

from collections import deque

def topological_sort(graph):
    # Step 1: Initialize S with nodes with no incoming edges
    in_degrees = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degrees[neighbor] += 1
    S = deque([node for node in in_degrees if in_degrees[node] == 0])

    # Step 2: Initialize an empty list to hold the sorted nodes
    L = []

    # Step 3: Remove nodes from S and add them to L
    while S:
        node = S.popleft()
        L.append(node)
        for neighbor in graph[node]:
            in_degrees[neighbor] -= 1
            if in_degrees[neighbor] == 0:
                S.append(neighbor)

    # Step 4: Check if the graph contains cycles
    if len(L) != len(graph):
        raise ValueError("Graph contains a cycle")

    return L

The function takes in a graph represented as a dictionary where each key is a node and the corresponding value is a list of nodes that it has edges too. The function returns a list of nodes in topological order.

Get Anubhav Singh Guleria’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Note that the in_degrees the dictionary is used to keep track of the number of incoming edges for each node, and nodes with zero incoming edges are added to the queue S. The while loop removes nodes from the queue S adds them to the list L and updates the in_degrees dictionary for their neighbours. If a node's incoming edge count becomes zero, it is added to S. If the length of L is not equal to the number of nodes in the graph, then the graph contains a cycle and an error is raised.

Complexity

The time complexity of Kahn’s algorithm is O(|V|+|E|), where |V| is the number of nodes in the graph and |E| is the number of edges. This makes the algorithm very efficient for large graphs.

Kahn’s algorithm is popular and widely used for topological sorting due to its simplicity and efficiency. It is also a great example of a graph algorithm that uses breadth-first search (BFS) to efficiently traverse the graph and identify nodes with no incoming edges.