No Chaos with super easy steps to Detecting a cycle in a Direct Graph (DG) with Kahn’s Algorithm

Title

Excited to share this new blog! If you haven’t checked our latest posts, take a look at our previous blogs. I strongly recommend it, as we’ve already explored Kahn’s algorithm. In this blog, we’ll be detecting cycles in a Directed Acyclic Graph (DAG), a concept similar to what we did in Kahn’s algorithm, with a slight difference. here is the problem link,
here is the blog post link.

Introduction:

Imagine throwing a stone into the river obviously, we all know the path is a one-way direction. Our task is to see if there’s a cycle on the stone path like that stone magically finding its way back to your hands. That’s the mystery we will uncover — the secrets, just like that stone’s journey, let’s dive into the blog.

Detecting Cycles in DG:

You can solve this with the DFS traversal technique but two things you have to keep with this entire journey of the DFS, 1) Visited Array, and 2) Path Visited, don’t be afraid, just a basic concept, and in our next blog post we will solve this problem with DFS technique, so all you know what is the DFS and how it works, when comes to your way DFS related problem you can easily solve any DFS problems

Example DFS Visualization:

DFS with a super easy example

DFS and How it works:

DFS traversing DEPTH via a very important phrase, I hope you all know about Recursion and Stack, the stack is nothing but last in first out LIFO if you have some idea about dynamic programming you can easily understand the DFS traversal technique, just assume a soccer man going to purchase the kit what he needs the real game is coming I’ve already mentioned above the image of DFS every split line on the route that you go for a different path isn’t now He is currently at the straight track, and as you can see, there are many possible pathways. In one path, there is no more road, therefore he must return to the track, and then he finds any other paths in the track, Yes! There’s one more track on the road, so he’s going to follow the path that leads to a shoe store. Once he buys the shoes, he’ll check the road track to see if there are any more, and if not, he’ll head back to the track. There is one more track on the road, so he’ll check in the track to see if there are any more. There is a football store on the road after he purchases the football obliviously we know no more track to move further so he returns to the location where he started this path. He then finds the next track, but it is not there, so he returns to the track and continues on a straight path until he eventually finds a whistle shop. After buying the product, there is no more track, so he chooses to return home.

What we got in the above section:

He was simply walking along a road that has many different kinds of paths. He chooses one and follows it until it ends, if he was reached end of that path, he returns to the beginning of the path. This path is similar to going into depth, depth, depth until it ends (keep digging), and then he is discovering any other paths in the track. If so, he takes that path and continues until the end of the path.

Hero of this section Kahn,s BFS:

how are we going to solve this problem with Kahn’s algorithm let’s drag it out of the bag DFS has a big pillar of backtracking so you may go back and back to the path but BFS doesn’t have any backtracking, the question given to us Directed Cyclic Graph isn’t in Kahn’s only applicable for DAG any topological sorting only applicable for DAG which is Directed Acyclic Graph so if it is cycle happens Kahn’s won’t applicable.

Cycle in a graph eye at once in a big circle

Explanation:

Kahn’s — — → Topo returns N vertex in a linear ordering

1. If the graph has a cycle we can’t make topological ordering right since we know Kahn’s only for DAG,
2. Let’s apply Kahn’s for DCG our first step in Kahn’s find an Indegree of 0 push into the queue reduce the in-degree who are connected with that node check the graph to find who has any indegree of 0 vertex push into the queue until the queue became empty isn’t that’s the Kahn’s s just one sec I’ll explain through visual.

Why we can’t make a topo in DCG using Kahn’s:

why can’t make topo

1. simple for the first 1 has 0 indegrees so push into the queue then 1 connect with 2 so reduce the in-degree of 2
2. check that graph 2 have 0 indegrees then push into queue 2 and connect with 6 to reduce the in-degree
3. check the graph now 6 has 0 indegrees pushed into the queue same as all other vertexes

at some point you can’t move forward which means 2 is connected with 6 and 3 but 3 only depends on some other vertices so topo means return N vertex in linear topo ordering here something happened inside of the graph only problem is Cyclic Dependency if don’t know about please eyes at once you will be understood what happens.

Topo < N return True (There is the cycle in the graph) simple….
with one extra variable gonna join with this journey that one COUNT
we have V → total vertex
count how many times we push the vertex into the queue with who has 0 indegree then ++ the count out of the loop check with top0(queue bag) === v
if equel there is no cycle if not there is a cycle so return true simple.

Code Visualization:

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]++;
      }
    }
    for (let j = 0; j < v; j++) {
      if (indegree[j] === 0) {
        queue.push(j);
      }
    }
    let count = 0;
    while (queue.length !== 0) {
      let vertex = queue.shift();
      count++;

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

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);

Conclusion:

I don’t want to make you suffer again it’s totally understandable you’ve been tired just kidding thanks for your patience if you’re standing at the conclusion you will pro to detect a cycle in the graph using powerful Kahn’s algorithm thanks your support means the world If there’s anything you’d like to add or if you have further questions please drop as a command.