package com.problems.graph;

public class GraphDriver {

 public static void main(String[] args)
 {
  BFSGraph g=new BFSGraph();
  g.addVertex('A');
  g.addVertex('B');
  g.addVertex('C');
  g.addVertex('D');
  g.addVertex('E');
  g.addVertex('F');
  g.addVertex('G');
  g.addVertex('H');
 
  g.addEdge(0, 1);
  g.addEdge(1, 2);
  g.addEdge(1, 7);
  g.addEdge(2, 3);
  g.addEdge(2, 4);
  g.addEdge(7, 4);
  g.addEdge(4, 5);
  g.addEdge(4, 6);
  g.bfs();
 }
 
}

package com.problems.graph;

import java.awt.DisplayMode;
import java.util.Iterator;
import java.util.LinkedList;




public class BFSGraph {

 int maxsize;
 Vertex vertexlist[];
 int matrixlist[][];
 int vertexcount;
 @SuppressWarnings({ "rawtypes", "unused" })
 LinkedList queue;
 
 public BFSGraph()
 {
  maxsize=20;
  matrixlist=new int[maxsize][maxsize];
  vertexlist=new Vertex[maxsize];
  for(int i=0;i<maxsize;i++)
  {
   for(int j=0;j<maxsize;j++)
   {
    matrixlist[i][j]=0;
   }
  }
  queue= new LinkedList();
  
 }
 
 public void addVertex(char label)
 {
  vertexlist[vertexcount++]=new Vertex(label);
 }
 public void addEdge(int i,int j)
 {
  matrixlist[i][j]=1;
  matrixlist[j][i]=1;
 }
 
 public void displayVertex(int v)
 {
  System.out.println(vertexlist[v].label);
 }
 
 public int adjVertex(int v)
 {
  for(int i=0;i<maxsize;i++)
  {
   if(matrixlist[v][i]==1 && vertexlist[i].visited==false )
    return i;
  }
  return -1;
 }
 
 public void bfs()
 {
  System.out.println("in bfs");
  vertexlist[0].visited=true;
  displayVertex(0);
  queue.add(0);
  int v2;
  while(!queue.isEmpty())
  {
   int v1=(Integer) queue.remove();
   System.out.println("removed"+v1);
   while( (v2=adjVertex(v1))!=-1)
   {
   vertexlist[v2].visited=true;
   displayVertex(v2);
   queue.add(v2);
   }
  }
  for(int j=0;j<vertexcount;j++)
  {
   vertexlist[j].visited=false;
  }
 }
}

public void dfs()
 {
  
  vertex[0].visited=true;
  displyVertex(0);
  stackobj.push(0);
  
  while(!stackobj.isEmpty())
  {
   int v=adjVertex((Integer) stackobj.peek());
   if(v==-1)
   {
    stackobj.pop();
   }
    else{
     vertex[v].visited=true;
     displyVertex(v);
     stackobj.push(v);
     
    }
   }
  }
  

package com.problems.graph;

public class Vertex{
  char label;
  boolean visited;
 
  public Vertex(char label){
   this.label=label;
   this.visited=false;
  }
}

public class Graph {

 int maxsize=20;
 Vertex vertex[];
 int matrix[][];
 int vertexcount;
 Stack stackobj;

 public Graph()
 {
  vertex = new Vertex[maxsize];
  matrix=new int[maxsize][maxsize];
  vertexcount=0;
  for(int i=0;i<maxsize;i++)
  {
   for(int j=0;j<maxsize;j++)
   {
    matrix[i][j]=0;
   }
  }
  stackobj=new Stack();   
 }
 
 public void addVertex(char label)
 {
  vertex[vertexcount++]=new Vertex(label);
 }
 public void addEdge(int i,int j)
 {
  matrix[i][j]=1;
  matrix[j][i]=1;
 }
 
 public void displyVertex(int v)
 {
  System.out.println(vertex[v].label);
 }
 

 public int adjVertex(int v)
 {
  for(int i=0;i<maxsize;i++)
  {
   if(matrix[v][i]==1 && vertex[i].visited==false )
    return i;
  }
  return -1;
 }
}

package com.problems.heap;



public class HeapFunctions {
  
 //Function to generate maxheapify where root is max than childs
 public void maxHeapify(int Arr[],int i,int N)
 {
    int largest;
    int left = 2*i+1;     //left child
       int right = 2*i +2;  //right child
       
       System.out.println("left"+" "+left);
       System.out.println("right"+" "+right);
       System.out.println("Max size"+" "+N);
       if(left< N && Arr[left] > Arr[i] )
       {
       largest = left;
       System.out.println("largest left"+largest);
       }
       else
       {
            largest = i;
            System.out.println("largest i"+largest);
       }
       if(right < N && Arr[right] > Arr[largest] )
       {
       largest = right;
       System.out.println("largest right"+largest);
       }
       if(largest != i )
       {
        System.out.println("No largest"+largest);
           Arr=swap (Arr, i , largest);
           maxHeapify (Arr,largest,N);
       } 
 }
 
 //function to generate minheapify where root is minimum than childs
 public void minHeapify(int Arr[],int i,int N)
 {
    int smallest;
    int left = 2*i+1;     //left child
       int right = 2*i +2;  //right child
       
       if(left< N && Arr[left]<  Arr[i] )
       {
       smallest = left;
       System.out.println("smallest left"+smallest);
       }
       else
       {
        smallest = i;
            System.out.println("smallest i"+smallest);
       }
       if(right < N && Arr[right] < Arr[smallest] )
       {
        smallest = right;
       System.out.println("smallest right"+smallest);
       }
       if(smallest != i )
       {
        System.out.println("No largest"+smallest);
           Arr=swap (Arr, i , smallest);
           minHeapify (Arr,smallest,N);
       } 
 }
 
 //function to swap elements in an Array
 public int[] swap(int Arr[],int x,int y)
 {
  System.out.println("in swap");
  System.out.println("x"+x+"y"+y);
  int temp=Arr[x];
  Arr[x]=Arr[y];
  Arr[y]=temp;
  return Arr;
 }
 
 //function to build maximum heap
 void build_maxheap (int Arr[ ],int N)
 {
     for(int i =N/2; i >= 0 ; i-- )
     {
         maxHeapify (Arr, i,N) ;
     }
 }
 
 //function to build minimum heap
 void build_minheap (int Arr[ ],int N)
 {
     for(int i =N/2; i >= 0 ; i-- )
     {
         minHeapify (Arr, i,N) ;
     }
 }
 
 
 //heap sorting 
 void heap_sort(int Arr[ ],int N)
 {
     int heap_size = N;
    
     for(int i = N-1; i>=1 ; i-- )
     {
      build_maxheap(Arr,heap_size);
      System.out.println("this"+i);
      System.out.println("i="+i+"");
         Arr=swap(Arr,0, i);
         heap_size = heap_size-1;
         System.out.println("calling max heapify"+heap_size);
        
     }
 }
 
 
 
}

package com.problems.heap;

public class HeapOperations {


 
 public static void main(String[] args)
 {
  int Elem[]={4,3,7,1,8,5};
 HeapFunctions func=new HeapFunctions();
 //max heapify
 func.maxHeapify(Elem, 6, Elem.length);
 System.out.println("min heap");
 func.build_maxheap(Elem, Elem.length);
 System.out.println("");
 for(int i=0;i<Elem.length;i++)
 {

  System.out.print(Elem[i]+",");
 
 }
 System.out.println("");
 //
 
 //min heapify
 System.out.println("min heap");
 func.build_minheap(Elem, Elem.length);
 System.out.println("");
 for(int i=0;i<Elem.length;i++)
 {
  
  System.out.print(Elem[i]+",");
  
 }
 System.out.println("");
 //
 
 //heap sort
 System.out.println("Heap Sort length"+ Elem.length);
 int Elemm[]={4,3,7,1,8,5};
 
 func.heap_sort(Elemm, Elemm.length);
 
 System.out.println("");
 System.out.println("sorted array");
 for(int i=0;i<Elemm.length;i++)
 {
  
  System.out.print(Elemm[i]+",");
  
 }
 
 //
 }
}

package com.problems.heap;

public class Priority_Queue {

 public int[] priority_Queue(int arr[],int N)
 {
  int[] newarray=new int[N];
  
  for(int i=0;i<N;i++)
  {
   System.out.println(i+"priority_Queue"+arr[i]);
   insert(newarray,N,arr[i]);
  }
  return newarray;
 }
 
 //inserting new element in array
 public void insert(int Arr[],int N,int a)
 {
  for(int i=0;i<N;i++)
  {
   System.out.println("insert");
   // search for the correct position in array
   if(a>Arr[i])
   {
    System.out.println("call insertAtThis");
    Arr=insertAtThis(Arr,N,a,i);
    break;
   }
  }
 }
 
 //insert and swap
 public int[] insertAtThis(int arr[],int N,int a,int index)
 {
  System.out.println("insertAtThis");
  System.out.println("index"+index);
  int j=index;
  N=N-1;
  while(N!=index)
  {
   arr[N]=arr[N-1];
   N--;
   
  }
  
  arr[index]=a;
  print(arr);
  return arr;
  
 }
 
 //print function
 public void print(int Elemmm[])
 {
  for(int i=0;i<Elemmm.length;i++)
  {
   
   System.out.print(Elemmm[i]+",");
   
  }
  System.out.println("");
 }
 
 
 public static void main(String[] args) {
  // TODO Auto-generated method stub
 Priority_Queue func=new Priority_Queue();
  int Elemmm[]={4,8,1,7,3,5};
  System.out.println("");
  System.out.println("priority queue");
  Elemmm=func.priority_Queue(Elemmm, Elemmm.length);
  System.out.println("");
  func.print(Elemmm);
 }

}

package com.BST;

public class BSTOperation {

 /**
  * @param args
  */
 public static void main(String[] args) {
  
  BinarySearchTree btree=new BinarySearchTree();
  btree.inorder(btree.root);
  Node node1=new Node(8);
  Node node2=new Node(3);
  Node node3=new Node(1);
  Node node4=new Node(6);
  Node node5=new Node(4);
  Node node6=new Node(7);
  Node node7=new Node(10);
  Node node8=new Node(14);
  Node node9=new Node(13);
  
  btree.root=btree.insert(node1, btree.root);
  btree.inorder(btree.root);
  System.out.println("");
  btree.root=btree.insert(node2, btree.root);
  btree.inorder(btree.root);
  System.out.println("");
  btree.root=btree.insert(node3, btree.root);
  btree.inorder(btree.root);
  System.out.println("");
  btree.root=btree.insert(node4, btree.root);
  btree.inorder(btree.root);
  System.out.println("");
  btree.root=btree.insert(node5, btree.root);
  btree.inorder(btree.root);
  System.out.println("");
  btree.root=btree.insert(node6, btree.root);
  btree.inorder(btree.root);
  System.out.println("");
  btree.root=btree.insert(node7, btree.root);
  btree.inorder(btree.root);
  System.out.println("");
  btree.root=btree.insert(node8, btree.root);
  btree.inorder(btree.root);
  System.out.println("");
  btree.root=btree.insert(node9, btree.root);
  System.out.println("Inorder");
  btree.inorder(btree.root);
  System.out.println("");
  System.out.println("post order");
  btree.postOrder(btree.root);
  System.out.println("");
  System.out.println("pre order");
  btree.preOrder(btree.root);
 }

}

public void inorder(Node root)
 {
  
  if(root==null)
  {
  return;
  }
  
  inorder(root.left);
  System.out.print(root.data+",");
  inorder(root.right);
  
  }
 
 public void preOrder(Node root)
 {
  
  if(root==null)
  {
  return;
  }
  
  System.out.print(root.data+",");
  preOrder(root.left);
  preOrder(root.right);
  
  }
 public void postOrder(Node root)
 {
  
  if(root==null)
  {
  return;
  }
  
  postOrder(root.left);
  
  postOrder(root.right);
  System.out.print(root.data+",");
  }

public class BinarySearchTree {

 Node root;
 
 public BinarySearchTree()
 {
  root=null;
 }
 

 public Node insert(Node node,Node root)
 {
  if(root==null)
  {
   root=node;
   return root;
  }
  else{
  
  if(node.data>root.data)
  {
   
   root.right=insert(node,root.right);
  
  }
  else if(node.data<root.data)
  {
   root.left=insert(node,root.left);
  }
  
  }
  return root;
 }
}

package com.BST;

public class Node {

 int data;
 Node left;
 Node right;
 /**
  * @return the data
  */
 public Node(int data)
 {
  this.left=null;
  this.right=null;
  this.data=data;
 }
 
 public int getData() {
  return data;
 }
 /**
  * @param data the data to set
  */
 public void setData(int data) {
  this.data = data;
 }
 /**
  * @return the left
  */
 public Node getLeft() {
  return left;
 }
 /**
  * @param left the left to set
  */
 public void setLeft(Node left) {
  this.left = left;
 }
 /**
  * @return the right
  */
 public Node getRight() {
  return right;
 }
 /**
  * @param right the right to set
  */
 public void setRight(Node right) {
  this.right = right;
 }
 /* (non-Javadoc)
  * @see java.lang.Object#toString()
  */
 @Override
 public String toString() {
  return "Node [data=" + data + ", left=" + left + ", right=" + right
    + "]";
 }
 
 

}