Disjoint set

A disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets. A union-find algorithm is an algorithm that performs two useful operations on such a data structure:


import java.util.HashMap;
import java.util.Map;

public class DisjointSet {

    Map<Integer,Node> map = new HashMap<>();
    class Node{
        int rank;
        int data;
        Node parent;
    }

    Node make(int val){
        Node node = new Node();
        node.data = val;
        node.rank = 0;
        node.parent = node;
        map.put(val,node);
        return node;
    }
    boolean union(int n1, int n2){
        Node node1 = map.get(n1);
        Node node2 = map.get(n2);

        Node parent1 = findSet(node1);
        Node parent2 = findSet(node2);
        if(parent1.data==parent2.data){
            return false;
        }
        if(parent1.rank>=parent2.rank){
            parent1.rank = (parent1.rank==parent2.rank)? parent1.rank+1:parent1.rank;
            parent2.parent = parent1;
        }else {
            parent1.parent = parent2;
        }
        return true;
    }
    Node findSet(Node node){
        Node parent = node.parent;
        if(node==parent){
            return parent;
        }else{
            node.parent = findSet(node.parent);
        }
        return node.parent;
    }

    int findSet(int val){
        return findSet(map.get(val)).data;
    }

    public static void main(String[] args) {
        DisjointSet ds= new DisjointSet();
        ds.make(1);
        ds.make(2);
        ds.make(3);
        ds.make(4);
        ds.make(5);
        ds.make(6);
        ds.make(7);

        ds.union(1, 2);
        ds.union(2, 3);
        ds.union(4, 5);
        ds.union(6, 7);
        ds.union(5, 6);
        ds.union(3, 7);

        System.out.println(ds.findSet(1));
        System.out.println(ds.findSet(2));
        System.out.println(ds.findSet(3));
        System.out.println(ds.findSet(4));
        System.out.println(ds.findSet(5));
        System.out.println(ds.findSet(6));
        System.out.println(ds.findSet(7));

    }

}

Ref: https://github.com/mission-peace/interview/blob/master/src/com/interview/graph/DisjointSet.java

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

Bipartite Graph DFS

package com.dsprep.graph;

import java.util.ArrayList;
import java.util.Iterator;

public class BipartiteGraphDFS {
    public BipartiteGraphDFS() {

    }

    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<10;i++){
            adj.add(new ArrayList<>());
        }
        BipartiteGraphDFS g = new BipartiteGraphDFS();
        g.addEdge(adj,1, 2);
        g.addEdge(adj,2, 3);
        g.addEdge(adj,2, 8);
        g.addEdge(adj,3, 4);
        g.addEdge(adj,4, 6);
        g.addEdge(adj,5, 7);
        g.addEdge(adj,5, 9);
        g.addEdge(adj,8, 9);
      //  g.addEdge(adj,7,9);
        boolean[] visited = new boolean[10];
        boolean[] color = new boolean[10];

        if(g.DFS(1,adj,visited,color)){
            System.out.println("Bipartite");
        }else{
            System.out.println("not bipartite");
        }

    }

    boolean DFS(int v,ArrayList<ArrayList<Integer>> adj,boolean[] visited, boolean[] color){
           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]){
                    color[i] = !color[v];
                   if(!DFS(i,adj,visited,color)){
                       return false;
                   }
                }else if(color[i]==color[v]){
                    return false;
                }
        }
            return true;
    }
}

Bipartite Graphs BFS

Bipartite Graphs OR Bigraphs is a graph whose vertices can be divided into two independent groups or sets so that for every edge in the graph, each end of the edge belongs to a separate group. There should not be any edge where both ends belong to the same set.


public class BipartiteGraph {

    public BipartiteGraph() {

    }

    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<10;i++){
            adj.add(new ArrayList<>());
        }
        BipartiteGraph g = new BipartiteGraph();
        g.addEdge(adj,1, 2);
        g.addEdge(adj,2, 3);
        g.addEdge(adj,2, 8);
        g.addEdge(adj,3, 4);
        g.addEdge(adj,4, 6);
        g.addEdge(adj,5, 7);
        g.addEdge(adj,5, 9);
        g.addEdge(adj,8, 9);
     //   g.addEdge(adj,2, 4);

       if( g.BFS(1,adj)){
           System.out.println("Bipartite Graphs");
       }else{
           System.out.println("not Bipartite Graphs");
       }

    }

    boolean BFS(int v,ArrayList<ArrayList<Integer>> adj){
        LinkedList<Integer> queue = new LinkedList<>();
        queue.add(v);

        boolean[] visited = new boolean[adj.size()];
        int[] level = new int[adj.size()];
        level[v]=0;
        visited[v]=true;

        while (!queue.isEmpty()){
            v = queue.poll();
            //System.out.println(v);
            ArrayList<Integer> list = adj.get(v);
            Iterator<Integer> iterator = list.iterator();
            while (iterator.hasNext()){
                Integer i = iterator.next();
               // System.out.println("i is:"+i);
                if(!visited[i]){
                    level[i]=level[v]+1;
                    visited[i] = true;
                    queue.add(i);
                }
                else if (level[v]==level[i]){
                   return false;
                }
            }

        }
        return true;
    }

}

output:

Bipartite Graphs

if if add 2 to 4 in adjacent list then it will not Bipartite graph

Arrival and Departure time Vertices in DFS

Arrival Time / Pre -Visit Time /Starting Time:

Arrival time for a node is the time when it is first discovered in DFS . It is the time at which the node gets into the recursion stack .

Departure Time / Post-Visit Time/Finishing time :

Departure time for a node is the time when all of its adjacent node in the graph are explored and is ready to backtrack . It is the time at which the node pops out of the recursion stack .

Take an example — When parents bring food to home , they first ensures that every child of them is fed , then they start eating . Same simple concept is applied here .

Program: 

import java.util.ArrayList;

import java.util.Iterator;

public class ArrivalDepartureTime {

    public ArrivalDepartureTime() {

    }

    void addEdge(ArrayList<ArrayList<Integer>> adj, int v, int u){

         adj.get(v).add(u);

     }

    public static void main(String[] args) {

        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();

        for(int i=0;i<8;i++){

            adj.add(new ArrayList<>());

        }

        ArrivalDepartureTime g = new ArrivalDepartureTime();

        g.addEdge(adj,0, 1);

        g.addEdge(adj,0, 2);

        g.addEdge(adj,2, 3);

        g.addEdge(adj,2, 4);

        g.addEdge(adj,3, 1);

        g.addEdge(adj,3, 5);

        g.addEdge(adj,4, 5);

        g.addEdge(adj,6, 7);

        g.arrivalDepartureVertex(adj,8);

    }

    void arrivalDepartureVertex(ArrayList<ArrayList<Integer>> adj,int V){

        boolean[] visited = new boolean[V];

        int[] arrival = new int[V];

        int[] departure = new int[V];

        int time = -1;

        for(int i=0;i<V;i++){

            if(!visited[i]){

               time = DFS(i,adj,visited,arrival,departure,time);

            }

        }

        for(int i=0;i<arrival.length;i++){

            System.out.println("vertex "+i +" arrival time:"+arrival[i]+" departure time: "+departure[i]);

        }

    }

    int DFS(int v,ArrayList<ArrayList<Integer>> adj,boolean[] visited, int[] arrival, int[] departure, int time){

        visited[v]=true;

        arrival[v] = ++time;

            ArrayList<Integer> list = adj.get(v);

            Iterator<Integer> iterator = list.iterator();

            while (iterator.hasNext()){

                Integer i = iterator.next();

                if(!visited[i]){

                  time =  DFS(i,adj,visited,arrival,departure,time);

                }

            }

            departure[v] = ++time;

            return time;

    }

}

Ref: https://www.techiedelight.com/arrival-departure-time-vertices-dfs/

https://medium.com/@kumarrocky436/dfs-time-stamp-on-nodes-da76a51a50cb

Transitive Closure of a Graph using DFS

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;

public class TransitiveClosureGraph {
    public static void main(String[] args) {
        int V = 4;
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        int[][] visitedList = new int[V][V];
        for(int i=0;i<V;i++){
            adj.add(new ArrayList<>());
        }
        TransitiveClosureGraph g = new TransitiveClosureGraph();
        g.addEdge(adj,0, 1);
        g.addEdge(adj,0, 2);
        g.addEdge(adj,1, 2);
        g.addEdge(adj,2, 0);
        g.addEdge(adj,2, 3);
        g.addEdge(adj,3, 3);


      for(int i=0;i<V;i++){
          g.DFS(i,adj,visitedList[i]);
      }
      //print
      for(int i=0;i<V;i++){
          System.out.println(Arrays.toString(visitedList[i]));
      }
    }

    void addEdge(ArrayList<ArrayList<Integer>> adj, int u,int v){
        adj.get(u).add(v);
    }

    void DFS(int v, ArrayList<ArrayList<Integer>> adj, int[] visitedList){
        visitedList[v] = 1;
        ArrayList<Integer> nodes = adj.get(v);
        Iterator<Integer> iterator = nodes.iterator();
        while (iterator.hasNext()){
            Integer val = iterator.next();
            if(visitedList[val]==0){
                DFS(val,adj,visitedList);
            }
        }
    }

}

output:

[1, 1, 1, 1]

[1, 1, 1, 1]

[1, 1, 1, 1]

[0, 0, 0, 1]

As we understand from above output there is path from

 0 to 0, 0 to 1, 0 to 2, 0 to 3

 1 to 0, 1 to 1, 1 to 2, 1 to 3

 1 to 0, 1 to 1, 1 to 2, 1 to 3

 3 to 3

Mother Vertex in Graph

 It is a vertex v such that all other vertices in G can be reached by a path from v.

Solution:

step1: first we need to do DFS on each vertex and get the value of vertex when all value of visited array true.

step2: need to DFS on selected value if all the vertex visited it means the value is mother vertex.

public class MotherVertex {

    public MotherVertex() {

    }

    void addEdge(ArrayList<ArrayList<Integer>> adj, int v, int u){
         adj.get(v).add(u);
     }

    public static void main(String[] args) {
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        for(int i=0;i<7;i++){
            adj.add(new ArrayList<>());
        }
        MotherVertex g = new MotherVertex();
        g.addEdge(adj,0, 1);
        g.addEdge(adj,0, 2);
        g.addEdge(adj,1, 3);
        g.addEdge(adj,4, 1);
        g.addEdge(adj,6, 4);
        g.addEdge(adj,6, 0);
        g.addEdge(adj,5, 2);
        g.addEdge(adj,5, 6);

        g.motherVertex(adj,7);
    }

    void motherVertex(ArrayList<ArrayList<Integer>> adj,int V){

//dfs on all vertex
        boolean[] visited = new boolean[V];
        for(int i=0;i<visited.length;i++){
            visited[i]=false;
        }
        int val= -1;
        for(int i=0;i<V;i++){
            if(!visited[i]) {
                DFS(i, adj, visited);
                val = i;
            }
        }

//selected value when visited array value get true
        System.out.println(val);

//dfs on selected value
        visited = new boolean[V];
        DFS(val,adj,visited);
        for (int i=0;i<7;i++){
            if(!visited[i]){
                System.out.println("not found mother vertex");
                return;
            }
        }

//if all value of visited array is true then its mother vertex
        System.out.println("mother vertex"+val);
    }

    void DFS(int v,ArrayList<ArrayList<Integer>> adj,boolean[] visited){



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

output: 

5

mother vertex 5

Depth First Search

public class DFS {
    boolean[] visited = new boolean[5];
    public DFS() {

    }

    void addEdge(ArrayList<ArrayList<Integer>> adj, int v, int u){
         adj.get(v).add(u);
     }

    public static void main(String[] args) {
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        for(int i=0;i<4;i++){
            adj.add(new ArrayList<>());
        }
        DFS g = new DFS();
        g.addEdge(adj,0, 1);
        g.addEdge(adj,0, 2);
        g.addEdge(adj,1, 2);
        g.addEdge(adj,2, 0);
        g.addEdge(adj,2, 3);
        g.addEdge(adj,3, 3);
        g.DFS(2,adj);

    }

    void DFS(int v,ArrayList<ArrayList<Integer>> adj){



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

Breadth First Search

import java.util.*;

public class BFS {

    public BFS() {

    }

    void addEdge(ArrayList<ArrayList<Integer>> adj, int v, int u){
         adj.get(v).add(u);
     }

    public static void main(String[] args) {
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        for(int i=0;i<4;i++){
            adj.add(new ArrayList<>());
        }
        BFS g = new BFS();
        g.addEdge(adj,0, 1);
        g.addEdge(adj,0, 2);
        g.addEdge(adj,1, 2);
        g.addEdge(adj,2, 0);
        g.addEdge(adj,2, 3);
        g.addEdge(adj,3, 3);
        g.BFS(2,adj);

    }

    void BFS(int v,ArrayList<ArrayList<Integer>> adj){
        LinkedList<Integer> queue = new LinkedList<>();
        queue.add(v);

        boolean[] visited = new boolean[adj.size()];
        visited[v]=true;

        while (!queue.isEmpty()){
            Integer val = queue.poll();
            System.out.println(val);
            ArrayList<Integer> list = adj.get(val);
            Iterator<Integer> iterator = list.iterator();
            while (iterator.hasNext()){
                Integer i = iterator.next();
                if(!visited[i]){
                    visited[i] = true;
                    queue.add(i);
                }
            }
        }
    }
}

Adjacent Matrix Graph

import java.util.ArrayList;

public class AdjecentMatrix {

    public static void main(String[] args) {

        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();

        for(int i=0;i<5;i++){

            adj.add(new ArrayList<>());

        }

        addEdge(adj, 0, 1);

        addEdge(adj, 0, 4);

        addEdge(adj, 1, 2);

        addEdge(adj, 1, 3);

        addEdge(adj, 1, 4);

        addEdge(adj, 2, 3);

        addEdge(adj, 3, 4);

        printGraph(adj);

    }

    static void addEdge(ArrayList<ArrayList<Integer>> adj,int u, int v){

        adj.get(u).add(v);

        adj.get(v).add(u);

    }

    static void printGraph(ArrayList<ArrayList<Integer>> adj){

        for(int i=0;i<adj.size();i++){

            System.out.println("adjency list of vertex");

            for(int j=0;j<adj.get(i).size();j++){

                System.out.print("->"+adj.get(i).get(j));

            }

            System.out.println();

        }

    }

}

import java.util.ArrayList;

public class AdjecentMatrix {

    public static void main(String[] args) {

        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();

        for(int i=0;i<5;i++){

            adj.add(new ArrayList<>());

        }

        addEdge(adj, 0, 1);

        addEdge(adj, 0, 4);

        addEdge(adj, 1, 2);

        addEdge(adj, 1, 3);

        addEdge(adj, 1, 4);

        addEdge(adj, 2, 3);

        addEdge(adj, 3, 4);

        printGraph(adj);

    }

    static void addEdge(ArrayList<ArrayList<Integer>> adj,int u, int v){

        adj.get(u).add(v);

        adj.get(v).add(u);

    }

    static void printGraph(ArrayList<ArrayList<Integer>> adj){

        for(int i=0;i<adj.size();i++){

            System.out.println("adjency list of vertex");

            for(int j=0;j<adj.get(i).size();j++){

                System.out.print("->"+adj.get(i).get(j));

            }

            System.out.println();

        }

    }

}