## Idea

For a Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge (u,v), vertex u comes before v in the ordering.

• For a DAG
• Topological sort is not unique:

A B C D E

A C B D E

## Topological Sorting

Start with A and perform DFS, while not priting the path on the way. Go to deepest vertex and when there are no neighbours to go from the vertex (it can be by two reason: first is because it is a leaf node, second all neighbour nodes are already visited) set the vertex as visited and push it onto the stack.

Continuing this process untill all nodes becomes visited and then perform pop operation from stack and print the poped elements from the stack.

## Time Complexity

• O(V+E)

V is the number of vertices E is the number of Edges

### Java Implementation

``````// A Java program to print topological sorting of a DAG
import java.io.*;
import java.util.*;

// This class represents a directed graph using adjacency
// list representation
class Graph
{
private int V;   // No. of vertices

//Constructor
Graph(int v)
{
V = v;
for (int i=0; i<v; ++i)
}

// Function to add an edge into the graph

// A recursive function used by topologicalSort
void topologicalSortUtil(int v, boolean visited[],
Stack stack)
{
// Mark the current node as visited.
visited[v] = true;
Integer i;

// Recur for all the vertices adjacent to this
// vertex
while (it.hasNext())
{
i = it.next();
if (!visited[i])
topologicalSortUtil(i, visited, stack);
}

// Push current vertex to stack which stores result
stack.push(new Integer(v));
}

// The function to do Topological Sort. It uses
// recursive topologicalSortUtil()
void topologicalSort()
{
Stack stack = new Stack();

// Mark all the vertices as not visited
boolean visited[] = new boolean[V];
for (int i = 0; i < V; i++)
visited[i] = false;

// Call the recursive helper function to store
// Topological Sort starting from all vertices
// one by one
for (int i = 0; i < V; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, stack);

// Print contents of stack
while (stack.empty()==false)
System.out.print(stack.pop() + " ");
}

// Driver method
public static void main(String args[])
{
// Create a graph given in the above diagram
Graph g = new Graph(6);

System.out.println("Following is a Topological " +
"sort of the given graph");
g.topologicalSort();
}
}
``````

## Topological Sort Applications

• Build Systems: IDE such as Visual Studio, Eclipse. When we build our project the dependency between libraries and sub-projects should be considered. We cannot build the library before building and solving its dependencies.
• Advanced-Packaging Tool (apt-get): In Linux we use this tool in order simply install the applications and libraries into our OS. This tool also uses a dependency map to install.