Topological Sort Code - Graphs

 Click Me


import java.util.*;

// A Graph Node
class GraphNode{
    String name;
    // list we use in adjacency list
    ArrayList<GraphNode> neighbours;
    
    // Constructor
    GraphNode(String name){
        this.name = name;
        this.neighbours = new ArrayList<>();
    }
}

public class Main {
    
    ArrayList<GraphNode> nodesList;
    
    // constructor
    Main(){
        this.nodesList = new ArrayList<>();
    }
    
    // function to add a directed edge from i->j
    public void addDirectedAcyclicEdge(int source, int destination){
        if(source==destination){
            System.out.println("Can't add cyclic edge in graph, as for topological sort the graph should be Directed Acyclic Graph");
            return;
        }
        // As we have to add a directed edge from source to destination node,
        // we get the source node from the list and add destination node in source node's neighbours
        this.nodesList.get(source).neighbours.add(this.nodesList.get(destination));
    
    }
    
    // function to do topological sort 
    // Time Complexity - O(V+E)  , Space Complexity - O(V+E)
    public void topologicalSort(){
        System.out.println("Topological Sort of given graph...");
        // Hashset to store nodes which are already visited
        HashSet<GraphNode> visitedNodes = new HashSet<>();
        // stack to do linear ordering of nodes using topologicalSort
        Stack<GraphNode> stack = new Stack<>();
        
        // for every unvisited node 
        for(GraphNode graphnode : this.nodesList){
            // here I am starting from node v0
            if(!visitedNodes.contains(graphnode)){
                topologicalVisit(graphnode,visitedNodes,stack);
            }
        }
        
        // Now here we will have all our node into the stack, so we just pop it one by one and display them
        // for the linear ordering of topological sort of given graph
        while(!stack.isEmpty()){
            System.out.print(stack.pop().name+" ");
        }
        
        
    }
    
    // hepler method for topologicalSort. We will call this method recursively for neighbours of current node
    private void topologicalVisit(GraphNode curr, HashSet<GraphNode> visitedNodes,Stack<GraphNode> stack){
        // if current node is visited, we return
        // base case of recursion
        if(visitedNodes.contains(curr)){
            return;
        }
        
        // for every neighbour or adjacent nodes which are unvisited call this function recursively
        for(GraphNode neighbour : curr.neighbours){
            if(!visitedNodes.contains(neighbour)){
                topologicalVisit(neighbour,visitedNodes,stack);
            }
        }
        
        // if no neigbour of current node, then simply push it to stack and mark it visited    
        visitedNodes.add(curr);
        stack.push(curr);
            
    }
    
    public static void main(String[] args) throws Exception {
        Main graph = new Main();
        
        // add 8 nodes to nodes list
        for(int i=0;i<8;i++){
            graph.nodesList.add(new GraphNode("V"+i));
        }
        
        // add directed acyclic edges between nodes. 
        // The image of graph used for this code is published in blog post.
        // IF you are on blog, see above.
        
        
        // Add directed and acyclic edge i->j
        graph.addDirectedAcyclicEdge(0,2);
        graph.addDirectedAcyclicEdge(1,3);
        graph.addDirectedAcyclicEdge(1,2);
        graph.addDirectedAcyclicEdge(2,4);
        graph.addDirectedAcyclicEdge(3,5);
        graph.addDirectedAcyclicEdge(4,7);
        graph.addDirectedAcyclicEdge(4,5);
        graph.addDirectedAcyclicEdge(5,6);
        
        // Now we have added all the directed acyclic edges.
        // we are now ready to do topological sorting
        
        graph.topologicalSort();
    }
}

Comments

Post a Comment

Popular posts from this blog

Binary Heap - Introduction

Image
#Image Credit - GeeksForGeeks Types of heap: Min Heap - every node is less than or equal to  its children(s) Max Heap - every node is more than or equal to its children(s) Operations on any heap : create insert extract/delete - we can extract/delete only the top node in any heap traverse delete entire heap get size of heap peek top of heap We should prefer implementing binary heap using arrays and not linked list, as during bottom to top heapify, in reaching the bottom rightmost node we take only 0(1) time in case of array but we take 0(n) time in case of linked list because first, we need to level order traverse the binary heap tree to get bottom-most rightmost element.  Heaps are used to efficiently implement:  Prim's Algorithm Heapsort Priority queue
Read more

Divide and Conquer - Introduction

Image
What is Divide and Conquer? Divide and Conquer is an algorithm paradigm in which we break down a given problem into smaller sub-problems of similar type until the sub-problems are small enough to be solved directly. The solution to these sub-problems are then combined to give a solution to the original problem.  Study the diagram below, it will then make more sense about what we do in Divide and Conquer : Where to Apply Divide and Conquer? The Divide and Conquer can be applied to all those problems that show Optimal Substructure property.  So, What is this Optimal Substructure property now? If we can break down a problem into similar sub-problems and the solution of these sub-problems can be used to create the solution of the whole problem, then that problem is said to have the Optimal Substructure property. For eg. : Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2),    In this example, we can see that if we want to find the Fibonacci number at the nth place, we can br...
Read more

Bubble Sort

Time complexity - O(n^2)  || Space Complexity - O(1) Bubble sort is an inplace sorting algorithm, that means we do not any extra space while bubble sorting public class Main {     public static void main(String[] args) throws Exception {         int[] arr={1,4,4,5,6,2,3,90,120,43,0};                  System.out.println("UnSorted Array :");         for(int i=0;i<arr.length;i++){             System.out.print(arr[i]+" ");         }         System.out.println();         // bubble sort         for(int i=0;i<arr.length-1;i++){ // iterates through first to last cell             for(int j=0;j<arr.length-1-i;j++){ // inner loop controls swapping and extent to which swapping is to be performed in array     ...
Read more