TopologicalSort.java

import java.util.*;

class TopologicalSort {
   public static class Edge{
     int u;
     int w;
     public Edge(int u, int w) {
       this.u=u;
       this.w=w;
     }
   };

   public static class Graph {
     public int V;
     public int E;
     public Vector<Vector<Edge>> adj;

     public Graph(int V){
       this.V = V;
       this.E = 0;
       this.adj = new Vector<Vector<Edge>> ();
       for(int i=0; i<V; i++) this.adj.add(new Vector<Edge>());
     }

     public void addEdge(int u, int v, int w) {
       this.adj.get(u).add(new Edge(v, w));
       this.E++;
     }
   };

   static Vector<Integer> topologicalSort(Graph dag){
     int indegree[] = new int[dag.V];
     Vector<Integer> order = new Vector<Integer>();
     Queue<Integer> q = new LinkedList<Integer>();
     
     for(int i=0;i<dag.V;i++){
       for(int j=0;j<dag.adj.get(i).size();j++){
          indegree[dag.adj.get(i).get(j).u]++;
       }
     }

     for(int i=0;i<indegree.length;i++){
       if(indegree[i] == 0) {
         q.add(i);
       }
     }

     while(!q.isEmpty()){
       int current = q.poll();
       order.add(current);
       for(Edge e:dag.adj.get(current)){
         indegree[e.u]--;
         if(indegree[e.u] == 0){
           q.add(e.u);
         }
       }
     }

     return order;
   }


   public static void main(String[] args)
   {

     Graph dag = new Graph(11);

     String names[] = new String[] {
       "Calculo I",
       "Calculo II",
       "Calculo III",
       "Probabilidad y estadistica",
       "Electronica y Electrotecnia",
       "Mecanica",
       "Calor y Ondas",
       "Ecuaciones diferenciales",
       "Electricidad y Magnetismo",
       "Algebra y geometria",
       "Algebra Lineal"
     };
     // add edges
     // v = 0 Calculo I
     dag.addEdge(0, 1, 1);
     dag.addEdge(0, 5, 1);
     // v = 1 Calculo II
     dag.addEdge(1, 2, 1);
     dag.addEdge(1, 3, 1);
     dag.addEdge(1, 6, 1);
     dag.addEdge(1, 7, 1);
     // v = 2 Calculo III
     dag.addEdge(2, 4, 1);
     dag.addEdge(2, 8, 1);
     // v = 3 Probabilidad y estadistica
     //
     // v = 4 Electronica y Electrotecnia
     //
     // v = 5 Mecanica
     dag.addEdge(5, 6, 1);
     // v = 6 Calor y Ondas
     //
     // v = 7 Ecuaciones diferenciales
     dag.addEdge(7, 4, 1);
     dag.addEdge(7, 8, 1);
     // v = 8 Electricidad y Magnetismo
     //
     // v = 9 Algebra y geometria
     dag.addEdge(9, 10, 1);
     // v = 10 Algebra Lineal
     dag.addEdge(10, 7, 1);

     Vector<Integer> topSort = topologicalSort(dag);

     if(topSort.size() != dag.V) {
       System.out.println("Existe un ciclo en el grafo, por lo cual no se puede obtener el orden topologico");
     } else {
       for(int i=0;i<topSort.size();i++) {
         System.out.println(names[topSort.get(i)]);
       }
     }
   }

};