Challenge 3: Topological Sorting of a Graph

Given a graph, return a list containing nodes the of the graph in topological order.

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 uu must be completed before a task vv can be started, then there is an edge from uu to vv 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 {u,v}\{u,v\} vertex uu comes before vv 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 70+ hands-on prep courses.