Skip to main content

Posts

Showing posts from January, 2016

Driver program to perform operations in graph

Driver program to perform operations in graph:-



package com.problems.graph;publicclassGraphDriver{publicstaticvoidmain(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();}}

BREADTH FIRST SEARCH IN JAVA

BREADTH FIRST SEARCH IN JAVA:-


package com.problems.graph;importjava.awt.DisplayMode;importjava.util.Iterator;importjava.util.LinkedList;publicclassBFSGraph{int maxsize; Vertex vertexlist[];int matrixlist[][];int vertexcount;@SuppressWarnings({"rawtypes","unused"}) LinkedList queue;publicBFSGraph(){ maxsize=20; matrixlist=newint[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();}publicvoidaddVertex(char label){ vertexlist[vertexcount++]=new Vertex(label);}publicvoidaddEdge(int i,int j){ matrixlist[i][j]=1; matrixlist[j][i]=1;}publicvoiddisplayVertex(int v){ System.out.println(vertexlist[v].label);}publicintadjVertex(int v){for(int i=0;i<maxsize;i++){if(matrixlist[v][i]==1&& vertexlist[i].visited==false)return i;}return-1;}publicvoidbfs(){ System.out.println("in bfs"); vertexlist[0].visited=true; displayVertex(0); …

DEPTH FIRST SEARCH IN JAVA

DEPTH FIRST SEARCH IN JAVA



publicvoiddfs(){ 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);}}}

Designing graph in JAVA

How to design a Graph in JAVA:-
Vertex:-

package com.problems.graph;publicclassVertex{char label;boolean visited;publicVertex(char label){this.label=label;this.visited=false;}} Functions of Graphs
publicclassGraph{int maxsize=20; Vertex vertex[];int matrix[][];int vertexcount; Stack stackobj;publicGraph(){ vertex =new Vertex[maxsize]; matrix=newint[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();}publicvoidaddVertex(char label){ vertex[vertexcount++]=new Vertex(label);}publicvoidaddEdge(int i,int j){ matrix[i][j]=1; matrix[j][i]=1;}publicvoiddisplyVertex(int v){ System.out.println(vertex[v].label);}publicintadjVertex(int v){for(int i=0;i<maxsize;i++){if(matrix[v][i]==1&& vertex[i].visited==false)return i;}return-1;} }

Heap implementation in JAVA

In this tutorial we will see all the functionalities of heaps implemented through java language.



package com.problems.heap;publicclassHeapFunctions{//Function to generate maxheapify where root is max than childspublicvoidmaxHeapify(int Arr[],int i,int N){int largest;int left =2*i+1;//left childint 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 (A…

Priority Queue implementation in java -Arrays

Priority Queue implementation in java -Arrays


Input:- 4,8,1,7,3,5
output:-8,7,5,4,3,1,



package com.problems.heap;publicclassPriority_Queue{publicint[]priority_Queue(int arr[],int N){int[] newarray=newint[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 arraypublicvoidinsert(int Arr[],int N,int a){for(int i=0;i<N;i++){ System.out.println("insert");// search for the correct position in arrayif(a>Arr[i]){ System.out.println("call insertAtThis"); Arr=insertAtThis(Arr,N,a,i);break;}}}//insert and swappublicint[]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 functionpublicvoidprint(int Elemmm[]){for(int i=0;i<Elemmm.length;i++){ …

Driver Program to Test Tree in JAVA

Driver Program to Test Tree:-

A basic driver program to test all the functions that i will posting in my blogs using this sample tree.







package com.BST;publicclassBSTOperation{/** * @param args */publicstaticvoidmain(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(""); …

Tree Traversal in JAVA (InOder/preOrder/postOrder)

Tree Traversal in JAVA (InOder/preOrder/postOrder):-

Tree traversal can be done through three ways.

1)Inorder:-

Go recursively to the left node.
Read a node
Go recursively to the right node.

2)Pre Order.

Read a node
Go recursively to the left node.
Go recursively to the right node.


2)Post Order.


Go recursively to the left node.
Go recursively to the right node.
Read a node



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

Insertion in a Binary Search Tree JAVA

Insertion in a Binary Search Tree :_

Insertion in a BST follow simple operations. All the elements less than root lies on left subtree and all the elements greater than root lies on right subtree.

Every BST class will have a root variable of Node type that represents the head node of the tree.


publicclassBinarySearchTree{ Node root;publicBinarySearchTree(){ 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);}elseif(node.data<root.data){ root.left=insert(node,root.left);}}return root;}}

How to design a Node in Tree?

How to design a Node in Tree?

There are three main components of a tree in a node.

 1) Integer holding data.
2) Left pointer holding node in a left subtree.
3) Right pointer holding node in a right subtree.

The following design is having data of int type and left,right pointers of a node to the subtrees.


package com.BST;publicclassNode{int data; Node left; Node right;/** * @return the data */publicNode(int data){this.left=null;this.right=null;this.data=data;}publicintgetData(){return data;}/** * @param data the data to set */publicvoidsetData(int data){this.data= data;}/** * @return the left */public Node getLeft(){return left;}/** * @param left the left to set */publicvoidsetLeft(Node left){this.left= left;}/** * @return the right */public Node getRight(){return right;}/** * @param right the right to set */publicvoidsetRight(Node right){this.right= right;}/* (non-Javadoc) * @see java.lang.Object#toString() */@Overridepublic String toString(){return"Node [data=&quo…

.