Challenge 10: Topological Sorting of a Graph
Given a graph, perform topological sorting of 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 an order of the tasks(graph) in such a way that each task can be performed in the right order.
This problem can be solved if we find the topological sorting of the graph. A topological sort gives an order in which to perform the jobs.
Topological sorting for 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 which takes a Directed Acyclic Graph (DAG) and computes its topological sorting.
Input
A Directed Acyclic Graph.
Output
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.