I have implemented the topological sort.
Is there any suggestion for optimizing the solution?
Thanks.
package src;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Stack;
class Graph{
int V;
LinkedList[] edges;
public Graph(int vertices){
V =vertices;
edges = new LinkedList[V];
for(int i=0;i<V;i++){
edges[i] = new LinkedList();
}
}
// Time complexity O(V+E)
public void topologicalSort() {
Stack stacks = new Stack();
boolean[] visited = new boolean[V];
for(int i=0;i<V;i++) {
if(!visited[i]){
topologicalSortUtil(i,visited,stacks);
}
}
while(!stacks.isEmpty()){
System.out.println(stacks.pop());
}
}
private void topologicalSortUtil(int i, boolean[] visited, Stack stacks) {
stacks.push(i);
visited[i] =true;
Iterator<Integer> iterator = edges[i].listIterator();
while(iterator.hasNext()){
int item = iterator.next();
if(!visited[item]){
topologicalSortUtil(item,visited,stacks);
}
stacks.push(item);
}
}
}
public class TopologicalSorting {
public static void main(String[] args) {
Graph graph = new Graph(8);
graph.topologicalSort();
}
}
package src;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Stack;
class Graph{
int V;
LinkedList[] edges;
public Graph(int vertices){
V =vertices;
edges = new LinkedList[V];
for(int i=0;i<V;i++){
edges[i] = new LinkedList();
}
}
// Time complexity O(V+E)
public void topologicalSort() {
Stack stacks = new Stack();
boolean[] visited = new boolean[V];
for(int i=0;i<V;i++) {
if(!visited[i]){
topologicalSortUtil(i,visited,stacks);
}
}
while(!stacks.isEmpty()){
System.out.println(stacks.pop());
}
}
private void topologicalSortUtil(int i, boolean[] visited, Stack stacks) {
stacks.push(i);
visited[i] =true;
Iterator<Integer> iterator = edges[i].listIterator();
while(iterator.hasNext()){
int item = iterator.next();
if(!visited[item]){
topologicalSortUtil(item,visited,stacks);
}
stacks.push(item);
}
}
}
public class TopologicalSorting {
public static void main(String[] args) {
Graph graph = new Graph(8);
graph.topologicalSort();
}
}
