Challenge: Topological Sorting of a Graph
Given a graph, topologically sort it.
We'll cover the following
Problem statement
You have been given the task to schedule tasks. The tasks are represented by vertices of a graph, and there is an edge from to if a task must be completed before a task can be started.
Find the order of the tasks(graph) so that each task can be performed in the right order.
This problem can be solved by finding the topological sorting of the graph. A topological sort gives the order in which to perform the jobs.
Topological sorting for a Directed Acyclic Graph (DAG) is a linear ordering of vertices, such that 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.
Implement a function that takes a directed acyclic graph (DAG) and computes its topological sorting.
Input
The input is a directed acyclic graph.
Output
The output is the topological sorting of the graph.
Sample input
graph = {
5 -> 2
5 -> 0
4 -> 0
4 -> 1
2 -> 3
3 -> 1
}
Sample output
5 4 2 3 1 0
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.