Monday, 27 April 2020

TopologicalSort using for Directed Acyclic graph DFS

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);
    }
}

No comments:

Post a Comment

links for Data Structure

  1) 𝐁𝐞𝐜𝐨𝐦𝐞 𝐌𝐚𝐬𝐭𝐞𝐫 𝐢𝐧 𝐋𝐢𝐧𝐤𝐞𝐝 𝐋𝐢𝐬𝐭:  https://lnkd.in/gXQux4zj 2) 𝐀𝐥𝐥 𝐭𝐲𝐩𝐞𝐬 𝐨𝐟 𝐓𝐫𝐞𝐞 𝐓𝐫𝐚𝐯𝐞𝐫𝐬𝐚𝐥𝐬...