Kahn’s Topological Sort Algorithm

Algorithms

Summary: In this tutorial, we will learn what Kahn’s Topological Sort algorithm is and how to obtain the topological ordering of the given graph using it.

Introduction to Topological Sort

Topological ordering of a directed graph is the ordering of its vertices such that for each directed edge from vertex A to vertex B, vertex A appears before vertex B in the ordering.

Topological Sort
One of the Topological orders of the given graph.

Topological sorting sorts vertices in such a way that every directed edge of the graph has the same direction.

It is important to note that the same graph may have different topological orders.

Topological ordering is only possible for the Directed Acyclic Graphs (i.e., DAG). Graph with cycles cannot be topologically sorted.

Kahn’s Algorithm for Topological Sort

Kahn’s algorithm in order to form topological order constantly looks for the vertices that have no incoming edge and removes all outgoing edges from them.

Basically, the algorithm:

  1. Finds the vertex that has no incoming edges.
  2. Remove all outgoing edges from that vertex.
  3. Add vertex to the topological order.
  4. Repeat the process until all the vertices are processed.
Khan's Topological Sort Algorithm
Illustration of Kahn’s Algorithm.
Note: The order may differ depending on which vertices are processed first.

Implementation of the Algorithm

In programming, to perform edge related operations, we use another graph property known as a degree.

A degree to a vertex is the number of incoming edges.

A degree represents how many incoming edges does a vertex has. A vertex with 0 degrees means no incoming edges.

We use Queue to process those vertices because it follows the First In First Out (FIFO) pattern.

To implement Kahn’s Topological Algorithm:

  1. We look for 0-degree vertices in the given graph and add them to the queue.
  2. We process the vertices one by one until the queue is emptied.
    1. We pop a vertex from the queue and add it in topological order.
    2. After that, we decrement the degree of all its adjacent vertices (apparently to remove the outgoing edges).
    3. We add it to the queue if the degree of any adjacent vertex is reduced to zero.
  3. Once all the vertices are processed, we print the order.

Here is the implementation of the algorithm in Python, C++ and Java:

Python

#class representing vertex of the graph
class Vertex:

  def __init__(self, name):
    #vertex label
    self.name = name
    #adjacency list
    self.neighbors = []
    #degree of the vertex
    self.degree = 0

  #method to add vertex to the adjacency list 
  #i.e., connect vertices (undirected)
  def add_neighbor(self, vertex):
    self.neighbors.append(vertex)

  #string representation of the class
  def __repr__(self):
    return self.name


class KahnsTopological:

  def __init__(self, vertices):
    self.vertices = vertices

  #method to initialize degree of every vertices
  def init_degree(self):
    for vertex in self.vertices:
      for nbr in vertex.neighbors:
        nbr.degree += 1

  #method to find the topological order of the graph
  #using the kahn's Topological sort algorithm
  def sort(self):
    #create an empty queue
    queue = []

    #fill queue with 0 degree vertices
    for vertex in self.vertices:
      if vertex.degree == 0:
        queue.append(vertex)

    #list to store topological order
    order = []

    #To store count of processed vertices
    count = 0 

    #run the algorithm until queue is empty
    while queue:
      #dequeue an vertex from the queue
      #and append to the order
      current_vertex = queue.pop(0)
      order.append(current_vertex)

      #decrement the degree of the connected vertices
      for nbr in current_vertex.neighbors:
        nbr.degree -= 1

        #if the degree reduces to 0
        #add it to the queue
        if nbr.degree == 0:
          queue.append(nbr)
      
      count =+ 1

    #algorithm has finished
    #if the number of processed vertices is greater-
    #than the number of vertices in the graph,
    #then it means the graph has a cycle
    if count > len(self.vertices):
      print("The graph has cycle")
    else:
      #output the topological order
      print(order)


if __name__ == '__main__':
  #vertices
  vertices = [Vertex('A'), Vertex('B'), Vertex('C'), Vertex('D'), Vertex('E'), Vertex('F')]
  
  #connect nodes (i.e. create graph)
  vertices[0].add_neighbor(vertices[2]); #A->C
  vertices[0].add_neighbor(vertices[1]); #A->B
  
  vertices[1].add_neighbor(vertices[3]); #B->D
  vertices[2].add_neighbor(vertices[3]); #C->D
  vertices[1].add_neighbor(vertices[4]); #B->E
  vertices[2].add_neighbor(vertices[5]); #C->F
  vertices[4].add_neighbor(vertices[5]); #E->F

  #driver code
  topological = KahnsTopological(vertices)
  topological.init_degree()
  topological.sort()

C++

#include <iostream>
#include<list>
#include<queue>
using namespace std;
 
//class representing a vertex of the graph
class Vertex{
public:
  //vertex label
  char name;
  //Adjacency List
  list<Vertex*> neighbors;
  //degree of the vertex
  int degree = 0;
  
 
  Vertex(char name){
    this->name = name;
  }
 
  //Method to connect vertices (directed)
  void add_neighbor(Vertex* v){
    this->neighbors.push_back(v);
  }
};
 

class KahnsTopological{
public:
  Vertex** vertices;
  int n;

  KahnsTopological(Vertex* vertices[], int n){
    this->vertices = vertices;
    this->n = n;
  }

  //method to initialize degree of every vertices
  void init_degree(){
    for(int i=0; i<n; i++){
      Vertex* vertex= vertices[i];
      for(Vertex* nbr: vertex->neighbors){
        nbr->degree += 1;
      }
    }
  }

  //method to find the topological order of the graph
  //using the kahn's Topological sort algorithm
  void sort(){
    //create an empty queue
    queue<Vertex*>  Queue;

    //fill queue with 0 degree vertices
    for(int i=0; i<n; i++){
      Vertex* vertex= vertices[i];
      if(vertex->degree == 0)
        Queue.push(vertex);
    }

    //list to store topological order
    list<Vertex*> order;

    //To store count of processed vertices
    int count = 0;

    //run the algorithm until queue is empty
    while(!Queue.empty()){
      //dequeue an vertex from the queue
      //and append to the order
      Vertex* current_vertex = Queue.front();
      Queue.pop();
      order.push_back(current_vertex);

      //decrement the degree of the connected vertices
      for(Vertex* nbr: current_vertex->neighbors){
        nbr->degree -= 1;

        //if the degree reduces to 0
        //add it to the queue
        if(nbr->degree == 0)
          Queue.push(nbr);
      }

      count++;
    }

    //algorithm has finished
    //if the number of processed vertices is greater-
    //than the number of vertices in the graph,
    //then it means the graph has a cycle
    if(count > n)
      cout << "The graph has cycle";
    else{
      //output the topological order
      for(Vertex* v: order){
        cout << v->name << " ";
      }
    }
  }
};


int main()
{
  //vertices
  Vertex* vertices[] = {new Vertex('A'), new Vertex('B'), new Vertex('C'), new Vertex('D'), new Vertex('E'), new Vertex('F')};
  
  //connect vertices (i.e. create graph)
  vertices[0]->add_neighbor(vertices[1]); //A->B
  vertices[0]->add_neighbor(vertices[2]); //A->C
  vertices[1]->add_neighbor(vertices[3]); //B->D
  vertices[2]->add_neighbor(vertices[3]); //C->D
  vertices[1]->add_neighbor(vertices[4]); //B->E
  vertices[2]->add_neighbor(vertices[5]); //C->F
  vertices[4]->add_neighbor(vertices[5]); //E->F
  
  //Driver Code
  KahnsTopological topological(vertices, 6);
  topological.init_degree();
  topological.sort();
}

Java

import java.util.*;
 
//class representing a vertex of the graph
class Vertex{
  //vertex label
  String name;
  //degree of the vertex
  int degree = 0;
  //Adjacency List
  List<Vertex> neighbors = new ArrayList<>();
  
 
  Vertex(String name){
    this.name = name;
  }
 
  //Method to connect vertices (directed)
  public void add_neighbor(Vertex v){
    this.neighbors.add(v);
  }

  public String toString(){
    return this.name;
  }
};
 


class KahnsTopological{

  Vertex vertices[];

  KahnsTopological(Vertex vertices[]){
    this.vertices = vertices;
  }

  //method to initialize degree of every vertices
  void init_degree(){
    for(Vertex vertex: vertices){
      for(Vertex nbr: vertex.neighbors){
        nbr.degree += 1;
      }
    }
  }

  //method to find the topological order of the graph
  //using the kahn's Topological sort algorithm
  void sort(){
    //create an empty queue
    Queue<Vertex>  queue = new LinkedList<>();

    //fill queue with 0 degree vertices
    for(Vertex vertex: vertices){
      if(vertex.degree == 0)
        queue.add(vertex);
    }

    //list to store topological order
    List<Vertex> order = new ArrayList<>();

    //To store count of processed vertices
    int count = 0;

    //run the algorithm until queue is empty
    while(!queue.isEmpty()){
      //dequeue an vertex from the queue
      //and append to the order
      Vertex current_vertex = queue.poll();
      order.add(current_vertex);

      //decrement the degree of the connected vertices
      for(Vertex nbr: current_vertex.neighbors){
        nbr.degree -= 1;

        //if the degree reduces to 0
        //add it to the queue
        if(nbr.degree == 0)
          queue.add(nbr);
      }

      count++;
    }

    //algorithm has finished
    //if the number of processed vertices is greater-
    //than the number of vertices in the graph,
    //then it means the graph has a cycle
    if(count > vertices.length)
      System.out.println("The graph has cycle");
    else{
      //output the topological order
      System.out.println(order);
    }
    
  }
}


class Main {
  public static void main(String[] args) {
  //vertices
  Vertex vertices[] = {new Vertex("A"), new Vertex("B"), new Vertex("C"), new Vertex("D"), new Vertex("E"), new Vertex("F")};
  
  //connect vertices (i.e. create graph)
  vertices[0].add_neighbor(vertices[1]); //A->B
  vertices[0].add_neighbor(vertices[2]); //A->C
  vertices[1].add_neighbor(vertices[3]); //B->D
  vertices[2].add_neighbor(vertices[3]); //C->D
  vertices[1].add_neighbor(vertices[4]); //B->E
  vertices[2].add_neighbor(vertices[5]); //C->F
  vertices[4].add_neighbor(vertices[5]); //E->F
  
  //Driver Code
  KahnsTopological topological = new KahnsTopological(vertices);
  topological.init_degree();
  topological.sort();
  }
}

Output:

Python: [A, C, B, D, E, F]
C++: [A, B, C, E, D, F]
Java: [A, B, C, E, D, F]


The order of different languages is not the same, yet all are correct.

The orders are such that for each directed edge from vertex A to vertex B, vertex A appears before vertex B in the ordering.

In the above programs, the init_degree() method calculates the degree of each vertex of a given graph. We have called this method before the sorting process.

If there is a cycle in the graph, some vertices will be processed several times. In that case, the count of processed vertices exceeds the number of vertices in the graph, and topological order is not possible.

In this tutorial, we learned to get the topological ordering of the vertices of the given graph using the Kahn’s Topological Sort Algorithm

Leave a Reply

Your email address will not be published. Required fields are marked *