Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Stack;
public class TopologicalSortDFS {
public TopologicalSortDFS() {
}
void addEdge(ArrayList<ArrayList<Integer>> adj, int v, int u){
adj.get(v).add(u);
// adj.get(u).add(v);
}
public static void main(String[] args) {
ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
for(int i=0;i<8;i++){
adj.add(new ArrayList<>());
}
TopologicalSortDFS g = new TopologicalSortDFS();
g.addEdge(adj,7, 1);
g.addEdge(adj,7, 0);
g.addEdge(adj,5, 1);
g.addEdge(adj,1, 2);
g.addEdge(adj,1, 6);
g.addEdge(adj,1, 4);
g.addEdge(adj,3, 4);
g.addEdge(adj,3, 0);
g.addEdge(adj,0,6);
boolean[] visited = new boolean[8];
Stack<Integer> stack = new Stack<>();
for(int i=0;i<8;i++){
if(!visited[i]){
g.DFS(i,adj,visited,stack);
}}
System.out.println(stack);
}
void DFS(int v,ArrayList<ArrayList<Integer>> adj,boolean[] visited, Stack<Integer> stack){
visited[v]=true;
System.out.println(v);
ArrayList<Integer> list = adj.get(v);
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()){
Integer i = iterator.next();
if(!visited[i]){
DFS(i,adj,visited,stack);
}
}
stack.push(v);
}
}
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Stack;
public class TopologicalSortDFS {
public TopologicalSortDFS() {
}
void addEdge(ArrayList<ArrayList<Integer>> adj, int v, int u){
adj.get(v).add(u);
// adj.get(u).add(v);
}
public static void main(String[] args) {
ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
for(int i=0;i<8;i++){
adj.add(new ArrayList<>());
}
TopologicalSortDFS g = new TopologicalSortDFS();
g.addEdge(adj,7, 1);
g.addEdge(adj,7, 0);
g.addEdge(adj,5, 1);
g.addEdge(adj,1, 2);
g.addEdge(adj,1, 6);
g.addEdge(adj,1, 4);
g.addEdge(adj,3, 4);
g.addEdge(adj,3, 0);
g.addEdge(adj,0,6);
boolean[] visited = new boolean[8];
Stack<Integer> stack = new Stack<>();
for(int i=0;i<8;i++){
if(!visited[i]){
g.DFS(i,adj,visited,stack);
}}
System.out.println(stack);
}
void DFS(int v,ArrayList<ArrayList<Integer>> adj,boolean[] visited, Stack<Integer> stack){
visited[v]=true;
System.out.println(v);
ArrayList<Integer> list = adj.get(v);
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()){
Integer i = iterator.next();
if(!visited[i]){
DFS(i,adj,visited,stack);
}
}
stack.push(v);
}
}
No comments:
Post a Comment