If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.
In previous post, we have seen breadth first search(bfs). In this post, we will see how to implement depth first search(DFS) in java.

Graph traversal Algorithms:

    Breadth first search in java Depth first search in java
In DFS,  You start with  an un-visited node and start picking an adjacent node, until you have no choice, then you backtrack until you have another choice to pick a node, if not, you select another un-visited node.

DFS can be implemented in two ways.
  • Recursive
  • Iterative

Iterative:

Depth first search can be implemented using iterative approach.
Let see with the help of example:
Depth first search example

We start with node 40. It then visit node 20, node 50, node 70 respectively as they are directly connected . After that , it backtracks to node 20 and visited node 60,node 30 and node 10 respectively.

public  void dfsUsingStack(int adjacency_matrix[][], Node node)
 {
  Stack stack=new  Stack();
  stack.add(node);
  node.visited=true;
  while (!stack.isEmpty())
  {
   Node element=stack.pop();
   System.out.print(element.data + "\t");

   ArrayList neighbours=findNeighbours(adjacency_matrix,element);
   for (int i = 0; i < neighbours.size(); i++) {
    Node n=neighbours.get(i);
    if(n!=null && !n.visited)
    {
     stack.add(n);
     n.visited=true;

    }
   }
  }
 }

Recursive:

Depth first search can be implemented using recursion too. We do not need to maintain external stack, it will be taken care by recursion.
public  void dfs(int adjacency_matrix[][], Node node)
 {

  System.out.print(node.data + "\t");
  ArrayList<Node> neighbours=findNeighbours(adjacency_matrix,node);
  for (int i = 0; i < neighbours.size(); i++) {
   Node n=neighbours.get(i);
   if(n!=null && !n.visited)
   {
    dfs(adjacency_matrix,n);
    n.visited=true;

   }
  }
 }

Java Example: 

Create DepthFirstSearchExample.java
import java.util.ArrayList;
import java.util.Stack;

public class DepthFirstSearchExample
{ 

 static ArrayList<Node> nodes=new ArrayList<Node>();
 static class Node
 {
  int data;
  boolean visited;

  Node(int data)
  {
   this.data=data;

  }
 }

 

 // find neighbors of node using adjacency matrix
 // if adjacency_matrix[i][j]==1, then nodes at index i and index j are connected
 public ArrayList<Node> findNeighbours(int adjacency_matrix[][],Node x)
 {
  int nodeIndex=-1;

  ArrayList<Node> neighbours=new ArrayList<Node>();
  for (int i = 0; i < nodes.size(); i++) {
   if(nodes.get(i).equals(x))
   {
    nodeIndex=i;
    break;
   }
  }

  if(nodeIndex!=-1)
  {
   for (int j = 0; j < adjacency_matrix[nodeIndex].length; j++) {
    if(adjacency_matrix[nodeIndex][j]==1)
    {
     neighbours.add(nodes.get(j));
    }
   }
  }
  return neighbours;
 }

 
    // Recursive DFS
 public  void dfs(int adjacency_matrix[][], Node node)
 {

  System.out.print(node.data + "\t");
  ArrayList<Node> neighbours=findNeighbours(adjacency_matrix,node);
  for (int i = 0; i < neighbours.size(); i++) {
   Node n=neighbours.get(i);
   if(n!=null && !n.visited)
   {
    dfs(adjacency_matrix,n);
    n.visited=true;

   }
  }
 }

 // Iterative DFS using stack
 public  void dfsUsingStack(int adjacency_matrix[][], Node node)
 {
  Stack<Node> stack=new  Stack<Node>();
  stack.add(node);
  node.visited=true;
  while (!stack.isEmpty())
  {
   Node element=stack.pop();
   System.out.print(element.data + "\t");

   ArrayList<Node> neighbours=findNeighbours(adjacency_matrix,element);
   for (int i = 0; i < neighbours.size(); i++) {
    Node n=neighbours.get(i);
    if(n!=null && !n.visited)
    {
     stack.add(n);
     n.visited=true;

    }
   }
  }
 }

 public static void main(String arg[])
 {

  Node node40 =new Node(40);
  Node node10 =new Node(10);
  Node node20 =new Node(20);
  Node node30 =new Node(30);
  Node node60 =new Node(60);
  Node node50 =new Node(50);
  Node node70 =new Node(70);

  nodes.add(node40);
  nodes.add(node10);
  nodes.add(node20);
  nodes.add(node30);
  nodes.add(node60);
  nodes.add(node50);
  nodes.add(node70);
  int adjacency_matrix[][] = {
    {0,1,1,0,0,0,0},  // Node 1: 40
    {0,0,0,1,0,0,0},  // Node 2 :10
    {0,1,0,1,1,1,0},  // Node 3: 20
    {0,0,0,0,1,0,0},  // Node 4: 30
    {0,0,0,0,0,0,1},  // Node 5: 60
    {0,0,0,0,0,0,1},  // Node 6: 50
    {0,0,0,0,0,0,0},  // Node 7: 70
  };
  
  DepthFirstSearchExample dfsExample = new DepthFirstSearchExample();
  
  System.out.println("The DFS traversal of the graph using stack ");
  dfsExample.dfsUsingStack(adjacency_matrix, node40);
  
  System.out.println();
  
  clearVisitedFlags();
  
  System.out.println("The DFS traversal of the graph using recursion ");
  dfsExample.dfs(adjacency_matrix, node40);

 }
 
 public static void clearVisitedFlags()
 {
  for (int i = 0; i < nodes.size(); i++) {
   nodes.get(i).visited=false;
  }
 }
}
When you run above program, you will get below output
The DFS traversal of the graph using stack 
40 20 50 70 60 30 10 
The DFS traversal of the graph using recursion 
40 10 30 60 70 20 50
Please go through data structure and algorithm interview programs for more such programs.

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.
We have already seen about breadth first search in level order traversal of binary tree.

Graph traversal Algorithms:

    Breadth first search in java Depth first search in java
Breadth first search is graph traversal algorithm. In this algorithm, lets say we start with node i, then we will visit neighbours of i, then neighbours of neighbours of i and so on.

It is very much similar to which is used in binary tree. We use queue to traverse graph. We put first node in queue . It repeatedly extracts node and put its neighbours in the queue. Only difference with respect to binary tree is that we need to track if node have been visited before or not. It can be easily done with help of boolean variable visited in the node. If node have been already visited then we won't visit it again.

Algorithm:

Steps for Breadth first search:
  1. Create empty queue and push root node to it.
  2. Do the following when queue is not empty
    • Pop a node from queue and print it.
    • Find neighbours of node with the help of adjacency matrix and check if node is already visited or not.
    • Push neighbours of node into queue if not null
Lets understand with the help of example:
Lets say graph is:
Graph

Breadth first search traversal


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class BreadthFirstSearchExample
{ 

 private Queue<Node> queue;
 static ArrayList<Node> nodes=new ArrayList<Node>();
 static class Node
 {
  int data;
  boolean visited;

  Node(int data)
  {
   this.data=data;

  }
 }

 public BreadthFirstSearchExample()
 {
  queue = new LinkedList<Node>();
 }

 // find neighbors of node using adjacency matrix
 // if adjacency_matrix[i][j]==1, then nodes at index i and index j are connected
 public ArrayList<Node> findNeighbours(int adjacency_matrix[][],Node x)
 {
  int nodeIndex=-1;

  ArrayList<Node> neighbours=new ArrayList<Node>();
  for (int i = 0; i < nodes.size(); i++) {
   if(nodes.get(i).equals(x))
   {
    nodeIndex=i;
    break;
   }
  }

  if(nodeIndex!=-1)
  {
   for (int j = 0; j < adjacency_matrix[nodeIndex].length; j++) {
    if(adjacency_matrix[nodeIndex][j]==1)
    {
     neighbours.add(nodes.get(j));
    }
   }
  }
  return neighbours;
 }

 public  void bfs(int adjacency_matrix[][], Node node)
 {
  queue.add(node);
  node.visited=true;
  while (!queue.isEmpty())
  {

   Node element=queue.remove();
   System.out.print(element.data + "\t");
   ArrayList<Node> neighbours=findNeighbours(adjacency_matrix,element);
   for (int i = 0; i < neighbours.size(); i++) {
    Node n=neighbours.get(i);
    if(n!=null && !n.visited)
    {
     queue.add(n);
     n.visited=true;

    }
   }

  }
 }

 public static void main(String arg[])
 {

   Node node40 =new Node(40);
   Node node10 =new Node(10);
   Node node20 =new Node(20);
   Node node30 =new Node(30);
   Node node60 =new Node(60);
   Node node50 =new Node(50);
   Node node70 =new Node(70);

   nodes.add(node40);
   nodes.add(node10);
   nodes.add(node20);
   nodes.add(node30);
   nodes.add(node60);
   nodes.add(node50);
   nodes.add(node70);
   int adjacency_matrix[][] = {
     {0,1,1,0,0,0,0},  // Node 1: 40
     {0,0,0,1,0,0,0},  // Node 2 :10
     {0,1,0,1,1,1,0},  // Node 3: 20
     {0,0,0,0,1,0,0},  // Node 4: 30
     {0,0,0,0,0,0,1},  // Node 5: 60
     {0,0,0,0,0,0,1},  // Node 6: 50
     {0,0,0,0,0,0,0},  // Node 7: 70
   };
   System.out.println("The BFS traversal of the graph is ");
   BreadthFirstSearchExample bfsExample = new BreadthFirstSearchExample();
   bfsExample.bfs(adjacency_matrix, node40);
 
 }
}
When you run above program, you will get below output:
The BFS traversal of the graph is 
40 10 20 30 60 50 70 
Please go through Algorithm Interview Programs in java  for more such programs.

In this post, we will see how to find Greatest common divisor(GCD) and Least Common Multiple(LCM) in java.
GCD is calculated using Euclidean algorithm and LCM is calculated using reduction by GCD

Eucid algo for calculating GCD is:

Lets say , there are two numbers , a and b so
GCD of two numbers = GCD (b,a%b) and GCD(a,0)=a

LCM can be calculated using reduction by GCD :

LCM of two numbers a and b = a * b/GCD(a,b)

Java program :

package org.arpit.java2blog;

import java.util.Scanner;

public class GCDLCMMain {

 /**
  * @author arpit mandliya
  */
 public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        System.out.println("Enter the two numbers: ");

        int number1 = input.nextInt();
        int number2 = input.nextInt();


        System.out.println("The GCD of two numbers is: " + gcd(number1, number2));
        System.out.println("The LCM of two numbers is: " + lcm(number1, number2));

        input.close();  

 }

 // Using Eucid algorithm for calculating gcd
 public static int gcd(int a,int b)
 {
  if(b==0)
   return a;
  else
   return gcd(b,a%b);
 }
 
 public static int lcm(int a,int b)
 {
  return a*b/(gcd(a,b));
 }
 
 
}

When you run above program, you will get following output:
Enter the two numbers: 
4
6
The GCD of two numbers is: 2
The LCM of two numbers is: 12
 

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview programs.
In this post, we will see how to implement insertion sort in java. Insertion sort is very much similar to bubble sort.

Insertion sort algorithm:

Insertion sort works by comparing values at index with all its prior elements.We place value at the index where there are no lesser value to the elements. So when you reach last element,we get a sorted array.

Lets see how it works:
Lets say you have array as {100,20,15,30,5,75}
  1. 1. Compare 20 with 100,as 20 is less than 100, our array will become {100,100,15,30,5,75}. We have reached to 0th index, we will place 20 to 0th index {20,100,15,30,5,75}
  2. 2. Compare 15 with 100, as it is less,our array will become {20,100,100,30,5,75}. Now compare 20 with 15, it is again less, our array will become {20,20,100,30,5,75}. As we have reached start of array again. Place 15 at 0th index.our array will become {15,20,100,30,5,75}
  3. 3. Compare 30 with 100, as it is less,our array will become {15,20,100,100,5,75}.Now compare 30 with 20 again, it is more, so we will stop here, As we reached at index where 30 is greater than 15 and 20. so we will put 30 at this index. our array will become {15,20,30,100,5,75}
  4. 4. Compare 5 with 100, as it is less, our array will become {15,20,30,100,100,75}. Now compare 30 with 5 again,it is less,our array will become {15,20,30,30,100,75}. Similarly 20 with 5, it is less,our array will become {15,20,20,30,100,75}.Compare 15 with 5 , it is  less,our array will become {15,15,20,30,100,75}.As we have reached start of array again. Place 5 at 0th index.our array will become {5,15,20,30,100,75}
  5. 5. Compare 75 with 100, it is less,so our array will become {5,15,20,30,100,100}.Now compare 30 with 75 again, it is more, so we will stop here, As we reached at index where 75 is greater than 5,15,20 and 30. so we will put 75 at this index. our array will become {5,15,20,30,75,100}
  6. 6. Finally we got sorted array.

Insertion sort example:

I have printed intermediate steps to understand it better:
public class InsertionSortMain {
 /*
  * @author: Arpit Mandliya
 */
 
 public static void main(String args[])
 {
  int  arr[]={100,20,15,30,5,75};
  insertionSort(arr);
 
 }
  
 public static int[] insertionSort(int arr[])
 {
  for (int i = 1; i < arr.length; i++) {
   int valueToSort = arr[i];
   int j;
   // If we get smaller value than valueToSort then , we stop at that index.
   
   for ( j = i; j > 0 && arr[j - 1] > valueToSort; j--) {
     arr[j] = arr[j - 1];
   }
          
   // We will put valueToSort at that index
                        arr[j] = valueToSort;
                        System.out.print("Iteration "+(i)+": ");
   printArray(arr);
  }
  
  return arr;
 }
 
 public static void printArray(int arr[])
 {
  for (int i = 0; i <arr.length; i++) {
   System.out.print(arr[i]+" ");
  }
  System.out.println();
 }
}

When you run above program, you will get following output:

Iteration 1: 20 100 15 30 5 75 
Iteration 2: 15 20 100 30 5 75 
Iteration 3: 15 20 30 100 5 75 
Iteration 4: 5 15 20 30 100 75 
Iteration 5: 5 15 20 30 75 100  

We are iterating from first element to last element.You may notice that each iteration places current element at its right place where all its prior element are less than current element.

Complexity: 

Best case: O(n)
Average case: O(nˆ2)
Worst case: O(nˆ2)
To understand more about complexity,please go through complexity of algorithm.

Please go through java interview programs for more such programs.

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.
In this post, we will see how to implement Bubble sort in java. Bubble sort is also known as sinking sort.Bubble sort is a comparison based sorting algorithm and is very easy to implement.

Bubble sort algorithm:

Bubble sort works by iterating first element to last element, comparing two adjacent elements and swapping them if they are not in correct order. Each iteration places next larger value to its correct place.

Why bubble sort is called bubble sort or sinking sort(From wikipedia):

Bubble sort can be done in ascending order or descending order.

Reason for being called Sinking sort:
The larger values might be regarded as heavier and therefore be seen to progressively sink to the bottom of the list

Reason for being called Bubble sort:
The smaller values might be regarded as lighter and therefore be seen to progressively bubble up to the top of the list

Bubble sort example:

I have printed intermediate steps to understand it better:
public class BubbleSortMain {
 /*
  * @author: Arpit Mandliya
 */
 
 public static void main(String args[])
 {
  int  arr[]={100,20,15,30,5,75,40};
  bubbleSort(arr);
 
 }
 
 public static int[] bubbleSort(int arr[])
 {
  for (int i = 0; i < arr.length; i++) {
   for (int j = 0; j < arr.length-1; j++) {
   
    if(arr[j]>arr[j+1])
    {
     int temp=arr[j];
     arr[j]=arr[j+1];
     arr[j+1]=temp;
    }
   }
   System.out.print("Iteration "+(i+1)+": ");
   printArray(arr);
  }
  return arr;
 }
 
 public static void printArray(int arr[])
 {
  for (int i = 0; i <arr.length; i++) {
   System.out.print(arr[i]+" ");
  }
  System.out.println();
 }
}

When you run above program, you will get following output:

Iteration 1: 20 15 30 5 75 40 100 
Iteration 2: 15 20 5 30 40 75 100 
Iteration 3: 15 5 20 30 40 75 100 
Iteration 4: 5 15 20 30 40 75 100 
Iteration 5: 5 15 20 30 40 75 100 
Iteration 6: 5 15 20 30 40 75 100 
Iteration 7: 5 15 20 30 40 75 100 

You may notice that each iteration places next larger element to its correct place.

Complexity: 

Best case: O(n)
Average case: O(nˆ2)
Worst case: O(nˆ2)
To understand more about complexity,please go through complexity of algorithm.

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.
Merge sort is divide and conquer sorting algorithm. It is efficient, comparison based sorting algorithm.

It works on below principle:
  • Divide list into sub list of about half size in each iteration until each sublist has only one element.
  • Merge each sublist repeatedly to create sorted list. It will run until we have only 1 sorted list. This will be the sorted list.
Below diagram will make it clearer:


Example of Merge sort:

I have printed intermediate steps to understand algorithm better.

MergeSortMain.java
public class MergeSortMain {
 
 /*
  * @author: Arpit Mandliya
 */
 static  int  arr[]={100,20,15,30,5,75,40};

 public static void main(String args[])
 {
  // Print array before merge sort
  System.out.println("Array before sorting:");
  printArray(arr,0,arr.length-1);
  System.out.println("-----------------------------");
  
  mergeSort(0,arr.length-1);
  
  System.out.println("-----------------------------");
  
  // Print array after sorting
  System.out.println("Array After sorting:");
  printArray(arr,0,arr.length-1);
  

 }

 // Recursive algorithm for merge sort
 public static void mergeSort(int start,int end)
 {
  int mid=(start+end)/2;
  if(start<end)
  {
   // Sort left half
   mergeSort(start,mid);
   // Sort right half
   mergeSort(mid+1,end);
   // Merge left and right half
   merge(start,mid,end);
  }

 }


 private static void merge(int start, int mid, int end) {
  // Initializing temp array and index
  int[] tempArray=new int[arr.length];
  int tempArrayIndex=start;
  
  System.out.print("Before Merging:  ");
  printArray(arr,start,end);
  
  int startIndex=start;
  int midIndex=mid+1;
  
  // It will iterate until smaller list reaches to the end
  while(startIndex<=mid && midIndex<=end)
  {
   if(arr[startIndex]< arr[midIndex])
   {
    tempArray[tempArrayIndex++]=arr[startIndex++];
   }
   else
   {
    tempArray[tempArrayIndex++]=arr[midIndex++];
   }
  }

  // Copy remaining elements
  while(startIndex<=mid)
  {
   tempArray[tempArrayIndex++]=arr[startIndex++];
  }
  while(midIndex<=end)
  {
   tempArray[tempArrayIndex++]=arr[midIndex++];
  }

  // Copy tempArray to actual array after sorting 
  for (int i = start; i <=end; i++) {
   arr[i]=tempArray[i];
  }
  
  System.out.print("After merging:   ");
  printArray(tempArray,start,end);
  System.out.println();
 }
 
 public static void printArray(int arr[],int start,int end)
 {
  for (int i = start; i <=end; i++) {
   System.out.print(arr[i]+" ");
  }
  System.out.println();
 }
 

}

When you run above program , you will get following output:
Array before sorting:
100 20 15 30 5 75 40 
-----------------------------
Before Merging:  100 20 
After merging:   20 100 

Before Merging:  15 30 
After merging:   15 30 

Before Merging:  20 100 15 30 
After merging:   15 20 30 100 

Before Merging:  5 75 
After merging:   5 75 

Before Merging:  5 75 40 
After merging:   5 40 75 

Before Merging:  15 20 30 100 5 40 75 
After merging:   5 15 20 30 40 75 100 

-----------------------------
Array After sorting:
5 15 20 30 40 75 100 

Complexity: 

Best case: O(nlogn) or O(n)
Average case: O(nlogn)
Worst case: O(nlogn)
To understand more about complexity,please go through complexity of algorithm.

Please go through java interview programs for more such programs.

BlockingQueue is introduced in java with concurrent package with ConcurrentHashMap. It is thread safe queue to put and take elements from it.

BlockingQueue is special type of queue which is used when one thread produces object and another thread consumes it.

Producer thread will keep inserting objects to queue until it reaches upper limit. Once this queue size has reached that limit then producer thread will get blocked and won't able to put objects into queue until consumer thread starts consuming it.

Similarly consumer thread keep taking objects from queue until queue becomes empty. Once queue becomes empty, consumer thread get blocked and waits for producer threads for inserting objects into the queue.
If you put null to BlockingQueue, it will NullPointerException at run time.
It has two important methods
put : producer thread put objects into the queue until it reaches to the limit and waits for consumer thread to take out object after that.

take : consumer thread take out object from the queue until queue becomes empty. Once queue is empty, it waits for producer thread to put object into the queue.

Example:

In this example, we will see how to use BlockingQueue.
Create Producer thread which will create objects which will be consumed by Consumer thread.
1. Producer.java
package org.arpit.java2blog;

import java.util.concurrent.BlockingQueue;

public class Producer implements Runnable {

 BlockingQueue<String> queue=null;
 
 public Producer(BlockingQueue<String> queue) {
  super();
  this.queue = queue;
 }

 @Override
 public void run() {
  for (int i = 1; i <=50; i++) {
   System.out.println("Produced item "+i);
   try {
    queue.put("item "+i);
   } catch (InterruptedException e) {
    
    e.printStackTrace();
   }
  }
  
 }

}

Create Consumer thread which will consume objects.
2. Consumer.java
package org.arpit.java2blog;

import java.util.concurrent.BlockingQueue;

public class Consumer implements Runnable {

 BlockingQueue<String> queue=null;

 public Consumer(BlockingQueue<String> queue) {
  super();
  this.queue = queue;
 }

 @Override
 public void run() {

  while(true)
  {
   try {
    System.out.println("Consumed "+queue.take());
   } catch (InterruptedException e) {
    // TODO Auto-generated catch block
    e.printStackTrace();
   }
  }
 }

}

Create main class which will start above two threads.
3. BlockingQueueMain.java
package org.arpit.java2blog;

import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;

public class BlockingQueueMain {

 public static void main(String args[])
 {
  BlockingQueue<String> queue=new ArrayBlockingQueue<String>(10);
  Producer producer=new Producer(queue);
  Consumer consumer=new Consumer(queue);
  new Thread(producer).start();
  new Thread(consumer).start();
 }
}

When you run above program , you will get following output:
Produced item 1
Produced item 2
Consumed item 1
Produced item 3
Consumed item 2
Produced item 4
Consumed item 3
Produced item 5
Consumed item 4
Produced item 6
Consumed item 5
Produced item 7
Consumed item 6
Produced item 8
Consumed item 7
Produced item 9
Consumed item 8
Produced item 10
...

Source code:

click to begin

20KB .zip

 

Java tutorial for beginners Copyright © 2012