What is topological sorting in a graph?

Web Development
,
#1

Topological sorting is a linear ordering of vertices such that for every directed edge ij, vertex i comes before j in the ordering.
Topological sorting is only possible for Directed Acyclic Graph (DAG).
Applications:
jobs scheduling from the given dependencies among jobs.
ordering of formula cell evaluation in spreadsheets
ordering of compilation tasks to be performed in make files,
data serialization
resolving symbol dependencies in linkers.
Topological Sort Code in Java:

 // V - total vertices
 // visited - boolean array to keep track of visited nodes
 // graph - adjacency list.
// Main Topological Sort Function. 
void topologicalSort() 
{ 
    Stack<Integer> stack = new Stack<Integer>(); 

    // Mark all the vertices as not visited 
    boolean visited[] = new boolean[V]; 
    for (int j = 0; j < V; j++){ 
        visited[j] = false; 
    }
    // Call the util function 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 -> result of topological sort
    while (stack.empty() == false) 
        System.out.print(stack.pop() + " "); 
} 

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

    // Recur for all the vertices adjacent to the current vertex 
    Iterator<Integer> it = graph.get(v).iterator(); 
    while (it.hasNext()) { 
        i = it.next(); 
        if (!visited[i]) 
            topologicalSortUtil(i, visited, stack); 
    } 

    // Push current vertex to stack that saves result 
    stack.push(new Integer(v)); 
}
#2

Topological sorting is sorting a set of n vertices such that every directed edge (u,v) to the vertex v comes from u ∈E(G) where u comes before v in the ordering.

A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG).

Every DAG has at-least one topological ordering. There are algorithms to find topological ordering in O(m+n) time. One simple algorithm would be to do a DFS on a DAG. A possible topological order is obtained by ordering the vertices from higher to lower finish times of vertices in a DFS traversal