Find the topological sort of a given graph. Here, i have explained how to find topological sort using Kahn’s algorithm.This algorithm is based on BFS (Breadth first search) and makes use of QUEUE and an Indegree ARRAY.Topological sort can also be found recursively using DFS (Depth first search) and a STACK which i have explained in my previous video.I have shown all the steps of this algorithm clearly using proper examples and have also shown the solution for a practice problem from leetcode number 210 which is course schedule 2.I have dry run the algorithm and have also explained the code walk through at the end of the video.CODE LINK is present below as usual.
In this tutorial we will solve the Course Schedule 2 problem from leetcode to understand Kahn’s Algorithm properly.
class Solution { //Graph coloring: 0->not visited...1->visited...2->visited & processed bool detectCycle_util(vector<vector<int>>& adj,vector<int>& visited,int v) { if(visited[v]==1) return true; if(visited[v]==2) return false; visited[v]=1; //Mark current as visited for(int i=0;i<adj[v].size();++i) if(detectCycle_util(adj,visited,adj[v][i])) return true; visited[v]=2; //Mark current node as processed return false; } //Cycle detection bool detectCycle(vector<vector<int>>& adj,int n) { vector<int> visited(n,0); for(int i=0;i<n;++i) if(!visited[i]) if(detectCycle_util(adj,visited,i)) return true; return false; } //Topological sort void dfs(vector<vector<int>>& adj,int v,vector<bool>& visited,stack<int>& mystack) { visited[v] = true; for(int i=0;i<adj[v].size();++i) if(!visited[adj[v][i]]) dfs(adj,adj[v][i],visited,mystack); mystack.push(v); } public: vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) { int n=prerequisites.size(); vector<vector<int>> adj(numCourses); //Make adjacecncy list for(int i=0;i<n;++i) adj[prerequisites[i][1]].push_back(prerequisites[i][0]); //Detect CYCLE...If present then return empty array vector<int> ans; if(detectCycle(adj,numCourses)) return ans; //Find toposort and store it in stack stack<int> mystack; vector<bool> visited(numCourses,false); //Apply DFS and find topological sort for(int i=0;i<numCourses;++i) if(!visited[i]) dfs(adj,i,visited,mystack); while(!mystack.empty()) { ans.push_back(mystack.top()); mystack.pop(); } return ans; } };