Write code to find post order and topological order (or) topological sort


import java.util.List;
import java.util.ArrayList;
import java.util.Stack;

class DepthFirstOrder {
    private boolean[] visited; // visited[v] = true if v connected to s
    private Stack reversePost; // all vertices in reverse DFS porst order
    
    public DepthFirstOrder(Digraph G) {
        // initialize data structures
        this.visited = new boolean[G.V()];
        this.reversePost = new Stack<>();
        
        for(int v = 0; v < G.V(); v++) {
            if(!visited[v]) {
                dfs(G, v);
            }
        }
    }
    
    // is there a path from s to v?
    public boolean isVisited(int v) {
        return visited[v];
    }
    
    private void dfs(Digraph G, int v) {
        // recursive DFS does the work
        visited[v] = true;
        for (int w : G.adj(v))
            if(!visited[w]) 
                dfs(G, w);
        reversePost.push(v);
    }
    
    /** returns all vertices in “reverse DFS postorder” */
    public Stack reversePost() { 
        return reversePost; 
    }
    
    private static Digraph prepareGraph() {
        int[][] edges = new int[][] {
            {0, 5}, {0, 2},
            {0, 1}, {3, 6},
            {3, 5}, {3, 4},
            {5, 2}, {6, 4},
            {6, 0}, {3, 2},
            {1, 4}
		};
		Digraph G = new Digraph(7);
		// add all edges 
		for(int i = 0; i < edges.length; i++) {
		    int v = edges[i][0];
		    int w = edges[i][1];
		    G.addEdge(v, w);
		}
		return G;
    }
    
    static class Digraph {
        private final int V; // number of vertices
        private final List[] adj; // adjacency lists... 0 to V-1
        
        /** create an empty digraph with V vertices */
        public Digraph(int V) {
            this.V = V;
            this.adj = new ArrayList[V]; // create empty graph with V vertices
            for(int i = 0; i < V; i++) {
                adj[i] = new ArrayList<>();
            }
        }
        
        /** add a directed edge v→w */
        public void addEdge(int v, int w) {
            // add edge v-w 
            adj[v].add(w);
        }
        
        /** Iterator for vertices pointing from v */
        public Iterable adj(int v) {
            return adj[v];
        }
        
        /** number of vertices */
        public int V() {
            return V;
        }
        
        /** number of edges */
        public int E() {
            int countEdges = 0;
            for(int v = 0; v < V; v++) {
                countEdges += adj[v].size();
            }
            return countEdges;
        }
        
        /** reverse of this digraph */
        Digraph reverse() {
            return null;// TODO
        }
        
        /** string representation */
        public String toString() {
            return "TODO";
        }
    }
    
    public static void main (String[] args) {
	    System.out.println("Find port order and topological order ");
		Digraph G = prepareGraph();
		System.out.println("V: " + G.V());
		System.out.println("E: " + G.E());
		DepthFirstOrder depthFirstOrder = new DepthFirstOrder(G);
		Stack postOrder = depthFirstOrder.reversePost();
		Stack reverse = new Stack<>();
		System.out.print("topological order :");
		while(!postOrder.isEmpty()) {
		    int i = postOrder.pop();
		    System.out.print(i + ", ");
		    reverse.push(i);
		}
		System.out.print("\nPost order :");
		while(!reverse.isEmpty()) {
		    System.out.print(reverse.pop() + ", ");
		}
	}
}

Find port order and topological order 
V: 7
E: 11
topological order :3, 6, 0, 1, 4, 5, 2, 
Post order :2, 5, 4, 1, 0, 6, 3, 

Comments

Popular posts from this blog

SQL basic interview question

gsutil Vs Storage Transfer Service Vs Transfer Appliance