fork download
copy 
  1.  
  2. import java.util.ArrayList;
  3. import java.util.HashMap;
  4. import java.util.Iterator;
  5. import java.util.List;
  6. import java.util.Map;
  7. import java.util.Set;
  8.  
  9. /**
  10.  * Topological Sort Using DFS with few modifications
  11.  * NOte : applicable only for directed acyclic graphs
  12.  * @author Prateek
  13.  *
  14.  */
  15. class TOPOSort {
  16.  
  17. 	private int numVertices;
  18. 	// Map containing nodes and their connected Nodes
  19. 	private Map<Integer, List<Integer>> adjList;
  20.  
  21. 	// All nodes and their visit status 
  22. 	private Map<Integer, Boolean> vistedStatusList;
  23.  
  24. 	public TOPOSort(int n)	{
  25. 		this.numVertices=n;
  26. 		adjList=new HashMap<Integer, List<Integer>>(n);
  27. 		vistedStatusList=new HashMap<Integer,Boolean>(n);
  28. 	}
  29.  
  30. 	/**
  31. 	 * Desc: adding edge between vertices
  32. 	 * @param src edge starts from here
  33. 	 * @param dest edge ends here
  34. 	 */
  35. 	private void addEdge(int src, int dest) {
  36.  
  37. 		// add node and set visit status as false (unvisited/ unexplored nodes)
  38. 		vistedStatusList.put(src, false);
  39. 		vistedStatusList.put(dest, false);
  40.  
  41. 		// get the adjacency list of a given node 
  42. 		List<Integer> list=adjList.get(src);
  43.  
  44.  
  45. 		if(list==null) //if adjacency list is empty
  46. 			list = new ArrayList<Integer>();
  47.  
  48. 		list.add(dest);
  49. 		adjList.put(src,list);
  50. 	}
  51.  
  52. 	///======== TOPOLOGICAL SORT ========/////////
  53. 	// to keep track of ordering
  54. 	private int currentLabel;
  55. 	int[] sortedArray;
  56. 	public void topologicalSort()
  57. 	{
  58.  
  59. 		currentLabel=vistedStatusList.size()-1;
  60. 		sortedArray=new int[numVertices];
  61.  
  62. 		Set<Map.Entry<Integer, Boolean>> set=vistedStatusList.entrySet();
  63. 		Iterator<Map.Entry<Integer, Boolean>> iterator=set.iterator();
  64. 		while(iterator.hasNext())
  65. 		{
  66. 			Map.Entry<Integer,Boolean> node= iterator.next();
  67. 			int key=node.getKey();
  68. 			boolean isVisited=vistedStatusList.get(key);
  69. 			if(!isVisited)
  70. 				topologicalSortUtil(key); // Call DFS for a given node , if unvisited
  71. 		}
  72.  
  73. 		// printing the topological sorted array
  74. 		for(int i=0;i<sortedArray.length;i++)
  75. 		{
  76. 			if(sortedArray[i]!=0)
  77. 				System.out.print(sortedArray[i]+"\t");
  78. 		}
  79. 	}
  80.  
  81.  
  82. 	/**
  83. 	 * Procedure Similar to DFS, unwinds when deepest node is encountered
  84. 	 * @param vertex
  85. 	 */
  86. 	public void topologicalSortUtil(int vertex)
  87. 	{
  88. 		vistedStatusList.put(vertex,true);
  89. 		List<Integer> list=adjList.get(vertex);
  90.  
  91. 		if(list!=null)
  92. 		{
  93. 			int size= list.size();
  94. 			for(int i=0;i <size; ++i)
  95. 			{
  96. 				int adjNode=list.get(i);
  97. 				boolean isVisited=vistedStatusList.get(adjNode);
  98. 				if(!isVisited)
  99. 				{
  100. 					//System.out.println(adjNode + "\t");
  101. 					topologicalSortUtil(adjNode);
  102. 				}
  103. 			}	
  104. 		}
  105. 		/* for loop will end when the sink vertex is reached , that sink vertex is plucked and put in the array as per the currentLabel, 
  106. 		 * which corresponds to its position in topological sort */
  107. 		sortedArray[currentLabel]=vertex;
  108. 		currentLabel--;
  109.  
  110. 	}
  111.  
  112. 	public static void main(String[] args) {
  113. 		int numVertices = 7;
  114. 		TOPOSort g=new TOPOSort(numVertices);
  115.  
  116. 		g.addEdge(0, 1);
  117. 		g.addEdge(0, 2);
  118. 		g.addEdge(0, 5);
  119. 		g.addEdge(1, 4);
  120. 		g.addEdge(5, 2);
  121. 		g.addEdge(3, 2);
  122. 		g.addEdge(3, 5);
  123. 		g.addEdge(3, 4);
  124. 		g.addEdge(3, 6);
  125. 		g.addEdge(6, 4);
  126. 		g.addEdge(6, 1);
  127.  
  128. 		System.out.println("Topoogical Ordering is : ");
  129. 		g.topologicalSort();
  130.  
  131. 	}
  132. }
  133.  
Success #stdin #stdout 0.06s 380160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Topoogical Ordering is : 
3	6	5	2	1	4
https://ideone.com/lUrTaJ
language:
Java (12.0.1)
created:
10 years ago
visibility:
secret

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!