Mastery of Kahn’s Algorithm, Topological Sorting, in an easily understandable manner with visualization

Express the problem

Hi Coding Rockstars,
Let’s dive into “Topological Sorting” again with super “Kahn’s Algorithm”. It’s a simpler approach that makes grasping the core of the problem much easier, promising a blog that surpasses the clarity of the previous one. And from the bottom of my heart, I’m pleased to have you here with me.

Introduction :

I’ve explained Topological Sorting before. If you haven’t checked our previous blogs, I strongly recommend Eyes on Once because you might get a super understanding of what Topo Ordering is, In Kahn’s first we find the “start nodes” that have no incoming edges and insert them into Queue, yes you have heard me right I confident you all know what is stack and BFS, we are going to achieve Kahn’s algorithm with BFS (Breath-First-Search) simple level-wise traversing,
Queue: First In First Out — -> example Ration shop

Edges:

Edges are like bridges, connecting other individual vertices or nodes

Example of the edges

No Incoming Edges:

No Chaos In a graph, “no incoming edges” Technical Term (Indegree) refers to a vertex or node that does not have any edges pointing towards it from other vertices.
No In — -> means Zero → no incoming edges from other vertices in this graph we got two — -> 0 indegree Vertices one is 4 and another one is 5.

Indegree examples

Kahn’s Algorithm:

What was the definition of the Topo if there is a connection between U and V, U Always appears before V in Linear ordering’s the definition of the Topo isn’t, so according to the above Visual 4 and 5 have 0 indegree which means no incoming edges so Obviously we know no one here before 4 and 5 it’s an individual vertex, so you can blindly place 4 and 5 in first position in your ordering lists.

In Kahn’s, we are going to find the in-degree of each node and store it in the visited array why? (Picture) then find who has in-degree 0 which means no incoming edges that push into the queue bag one thing in the entire problem is we should keep tracking who has 0 indegree because the core of the problem is we are going to decrease who has 1 or more indegree of each node.

In the introduction, I’ve told you to first find no incoming edges vertex and then push them into your queue bag, so in this picture we got two 0 Indegree vertex aren’t then pushed into the queue bag with those two zero Indegree vertex which means 4 and 5, then taking out the 4 and 5 why Marudhu? because 4 and 5 may have made some connection other vertices aren’t, like 4 and 5 were getting into someone, don’t be confused I’ll explain everything in the diagram,

Hey marudhu how can I find the Indegree of each vertex, In the question they give us an adjacency list, with adjList you can easily find the in-degree and store it in the visited array, if you checked out our last blogs you might know what visited array simple just monitoring each node indegrees the function of the visited array works same of any problems, but slightly different to monitoring the data, It’s very important term visited array in a graph space.

How To Find An Indegree Of Each Vertex:

• let adjacencyList = [[ ], [ ], [3], [1], [0, 1], [0, 2]] is an adjacency list representing a graph with 6 vertices (0 to 5)
• The outer loop(let i = 0; i < v; i++) goes through each vertex from 0 to 5.
• The inner loop for (let degreeIncreasing of adj[i]) goes through each neighbour of the current vertex [I] in the adjacency list.
• Inside the inner loop, indegree[degreeIncreasing]++ increments a counter for each neighbour. This Indegree array keeps track of **how many times each vertex is mentioned as a neighbour in the graph**.

Why Taking Out The Nodes From The Queue:

Why take out the node from the queue and why should remove the indegree of the node

What Is Adjacency List:

• Each node (or vertex) of the graph is represented by an array.
• The array contains a list of neighbours for that particular node.
• For a directed graph, each entry in the array corresponds to a vertex that the current vertex has an outgoing edge.
• For an undirected graph, each entry in the array corresponds to an adjacent vertex.

Visualization Of AdjList:

Adjacency List Representation

Core Kahn’s Algorithm:

1) Start by identifying nodes with zero in-degree (no incoming edges).
2) Process a node by decrementing the in-degrees of its neighbors.
3) Check if any of the neighbors now have zero in-degree and add them to the processing queue.
4) Repeat the process until all nodes are visited.
This algorithm is commonly used to find a topological ordering of a directed acyclic graph (DAG).

Code Showcase:

class solution {
  kahnsAlgo(v, adj) {
    let indegree = new Array(v).fill(0);
    let queue = []; // first in first out
    for (let i = 0; i < v; i++) {
      for (let degreeIncreasing of adj[i]) {
        indegree[degreeIncreasing]++;
      }
    }

    // // both loops are same you can use what's your convenient.
    // // find indegree of each vertex

    // for (let i = 0; i < v; i++) {
    //   for (let j = 0; j < adj[i].length; j++) {
    //     let increasing = adj[i][j];
    //     indegree[increasing]++;
    //   }
    // }

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

    let kahnstopo = [];
    while (queue.length !== 0) {
      let vertex = queue.shift();
      kahnstopo.push(vertex);

      for (let remove of adj[vertex]) {
        indegree[remove]--;
        if (indegree[remove] === 0) {
          queue.push(remove);
        }
      }
    }
    return kahnstopo;
  }
}

let adjList = [[], [], [3], [1], [0, 1], [0, 2]];
let totalList = adjList.length;

let data = new solution();
let output = data.kahnsAlgo(totalList, adjList);
console.log("this is your kahn's topological order", output);

Code Explanation With Behind The Scenes:

Conclusion:

I am confident all those powerful visualizations have made this complex topic clearer to all of you and if you are standing at the conclusion title you’ve officially earned the title of a master of Kahn’s algorithm, and when you see the DAG ordering problem comes your way or interview you’ve just remembered all of above visual you can easily crack the problem.
I hope I’ve unravelled the secrets of Kahn’s algorithm in a manner that resonates with you. Thank you for sticking together until the conclusion. Your support means the world! If you have any doubts or queries, or if there’s a specific topic you’d like me to dive into, drop a comment below the blog or shoot me a direct message. I’m here to help and let’s tackle more algorithmic adventures together.