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

        }

    }

}

Max Sum Contiguous Subarray

public class Solution {
    public int maxSubArray(final List<Integer> A) {
        int tempSum=0;
        int maxSum = Integer.MIN_VALUE;
            for(int j=0;j<A.size();j++){
                tempSum +=A.get(j);
                if(tempSum>maxSum){
                    maxSum = tempSum;
                }
                if(tempSum<0){
                    tempSum=0;
                }
               
            }
            return maxSum;
    }
}