Challenge 3: Topological Sorting of a Graph
Given a graph, return a list containing all the nodes of the graph in topological order.
We'll cover the following
Problem Statement
Imagine you have been given the task to schedule some tasks. The tasks are represented as vertices of the graph, and if a task must be completed before a task can be started, then there is an edge from to in the graph.
Find the order of the tasks so that each task can be performed in the right order.
This problem can be solved if we find the topological sorting of the graph.
What is Topological Sort of a Graph?
A topological sort gives the order in which to perform the tasks.
Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices. For every directed edge vertex comes before in the ordering.
Topological sorting for a graph is not possible if the graph is not a DAG.
The algorithm for topological sorting can be visualized as follows:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.