Depth-First Search based

Topological sorting is a linear ordering of the vertices in a directed acyclic graph (DAG) such that for every directed edge $uv$ from vertex $u$ to vertex $v$, vertex $u$ “comes before” vertex $v$ in the ordering.

By comes before, we mean that there is a directed path from $u$ to $v$ in the graph and no directed path from $v$ to $u.

Topological sorting is used in many applications, such as task scheduling, data processing, and resolving dependencies between tasks.

Topological sorting is not possible if the graph has a cycle, as there is no way to order the vertices in a linear fashion without violating the edge directions.

Algorithm

The topological sort algorithm using depth-first search (DFS) maintains the following data structures:

Sorted: stack to store the topological ordering of the vertices.
Visited: set to keep track of visited vertices.

The topological sort algorithm using depth-first search (DFS) works as follows:

Pick an unvisited vertex and perform a depth-first search (DFS) on it.
When a vertex has no unvisited adjacent vertices,
- push the vertex onto the Sorted stack.
- mark the vertex as visited.
Repeat step 1 and 2 until all vertices are visited.
The Sorted stack contains the topological ordering of the graph.

Pseudocode

The pseudocode for the topological sort algorithm using depth-first search (DFS) is as follows:

function topologicalSort(graph):
    Sorted = stack()
    Visited = set()
    for each vertex in graph:
        if vertex is not in Visited:
            DFS(vertex, Sorted, Visited)

    return Sorted


function DFS(vertex, Sorted, Visited):
    add vertex to Visited

    for each neighbor of vertex:
        if neighbor is not in Visited:
            DFS(neighbor, Sorted, Visited)

    push vertex onto Sorted

Analysis

The time complexity of the topological sort algorithm using depth-first search (DFS) is $O(V + E)$, where $V$ is the number of vertices and $E$ is the number of edges in the graph. The algorithm performs a depth-first search on each unvisited vertex, visiting each edge at most once, resulting in a total time complexity of $O(V + E)$.