# Topological Sorting Using DFS

Use the concept of depth-first traversal to perform topological sorting on a graph.

## We'll cover the following

## Problem statement

In the field of computer science, a topological sort or topological
ordering of a directed graph is a linear ordering of its vertices such that for every directed edge **(u, v)**
from vertex **u** to vertex **v**, **u** comes before **v** in the ordering. For instance, the vertices of the graph
may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another. In this application, a topological ordering is just a valid sequence for the tasks. A topological ordering is possible if and only if the graph has no directed cycles, i.e, if it is a *directed acyclic graph* (*DAG*). Any *DAG* has at least one topological ordering.

## Solution

There can be more than one topological sorting for a graph. We can use *Depth-First Search* to solve this problem. Before moving to the implementation, let us first take an example of topological sorting.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.