Demystifying the Topological Sorting: here is the step-by-step guide and dry-run as well with DFS

Hi Coding RockStars,
Today we will unravel the “Topological Sorting” and how it works the dry run and master this algorithm in a simple manner.

Disclaimer:
Before jumping the code directly, take a moment to read all the lines and try to understand the visualizations. This process helps in understanding the pseudo code, that making it simpler when interpreting the actual code.

Introduction:

The Topological Sorting (TS) is only applicable to the DAG which means (Directed Acyclic Graph) it means any directed graph which does not have a cycle I’ll tell you why.
The definition of the Topo is a linear ordering of its vertices such that every directed edge you consider as (u & v) such as the vertex of u should always come before the vertex of v and any DAG has at least one topological ordering.

Visualizations:

DAG without cycle with Topo order of this graph

Explanation of this image:

don’t chaos very simple understanding, We have 6 edges so corresponding to the edges we have the list of the connected edges the list will represent u & v as I told you before, the vertex of u should always be before the vertex of v.

In this example, 1 made a connection with 2, which is an array of [1, 2] so the vertex of u = array[0]th index, and the vertex of v = array[1]th index so as rules 1 should appear before 2 so as it same for every other u & v of the lists. here is the problem link.

Explain about the topo output:

Topo-order visualization

In this graph, we got a simple topo output [1,2,3,4,5,6] that’s one of the linear ordering in some graphs you can make multiple linear ordering so that doesn’t matter the end of the problems you just return any one of the topo-ordering simple, please eyes on the above picture once.

Why is topo applicable only to DAG:

Visualizations: Why is topo applicable only to DAG

If you have an undirected graph you never make a Topo-ordering because of 1 to 2 so 1 comes before 2 is good but next 2 to 1 how do we get 2 comes before 1 that does not make sense and it practically impossible to make a Topo-order with an undirected graph.

Next, why doesn’t have a cycle when making a Topo-order I'll explain please eyes on the above picture once, 1 to 2 so 1 comes before 2 next 2 to 3 so 2 comes before 3 the real game will come next 3 to 1 how do we get 3 comes before 1 That time will create cyclic dependency, as it is same what I told you not possible to make a topo order with the cyclic graph as well, I really confidence the reason was cleared all of you, end of the line the Topological ordering only applicable for DAG.

Code Showcase:

class solution {
  dfs(node, visited, stack, adjList) {
    visited[node] = true;

    for (let neighbor of adjList[node]) {
      if (!visited[neighbor]) {
        this.dfs(neighbor, visited, stack, adjList);
      }
    }
    stack.push(node);
  }
// step one
  topoSort(v, adj) {
    let visited = new Array(v).fill(false);
    let stack = [];// LIFO last in first out 
    for (let i = 0; i < v; i++) {
      if (!visited[i]) {
        this.dfs(i, visited, stack, adj);
      }
    }
    // don't think it's and reversing order check out 
    // the adjList the all answer will be based on the adjList 
    // why i'm telling when you see the coder first you might think 
    // it's an reverse order list no definetely not

    let ans = [];
    while (stack.length !== 0) {
      let vertex = stack.pop();
      ans.push(vertex);
    }
    return ans;
  }
}

let adjList = [[], [3], [3], [], [1, 0], [0, 2]];
// the index of the arrays consider as a U and the array value arr neighbors of 
// index so consider V simple :) like 0 connect with nothing 1 connect with
// 3 and 2 connect with 3, next 3 connect with nothing, 4 connect with 1 & 0
let totalList = adjList.length;

let data = new solution();
let output = data.topoSort(totalList, adjList);
console.log("this is your toposort order list", output); 
// [ 5, 4, 2, 1, 3, 0 ] output

Code Explanation:

Please read all the command lines in the above Code, Come to the code what is the stack, who comes last that node will out first,

explanation of the code in a simple manner

In the code first index, 0 is thrown into the DFS the DFS will check if anyone has a neighbour of the 0, obviously we know not, so push it into the stack next, and the loop becomes 1 thrown into the DFS again check if anyone has a neighbour of the 1 yes we got one neighbour of 1 then the DFS check the neighbour is already visited or not obviously, not visited yet so push into the stack the no more neighbour of 1 so the DFS loop will end next push the node of 1 why because 1 connected with 3, similar of other indexes of the array nodes.

Conclusions:

In conclusion, I hope this code showcase and visualization have unravelled the secrets of Topological Ordering. With this knowledge, you’re well-equipped to tackle similar problems with confidence. 🚀💻
and you Have any questions or insights? Dive into the comments below! Your feedback fuels the journey, and I’m eager to hear your thoughts on how we can enhance this learning space. Happy coding, and stay tuned for more adventures in the coding realm! 💻🔍