fork download
copy 
  1. import java.util.*;
  2.  
  3. class GraphAllTopSorts {
  4.     int V;  // No. of vertices
  5.     LinkedList<Integer>[] adj;  //Adjacency List
  6.     boolean[] marked;   //Boolean array to store the visited nodes
  7.     List<Integer> list; //
  8.     int[] indegree; //integer array to store the indegree of nodes
  9.     Stack<Integer> st;
  10.     LinkedList<Integer> q;
  11.  
  12.     //Constructor
  13.     public GraphAllTopSorts(int v) {
  14.         this.V=v;
  15.         this.adj = new LinkedList[v];
  16.         for (int i=0;i<v;i++) {
  17.             adj[i] = new LinkedList<Integer>();
  18.         }
  19.         this.indegree = new int[v];
  20.         this.marked = new boolean[v];
  21.         list = new ArrayList<Integer>();
  22.         this.st = new Stack<Integer>();
  23.         this.q = new LinkedList<Integer>();
  24.     }
  25.  
  26.     // function to add an edge to graph
  27.     public void addEdge(int v, int w){
  28.         adj[v].add(w);
  29.         // increasing inner degree of w by 1
  30.         indegree[w]++;
  31.     }
  32.  
  33.     public void getKosarajuTopologicalSort(int val) {
  34.         for (int i=0;i<V;i++) {
  35.             if (!marked[i]) {
  36.                 dfs(i);
  37.             }
  38.         }
  39.  
  40.         if (val==0) {
  41.             while (!q.isEmpty()) {
  42.                 System.out.print(q.remove() + " ");
  43.             }
  44.             System.out.print("\n");
  45.         }
  46.         else {
  47.             while (!st.isEmpty()) {
  48.                 int w = st.pop();
  49.                 System.out.print(w + " ");
  50.             }
  51.             System.out.print("\n");
  52.         }
  53.  
  54.     }
  55.  
  56.     public void dfs(int v) {
  57.         marked[v] = true;
  58.         Iterator<Integer> iter = adj[v].listIterator();
  59.         while (iter.hasNext()) {
  60.             int w = iter.next();
  61.             if (!marked[w]) {
  62.                 dfs(w);
  63.             }
  64.         }
  65.         q.add(v);
  66.         st.push(v);
  67.     }
  68.  
  69.     public GraphAllTopSorts reverse() {
  70.         GraphAllTopSorts g2 = new GraphAllTopSorts(V);
  71.         for (int i=0;i<V;i++) {
  72.             Iterator<Integer> iter = adj[i].listIterator();
  73.             while (iter.hasNext()) {
  74.                 int w = iter.next();
  75.                 g2.addEdge(w, i);
  76.             }
  77.         }
  78.         return g2;
  79.     }
  80.  
  81.     // Driver program to test above functions
  82.     public static void main(String[] args) {
  83.         // Create a graph given in the above diagram
  84.         GraphAllTopSorts g = new GraphAllTopSorts(6);
  85.         g.addEdge(5, 2);
  86.         g.addEdge(5, 0);
  87.         g.addEdge(4, 0);
  88.         g.addEdge(4, 1);
  89.         g.addEdge(2, 3);
  90.         g.addEdge(3, 1);
  91.  
  92.         System.out.println("PostOrder for original graph");
  93.         g.getKosarajuTopologicalSort(0);
  94.  
  95.         System.out.println("Kosaraju Topological Sort (Reverse PostOrder) for reverse graph");
  96.         GraphAllTopSorts g2 = g.reverse();
  97.         g2.getKosarajuTopologicalSort(1);
  98.  
  99.  
  100.     }
  101. }
Success #stdin #stdout 0.1s 320576KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
PostOrder for original graph
0 1 3 2 4 5 
Kosaraju Topological Sort (Reverse PostOrder) for reverse graph
1 3 2 0 5 4
https://ideone.com/Dc2TnM
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!