Topological Sort

Topological sorting is one of the most important operations on Directed Acyclic Graphs (DAGs).  It orders vertices of the graph linearly such that for every directed edge uv, vertex u comes before vertex v. Topological sorting of a graph is not possible if the graph is cyclic.
Suppose you have a set of precedence constraint task to be performed, where certain tasks have to be performed before other tasks. These precedence constraint tasks form DAGs, so topological sort can be used to linearly order these tasks in such a way that all dependencies are taken care.

Algorithm

Topological sort can be performed efficiently using depth-first search. A directed graph is a DAG if and only if no back edges are encountered. Labeling the vertices in the reverse order that they are marked processed generates a topological sort for DAG. 

There is another technique for topological sorting, known as source removal technique. Implementation of this approach is simpler but it modifies the graph object. It removes the vertex and the corresponding edge which doesn't have any incoming edge. So after this, the new graph will be a reduced sub-graph of the original graph. Keep doing the same until the graph is not empty or you find a cycle in the graph. Below diagram shows in steps. 

Note that in the first step, we could have removed B first and then A. So the order would have been B, A, C, D, E. So clearly more than one sort is possible for the same DAG.

Implementation 

Below is Java implementation of source removal technique. Adjacency list graph is referenced from here.

package graph.algo;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * Topological sort for Directed Acyclic Graphs using source removal technique
 * 
 * @author Siddheshwar
 * 
 * @param <V>
 */
public class TopologicalSort<V> {

 /**
  * Sort method which takes graph object as input and returns sorted list of
  * vertices
  * 
  * @param graph
  * @return
  */
 public List<V> sort(Graph<V> graph) {
  List<V> sortedVertices = new ArrayList<>();

  while (!graph.isEmpty()) {
   Set<V> vertices = getVerticesWithoutIncomingEdges(graph);
   if (!vertices.isEmpty()) {
    sortedVertices.addAll(vertices);
    for (V v : vertices) {
     graph.removeVertex(v);
    }
   } else {
    System.out.println(" Graph is NOT ADG");
    return Collections.emptyList();
   }
  }

  return sortedVertices;
 }

 /**
  * Returns set of vertices which doesn't have any incoming edge So there are
  * only outgoing connections/relationship
  * 
  * 
  * @param graph
  * @return
  */
 private Set<V> getVerticesWithoutIncomingEdges(Graph<V> graph) {
  if (graph.isEmpty() || graph == null) {
   return Collections.emptySet();
  }
  Set<V> response = new HashSet<>();
  Set<V> totalVertices = new HashSet<>();

  totalVertices.addAll(graph.getAllVertices());
  response.addAll(graph.getAllVertices());

  for (V v : totalVertices) {
   response.removeAll(graph.getAdjacentVertices(v));
  }
  return response;
 }

 /**
  * Test method
  * 
  * @param args
  */
 public static void main(String[] args) {
  TopologicalSort<Character> ts = new TopologicalSort<>();
  Graph<Character> g = new Graph<>();
  g.addEdge('A', 'C');
  g.addEdge('B', 'C');
  g.addEdge('C', 'D');
  g.addEdge('C', 'E');
  g.addEdge('D', 'E');

  System.out.println(g.toString());
  List<Character> sortedVertices = ts.sort(g);
  System.out.println(" sorted vertices -->" + sortedVertices);
 }

}

Output:
Set of Edges :
A ------->C
B ------->C
C ------->D
C ------->E
D ------->E
& Set of vertices :[A, B, C, D, E]

 sorted vertices -->[A, B, C, D, E]

--
keep coding !!!