Showing posts with label Topological sort. Show all posts
Showing posts with label Topological sort. Show all posts

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

links for Data Structure

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