Prerequisites: Graphs, DFS
Problem: Check if for the given directed graph, topological ordering can be found or not.
Solution Approach: As mentioned in the problem statement, the core idea behind finding topological ordering using BFS(Kahn’s Algorithm) is to process vertices in a way that respects their dependencies. It achieves this by iteratively selecting vertices with no incoming edges (in-degree 0) and gradually removing them from the graph.
Kahn’s Algorithm identifies vertices that can be processed first (those without dependencies) and ensures that each vertex is processed only after its dependencies have been satisfied. This systematic approach leads to a topological ordering of the vertices in a directed acyclic graph (DAG).
If the graph is not a DAG and contains a cycle then those nodes in cycle shall not be processed and hence not be added in topological order list. At the end, if the size of topological order list is not equal to total no. of nodes in graph, it means the graph had cycle and hence topological ordering is not possible.
Time complexity: O(N + M) as we are using BFS.
Space complexity: O(N) as we need to use a queue in BFS.