Stack
Stack is a data structure in which last element inserted is the first to come out, Last In First Out (LIFO).
Static Stack is implemented with array, and pointer (end) for inserting and removing element from the array. Stack has push, pop, display methods.
class stk{
int data[];
int top;
public stk(){
data = new int[10];
top = -1;
}
public void push(int x){
if(top<10){
++top;
data[top] = x;
}
}
public void pop(){
if(top>-1){
System.out.println("Popped: "+stk[top]);
--top
}
}
}
Queue
Queue is a data structure in which first element inserted is the first element to come out first (FIFO).
Static queue is implemented using an array and two pointers (ends): rear and front. Elements are inserted from rear end and removed from front end.
class qu{
int rear, front;
int data[];
public qu(){
rear = -1;
front = 0;
data = new int[10];
}
public void insert(int a){
if(rear <10){
++rear;
data[rear] = a;
}
}
public void remove(){
if(rear == -1){
System.out.println("Removed: "+data[front]);
++front;
}
}
}
Link List
This code snippet shows how to create a simple linked list with very few nodes. A node class is defined, it has two attributes: data and next; methods: two constructors, and method to get value stored in a node.
class node{
int data;
node next;
public node(int d){
data = d;
next = null;
}
public node(){
data = 0;
next = null;
}
public int getData(){
return data;
}
}
Another class Linked_LIST is defined with objects of node class as attributes, a constructor, method to insert data after given node, method to delete node after given node.
class Linked_LIST{
node n1,n2,n3,n4,n5;
public Linked_LIST(){
n1 = new node(33);
n2 = new node(44);
n3 = new node(55);
n4 = new node(66);
n5 = new node(99);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
}
public void insertAfter(int p, int d){
int i;
node t = n1;
for(i=1;i<p;i++){t = t.next;}
node nn = new node(d);
nn.next = t.next;
t.next = nn;
}
public void deleteAfter(int p){
int i;
node t = n1;
for(i=1;i<p;i++){t = t.next;}
node temp = t.next;
t.next = temp.next;
temp = null;
}
public void show(){
node t; int i=1;
for(t = n1; t!=null;t=t.next){
System.out.println(i+" : "+t.getData());
++i;
}
}
}
class Linked_List_Demo{
public static void main(String[] owl){
Linked_LIST l1 = new Linked_LIST();
l1.show();
l1.insertAfter(2, 200);
l1.show();
l1.deleteAfter(2);
l1.show();
}
}
Circular list
In circular List the insertion is possible even the end of the list is reached and empty positions are left in the beginning of the list.
class cq{
int rear;
int counter;
int front;
String[] data;
public cq(){
counter = 0;
front = 0;
rear = -1;
data = new String[5];
}
public void insert(String o){
if(rear < counter){
rear = (rear+1)%5;
data[rear] = o;
++counter;
}
}
public void remove(){
if(counter !=0){
System.out.println("Removed Item: "+data[front]);
front = (front+1)%5;
--counter;
}
}
public void show(){
int i=front;
do{
System.out.println("Data at "+i
+" is: "+data[i]);
i=(i+1)%5;
}while(i!=rear);
}
public static void main(String[] aargs){
cq c = new cq();
c.insert("chair");
c.insert("bench");
c.insert("desk");
c.show();
c.insert("sofa");
c.insert("Dinosaur");
c.insert("tea table");
c.show();
}
}
Output:
Data at 0 is: chair
Data at 1 is: bench
Data at 0 is: tea table
Data at 1 is: bench
Data at 2 is: desk
Data at 3 is: sofa
Data at 4 is: Dinosaur
MenuDriven Example
import java.util.*;
class menuDri{
public static void main(String [] aaaaaaaaaaa){
int op;
String str1="Tiger";
Scanner sc = new Scanner(System.in);
while(true){
System.out.println("\n1. Enter String ");
System.out.println("2. Display Entered String in Reverse ");
System.out.println("3. Display Length of Entered String ");
System.out.println("4. Exit ");
System.out.println("Enter Your Choice: ");
op = sc.nextInt();
switch(op){
case 1: System.out.println("Enter String: ");
str1 = sc.next();
break;
case 2: System.out.println("Reverse of "+str1);
for(int i=str1.length()-1;i>=0;i--)
System.out.print(str1.charAt(i));
break;
case 3:System.out.println("Length of "+str1+" is "+str1.length());
break;
default:
sc.close();
System.exit(0);
break;
}
}
}
}
MenuDriven Circular Queue
import java.util.*;
class cp_menu{
int rear;
int counter;
int front;
String[] data;
public cp_menu(){
counter = 0;
front = 0;
rear = -1;
data = new String[5];
}
public void insert(String o){
if(rear < counter){
rear = (rear+1)%5;
data[rear] = o;
++counter;
}
}
public void remove(){
if(counter !=0){
System.out.println("Removed Item: "+data[front]);
front = (front+1)%5;
--counter;
}
}
public void show(){
int i=front;
do{
System.out.println("Data at "+i+" is: "+data[i]);
i=(i+1)%5;
}while(i!=rear);
}
public static void main(String[] aargs){
cp_menu c = new cp_menu();
int op=4;
Scanner ss = new Scanner(System.in);
while(true){
System.out.println("1.Insert");
System.out.println("2.Remove");
System.out.println("3.Display");
System.out.println("4.Exit");
System.out.println("Choice:");
op = ss.nextInt();
if(op == 1){
System.out.println("Enter Word:");
String s = ss.next();
c.insert(s);
}else if(op == 2){
c.remove();
}else if(op == 3){
c.show();
}else{
ss.close();
System.exit(1);
}
}
}
}
Binary Search Tree (BST)
Binary Search Tree is a tree in which each node can have only 0, 1, or 2 children. Nodes in the left of root is less than root node and nodes in the right of the root is greater than root node. This rule is same for the sub trees also.
BST can be traversal in following ways:
- Preorder: First visit root node, then left child, then right child
- Inorder: First visit left child, then root node, then right child. This traversal displays node in ascending order.
- Post Order: First visit left child, then right child, the root.
If the left subtree or right subtree of the BST is lengthy compared to each other, then searching in the lengthy subtree will take more time than shorter subtree. The height of left and right subtrees are not balanced in the BST. This creates long search time for the lengthy subtree.
import java.util.*;
class node{
int data;
node left,right;
public node(int d){
data = d;
left = right = null;
}
}
class binary_tree{
node root=null;
node temp;
public void insertNode(node n){
if(root ==null){
root = n;
}else{
temp = root;
while(temp!=null){
if(temp.data>n.data){
if(temp.left == null){
temp.left = n;
break;
}else
temp = temp.left;
}
else if(temp.data <=n.data){
if(temp.right == null){
temp.right = n;
break;
}else
temp = temp.right;
}
}
}
}
public void inorder(node r){
if(r!=null){
inorder(r.left);
System.out.println(" "+r.data);
inorder(r.right);
}
}
public node getRoot(){
return root;
}
}
class binary_tree_demo{
public static void main(String[] args){
node temp;
Scanner sc = new Scanner(System.in);
int option,value;
binary_tree bt = new binary_tree();
while(true){
System.out.println("\n1.InsertNode\n2.DisplayTree\n8.Exit");
option = sc.nextInt();
switch(option){
case 1:System.out.println("Enter a value:");
value = sc.nextInt();
temp = new node(value);
bt.insertNode(temp);
break;
case 2: System.out.println("Display Tree:");
bt.inorder(bt.getRoot());
break;
case 8:System.exit(0);
}
}
}
}
AVL Tree
AVL tree is a height balance tree. If height of left and right sub trees of a binary search tree (BST) differs highly, then searching in that BST will be slow. Searching in lengthy tree takes more time than short tree.
To, remove this ineffiency of BST, AVL tree, a height balanced tree is developed. In AVL tree height of sub trees never differs more than 1, it can be -1, 0, or 1. Height of the AVL tree is adjusted at the time of inserting new node, if the insertion of new node voilates height factor (-1, 0 or 1) of the tree, then rotation of nodes is done to adjust the height factor of the tree.
- Left Rotation
- Right Rotation
- Double Rotation
class AVLNode {
int key, ht;
AVLNode left, right;
AVLNode(int d) {
key = d;
ht = 1;
}
}
class AVLTree {
AVLNode root;
// A utility function to get the ht of the tree
int getheight(AVLNode N) {
if (N == null)
return 0;
return N.ht;
}
int getMaxHeight(int x, int y) {
return (x > y) ? x : y;
}
AVLNode rightRotate(AVLNode b) {
AVLNode a = b.left;
AVLNode T2 = b.right;
// Perform rotation
a.right = b;
b.left = T2;
// Update hts
b.ht = getMaxHeight(getheight(b.left), getheight(b.right)) + 1;
a.ht = getMaxHeight(getheight(a.left), getheight(a.right)) + 1;
return a;
}
AVLNode leftRotate(AVLNode a) {
AVLNode b = a.right;
AVLNode T2 = b.left;
b.left = a;
a.right = T2;
a.ht = getMaxHeight(getheight(a.left), getheight(a.right)) + 1;
b.ht = getMaxHeight(getheight(b.left), getheight(b.right)) + 1;
return b;
}
int getBalance(AVLNode N) {
if (N == null)
return 0;
return getheight(N.left) - getheight(N.right);
}
AVLNode insert(AVLNode AVLNode, int key) {
if (AVLNode == null)
return (new AVLNode(key));
if (key < AVLNode.key)
AVLNode.left = insert(AVLNode.left, key);
else if (key > AVLNode.key)
AVLNode.right = insert(AVLNode.right, key);
else
return AVLNode;
AVLNode.ht = 1 + getMaxHeight(getheight(AVLNode.left),
getheight(AVLNode.right));
int bal = getBalance(AVLNode);
if (bal > 1 && key < AVLNode.left.key)
return rightRotate(AVLNode);
if (bal < -1 && key > AVLNode.right.key)
return leftRotate(AVLNode);
if (bal > 1 && key > AVLNode.left.key) {
AVLNode.left = leftRotate(AVLNode.left);
return rightRotate(AVLNode);
}
if (bal < -1 && key < AVLNode.right.key) {
AVLNode.right = rightRotate(AVLNode.right);
return leftRotate(AVLNode);
}
return AVLNode;
}
void preOrder(AVLNode AVLNode) {
if (AVLNode != null) {
System.out.print(AVLNode.key + " ");
preOrder(AVLNode.left);
preOrder(AVLNode.right);
}
}
void inOrder(AVLNode r){
if(r!=null){
inOrder(r.left);
System.out.println(r.key+ " ");
inOrder(r.right);
}
}
public static void main(String[] args) {
AVLTree tree = new AVLTree();
tree.root = tree.insert(tree.root, 10);
tree.root = tree.insert(tree.root, 20);
tree.root = tree.insert(tree.root, 30);
tree.root = tree.insert(tree.root, 40);
tree.root = tree.insert(tree.root, 50);
tree.root = tree.insert(tree.root, 25);
System.out.println("Preorder traversal" +
" of constructed tree is : ");
tree.preOrder(tree.root);
tree.inOrder(tree.root);
}
}
Graph
Directed Graph
Undirected Graph
Cycle in the Graph
Minimum Spanning Tree
Shortest Path
Topological sort
Connectivity in a graph
Connectivity in Directed Graph
Network
- Flow through an edge e can’t be greater than its capacity
- The total flow coming to a vertex v is equal to the total flow coming from it.
The problem is to maximize the flow f so that the sum of total of output is maximum value for any possible function f. This is called a maximum-flow or max-flow problem.
Graph Implementation as Adjacency List
import java.util.*;
class Graph_as_adjacencyList {
private int V; // Number of vertices
private ArrayList[] adj;
Graph_as_adjacencyList(int v)
{
V = v;
adj = new ArrayList[v];
for (int i = 0; i < v; ++i)
adj[i] = new ArrayList();
}
void addEdge(int v, int w)
{
adj[v].add(w); //Creating an edge.
}
void showGraph(){
for(int i=0;i<v;i++) for(int="" j="0;j<adj[i].size();j++){" system.out.println("edges:="" "+i+"<--="">"+adj[i].get(j));
}
}
}
class Graph_as_adjacencyList_Demo{
public static void main(String[] args){
Graph_as_adjacencyList g = new Graph_as_adjacencyList(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(0, 3);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
g.addEdge(3, 1);
g.showGraph();
}
}
Sortings
QuickSort
QuickSort(list[]){
if(length of list > 1){
pivot = select an first item of the list;
while(length of list > 0){
if( element of list < pivot){
place element in left of pivot (sublistleft);
}
if (element of list > pivot){
place element in right of pivot (sublistright);
}
}
QuickSort(sublistleft);
QuickSort(sublistright);
}
}
MergeSort
MergeSort(list){
if (size of list >= 2){
MergeSort(left half of list);
MergeSort(right half of list);
merge(left half of list and right half of list);
}
}
merge(list1,list2,list3){
initialize i1,i2,i3 properly;
while( both list1 and list2 have elements){
if(list2[i2] < list3[i3]){
list1[i1++] = list2[i2++];
list1[i1++] = list3[i3++];
}
store the remaining elements of either list2 or list3 to list1;
}
}
Heap Sort
Heap Sort was invented by John Williams. Heap sort uses approach similar to Selection Sort.
Heap sort uses a heap tree. There are two types of heap: max heap and min heap. A min heap tree is a binary tree having given properties:
- value stored in children is greater than value stored in its parent node.
- tree is perfectly balanced, and the leaves are in the last level are all in the leftmost positions.
heapsort(list a){
transform a to heap tree;
for(int i = a.length; i > 1;i--){
swap the root with the element in position i of the heap tree;
restore the heap property for the tree with element a[0] to a[i-1];
}
}
Quick Sort, Merge Sort and Heap sort’s running time is O(n lgn). Bubble sort, insertion sort and selection sort take O(n2) time. Algorithms with O(n2) take longer time to complete their operations than algorithms with O(n lgn) running time.
Radix Sort Algorithm
Consider a list of number
make all numbers of list of same digits by appending zero's in beginning of each numbers if required
for(int j=length of number;j>=0;j--){
for(int i = 1 ;i< list.size;i++){
compare element[i].digit[j] with element[i-1].digit[j];
order elements
}
}
Note:
- compare the last digit of each number of the list and order the numbers accordingly to the last digit.
- compare the second last digit of each number of the ordered list and order the numbers accordingly to the second last digit
Selection Sort
SelectionSort(list){
for(i=0;i<list.length;i++){
find largest element of the list of size: size(list)-i;
swap the found largest element with the last element of the list of size: size(list)-i
}
}
Insertion sort
InsertionSort(list){
for(i=1;i<list.size();i++){
temp = list[i];
j = i-1;
shift all elements before list[j] greater than temp by one position;
place temp in its proper position;
}
}
B Tree
A B Tree is multiway search tree having order m, m indicates how many children a node will have. B tree has following properties:
- If root is not leaf, it has at least two subtrees.
- Each intermediate node hold k – 1 keys and k references to subtrees where ceiling(m/2) <= k <=m.
- Each leaf node has k-1 keys where ceiling(m/2) <= k <=m
- All the leaves are in same level.
B Tree Node
class BTreeNode{
int m, int numberofkeys;
boolean leaf = true;
int keys[];
BTreeNode references[];
BTreeNode(int m, int n, int key){
this.m = m;
this.numberofkeys = n;
keys = new int[m-1];
references = new BTreeNode[m];
keys[0] = key;
for(int i=0;i<m;i++)
references[i] = null;
}
}
Algorithm to insert keys in B-trees:
BTreeInsert(key){
find a leaf node to insert key;
while(true){
find a proper position in found leaf node for key;
if node is have empty space{
insert key and increment numberofkeys;
return;
}else{
split node into two nodes: n1 and n2, n1 = node and n2 is new one;
distribute keys and references between n1 and n2 without violating definition of B Tree, initialize numberofkeys correctly;
key = the last key of n1;
if node is root{
create a new root node as parent of n1 and n2;
put key and references to n1 and n2 in the root, set it numberofkeys to 1;
return;
}else{
node = its parent;
}
}
}
}
Graph _ II
Cycle Detection using Depth First Search (DFS)in Graph Algorithm
int i = 0;
edges is array of edges;
//method num(vertex) assign number of the vertex pass to it.
cycleDetectionDFS(v){
num(v) = i++;
for all vertices u adjacent to v
if(num(v) == 0){
add edge uv to edges
cycleDetection DFS(u);
}else{
return cycle Detected;
}
}
Spanning Trees: Kruskal’s Algorithm
Minimum spanning tree is a tree in which the sum of the weight of its edges is minimal
Kruskal’s Algorithm
Graph must be connected undirected graph
E is number of edges;
V is number of vertices;
KruskalAlgorithm(Grapgh G){
tree = null;
edges = all the edges of graph sorted by weight;
for(i=1;i<=|E| and |tree| < |V|-1;i++){
if(e
i
from edges does not form a cycle with edges in tree){
add e
i
to tree;
}
}
}
Topological Sort
In many situations, tasks have to be performed in sequence as the order of tasks matters, it matters which task should be performed first. The dependencies between tasks can be show using directed graph (digraph) without cycle.
int i = 0;
V is number of vertices;
TopologicalSort(digraph){
for i=1 to |V|
find a minimal vertex v, vertex with minimum indegree or indegree = 0;
num(v) = i++;
perform depth first search for vertex v until vertex without any out going edge is reached, store
vertices in stack;
pop that vertex from stack, check if other edges can be traversed from elements of stack, if not
pop them out.
}
Connectivity
An undirected graph is called connected if there is a path between any two vertices of the graph. A vertex removal of which splits a graph into subgraphs is called articulation point or cut vertex. A graph is called n-connected if there are at least n different paths any two vertices without any vertex in common between those paths
Network
A network can be explained as a network of pipelines used to deliver water to one destination from a source. Many pipes of different diameters with may pumping stations will be used to deliver water from source to destination, pumping power of stations will be different.
Dynamic Stack
Dynamic stack is FIFO data structure in which any number of data can be inserted. It is implemented using Linked List, in which only one end is defined to insert (push) or remove (pop) elements named top.
import java.util.*;
class dynamicStack{
public static void main(String args[]){
node temp, top=null;
System.out.print("Creating Dynamic Stack!!!");
int choice;
String str;
Scanner sc = new Scanner(System.in);
while(true){
System.out.print("\n1.Push\n2.Pop\n3.Show\nChoice:");
choice = sc.nextInt();
switch(choice){
case 1:
System.out.println("Enter Data:");
str = sc.nextLine();
str = sc.nextLine();
temp = new node();
temp.data = str;
temp.address = null;
if(top == null){
top = temp;
}else{
temp.address = top;
top = temp;
}
break;
case 2: System.out.println("Popping Stack!!!");
System.out.println("Top of Stack : "+top.data);
temp = top.address;
top = temp;
temp = null;
break;
case 3: System.out.println("Show contents of Stack: \n");
if(top != null){
for(temp=top;temp.address!=null;temp=temp.address){
System.out.print(temp.data+" ");
}
System.out.print(temp.data+" ");
}
break;
default: System.exit(0);
break;
}
}
}
}
Output:
Creating Dynamic Stack!!!
1.Push
2.Pop
3.Show
Choice:1
Enter Data:
apple
1.Push
2.Pop
3.Show
Choice:1
Enter Data:
mango
1.Push
2.Pop
3.Show
Choice:3
Show contents of Stack:
mango apple
1.Push
2.Pop
3.Show
Choice:2
Popping Stack!!!
Top of Stack : mango
1.Push
2.Pop
3.Show
Choice:
Dynamic Queue
Queue is a data structure in which elements are added or inserted from end called rear and elements are removed from another end called front. In queue First element inserted is the first element to be removed. So, Queue is also known as First In First Out (FIFO) Data structure. Queue can be static or dynamic. If queue is implemented in array then it will be static queue. If queue is implemented using concept of linked list then it will be dynamic queue.
Here, is a code to implement queue dynamically. A node contained data field (here, string), and address field is defined. Three objects of node class is created: objects are temp, front, and rear. Both rear and front are assigned null. Object of Scanner is created to take data for node and for provided value action to perform. This is a menu driven program. Users can insert, remove and view contents of queue. Menu is written inside while loop so, user can run loop as s/he likes.
case 1 is for adding or inserting elements to the queue. if rear is null then queue is empty.
case 2 is for removing element from the queue.
case 3 is for displaying content of queue
*/
import java.util.*;
class dynamicQueue{
public static void main(String args[]){
node temp, front=null,rear=null;
System.out.println("Creating Dynamic Queue!!!");
int choice;
String str;
Scanner sc = new Scanner(System.in);
while(true){
System.out.println("\n1.Insert\n2.Remove\n3.Show\nChoice:");
choice = sc.nextInt();
switch(choice){
case 1: System.out.println("Enter Data:");
str = sc.nextLine();
str = sc.nextLine();
temp = new node();
temp.data = str;
temp.address = null;
if(rear == null){
rear = temp;
front = temp;
}else{
rear.address = temp;
rear = temp;
}
break;
case 2: System.out.println("Removing Element From Queue!!!");
System.out.println("Element Removed : "+front.data);
if(front == rear)
System.out.println("Queue is Empty");
else{
temp = front;
front = front.address;
temp = null;
}
break;
case 3: System.out.println("Show contents of Queue: \n");
for(temp=front;temp!=rear;temp=temp.address){
System.out.print(temp.data+" ");
}
System.out.print(temp.data+" ");
break;
case 4: System.exit(0);
break;
}
}
}
}
//Output:
Creating Dynamic Queue!!!
1.Insert
2.Remove
3.Show
Choice:
1
Enter Data:
movies
1.Insert
2.Remove
3.Show
Choice:
1
Enter Data:
books
1.Insert
2.Remove
3.Show
Choice:
3
Show contents of Queue:
movies books
1.Insert
2.Remove
3.Show
Choice:
2
Removing Element From Queue!!!
Element Removed : movies
1.Insert
2.Remove
3.Show
Choice:
3
Show contents of Queue:
books
1.Insert
2.Remove
3.Show
Choice: 5
Doubly Linked List
import java.util.*;
class dnode{
int data;
dnode left,right;
}
class doublelinkedlistDemo{
public static void main(String[] args){
dnode first=null, temp, dummy;
dummy = new dnode();
System.out.println("Creating Doubly Linked List!!!");
int choice;
int data;
Scanner sc = new Scanner(System.in);
while(true){
System.out.println("\n1.Insert\n2.Show\n3.Back Track\n4.Remove First Node\n5.Insert Before Firs node");
choice = sc.nextInt();
switch(choice){
case 1: System.out.println("Enter Integer Data:");
data = sc.nextInt();
temp = new dnode();
temp.data = data;
temp.left = temp.right = null;
if(first == null){
first = temp;
dummy = temp;
}else{
dummy.right = temp;
temp.left = dummy;
dummy = temp;
}
break;
case 2: System.out.println("Show contents of List: \n");
for(temp=first;temp.right!=null;temp=temp.right){
System.out.print(temp.data+" ");
}System.out.print(temp.data+" ");
break;
case 3: System.out.println("Back Tracking: \n");
for(temp=dummy;temp.left!=null;temp=temp.left){
System.out.print(temp.data+" ");
}System.out.print(temp.data+" ");
break;
case 4: System.out.println("Removing First Node of List");
temp = first.right;
first = temp;
first.left = null;
break;
case 5: System.out.println("Insert Before First Node");
data = sc.nextInt();
temp = new dnode();
temp.data = data;
temp.left = temp.right = null;
temp.right = first;
first.left = temp;
first = temp;
break;
default:System.exit(0);
break;
}
}
}
}
Output
Creating Doubly Linked List!!!
1.Insert
2.Show
3.Back Track
4.Remove First Node
5.Insert Before Firs node
1
Enter Integer Data:
33
1.Insert
2.Show
3.Back Track
4.Remove First Node
5.Insert Before Firs node
1
Enter Integer Data:
44
1.Insert
2.Show
3.Back Track
4.Remove First Node
5.Insert Before Firs node
1
Enter Integer Data:
5
1.Insert
2.Show
3.Back Track
4.Remove First Node
5.Insert Before Firs node
2
Show contents of List:
33 44 5
1.Insert
2.Show
3.Back Track
4.Remove First Node
5.Insert Before Firs node
3
Back Tracking:
5 44 33
1.Insert
2.Show
3.Back Track
4.Remove First Node
5.Insert Before Firs node
4
Removing First Node of List
1.Insert
2.Show
3.Back Track
4.Remove First Node
5.Insert Before Firs node
2
Show contents of List:
44 5
1.Insert
2.Show
3.Back Track
4.Remove First Node
5.Insert Before Firs node
Graph BSF Shortest Cycle
import java.util.*;
class AdjacencyGraph{
int matrix[][] = new int[10][10];
public void createEdge(int s, int e, int w){
matrix[s][e] = w;
}
public void showGraph(){
System.out.println("Size of Graph: "+matrix.length) ;
for(int i=0;i<=5;i++){
for(int j=0;j<=5;j++){
System.out.print(matrix[i][j]+" ");
}
System.out.println();
}
}
public void BSF(int start){
int queue[] = new int[10];
boolean visited[] = new boolean[10];
visited[start] = true;
int rear = -1,front=0,i;
queue[++rear] = start;
for(front=0;front <=rear;front++){
for(i=0;i<matrix.length;i++){
if(matrix[queue[front]][i]!=0){
if(visited[i]!=true){
queue[++rear] = i;
visited[i] = true;
}else if(visited[i]== true){
for(int j=0;j<queue.length;j++){
if(queue[j]== i)
System.out.println("Cycle Found!!!");
}
}
}
}
}
for(i=0;i<=rear;i++){
System.out.println(" "+queue[i]);
}
}
public void dijkstra(){
int v = matrix.length;
boolean visited[] = new boolean[v];
int distance[] = new int[v];
distance[0] = 0;
for(int i=1;i<v;i++){
distance[i] = Integer.MAX_VALUE;
}
for(int i=0;i<v-1;i++){
int minVertex = minVertex(distance,visited);
System.out.println("Min Vertext: "+minVertex);
visited[minVertex] = true;
//explore neighbors
for(int j=0;j<v;j++){
if(matrix[minVertex][j]!=0 && !visited[j] && (distance[minVertex]!=Integer.MAX_VALUE)){
int newDist = distance[minVertex]+matrix[minVertex][j];
if(newDist < distance[j]){
distance[j] = newDist;
}
}
}
}
for(int i=0;i<v-1;i++){
System.out.println(i+" "+distance[i]);
}
}
public int minVertex(int[] distance,boolean[] visited){
int minVertex = -1;
for(int i=0;i<distance.length;i++){
if(!visited[i] &&(minVertex == -1 || distance[i] < distance[minVertex])){
minVertex = i;
}
}
return minVertex;
}
public void showAdjacent(int vertex){
for(int i=0;i<5;i++){
if(matrix[vertex][i]!=0)
System.out.println("Adjacents: "+i);
}
}
public void showInDegree(int vertex){
int count = 0;
for(int i=1;i<matrix.length;i++){
if(matrix[i][vertex]!=0){
++count;
}
}
System.out.println("In Degree of "+vertex+" is "+count);
}
}
class AdjacencyGraphDemo{
public static void main(String[] args){
AdjacencyGraph gg = new AdjacencyGraph();
gg.createEdge(0,1,3);
gg.createEdge(0,2,4);
gg.createEdge(0,3,5);
gg.createEdge(3,4,4);
gg.BSF(0);
AdjacencyGraph g = new AdjacencyGraph();
g.createEdge(0,1,4);
g.createEdge(1,0,4);
g.createEdge(0,2,8);
g.createEdge(2,0,8);
g.createEdge(1,3,5);
g.createEdge(3,1,5);
g.createEdge(1,2,2);
g.createEdge(2,1,2);
g.createEdge(2,4,9);
g.createEdge(4,2,9);
g.createEdge(2,3,5);
g.createEdge(3,2,5);
g.createEdge(4,3,4);
g.createEdge(3,4,4);
//System.out.println("Shortest path");
g.showGraph();
g.dijkstra();
g.showAdjacent(3);
//g.detectCycle(0);
System.out.println("BSF Traversal");
g.BSF(0);
AdjacencyGraph dg = new AdjacencyGraph();
dg.createEdge(1,2,5);
dg.createEdge(3,2,4);
dg.createEdge(3,4,3);
dg.createEdge(4,1,2);
dg.createEdge(5,2,2);
dg.createEdge(5,1,2);
dg.createEdge(4,1,2);
dg.showGraph();
dg.showInDegree(2);
AdjacencyGraph d1 = new AdjacencyGraph();
d1.createEdge(1,2,3);
d1.createEdge(1,3,3);
d1.createEdge(1,4,3);
d1.createEdge(4,5,3);
d1.createEdge(2,6,3);
d1.createEdge(3,6,3);
d1.BSF(1);
}
}
Graph Implementation
Graph is a collection of nodes and edges between the nodes. In the program given below, class nodes is created to store name of nodes and class edges is created to store information about the edges. Class nodes simply stores name of nodes in the array of characters with the help of setNodes methods.
Class edges has src and dest variables to store name of nodes and wt variable to store weight of the edge. Method setEdges takes three parameters: source node, destination node, and weight of the edge.
Method showEdge displays information of the edges.
class nodes{
char[] nodes;
public nodes(){
nodes = new char[10];
}
public void setNodes(char[] nodes){
this.nodes = nodes;
}
public void showNodes(){
for(int i=0;i<nodes.length;i++){
System.out.println(nodes[i]);
}
}
}
class edges{
char src,dest;
int wt;
public edges(){}
public void setEdges(char s,char d,int w){
src = s;
dest = d;
wt = w;
}
public void showEdge(){
System.out.println("Edge: "+src+"---"+wt+"---"+dest);
}
}
class graph_2{
public static void main(String[] arr){
char n[] = {'a','b','c','d','e','f'};
nodes g_n = new nodes();
g_n.setNodes(n);
g_n.showNodes();
edges [] ee = new edges[7];
int i;
for(i=0;i<7;i++){
ee[i] = new edges();
}
ee[0].setEdges(n[0],n[1],9);
ee[1].setEdges(n[0],n[2],3);
ee[2].setEdges(n[2],n[3],7);
ee[3].setEdges(n[2],n[4],8);
ee[4].setEdges(n[0],n[5],5);
ee[5].setEdges(n[4],n[5],6);
ee[6].setEdges(n[2],n[5],5);
for(i=0;i<7;i++){
ee[i].showEdge();
}
}
}
Hashing Implementation
Hashing is a technique of storing data in a list or table such that stored data can be found in single comparison or in very few comparisons. Several methods are defined to store data in a list: division by prime number, folding individual digits of the given data, etc.
It is very possible that two or more data hash to same position, that is, hash method produce same hash values for different elements, this situation is known as Hash Collision.
Hash collision can be reduced by considering big prime number to division given data; probing methods can be used to address hash collisions.
Following program uses division by prime number to hash given elements, and quadratic probing to resolve collision.
List of numbers are stored in array named keys, those keys are stored or hash to list name table of size 100. Prime number 97 is used to divide given elements.
import java.util.*;
class hashing_Demo
{
public static void main(String[] aa){
int keys [] = {111,14,222,333,423,4556,6777,8889,3232,4345,46787};
int table[] = new int[100];
int i,prime=97,hashvalue=0;
for(i=0;i<keys.length;i++){
hashvalue = keys[i] % prime;
if(table[hashvalue]==0)
table[hashvalue] = keys[i];
else{
for(int j=1;j<100;j=j*j){
if(table[hashvalue+j]==0){
table[hashvalue+j] = keys[i];
break;
}
}
}
}
for(i=0;i<table.length;i++){
System.out.print(" "+table[i]);
}
Scanner sc = new Scanner(System.in);
System.out.println("Enter value to search: ");
int search = sc.nextInt();
hashvalue = search % prime;
if(table[hashvalue] == search)
System.out.println("Found at"+hashvalue);
else{
for(int j=1;j<100;j=j*j){
if(table[hashvalue+j]==search){
System.out.println("Found at"+(hashvalue+j));
break;
}
}
}
}
}
Copy Linked List to array
A simple linked list is creating in the following program. Node class with data field and address field is defined, constructor is defined to set value for data field (second constructor), show method returns content of a node.
In the driver class (class with main method): while loop is used to create a linked list, numbers from 100 to 109 is stored in the list.
A third loop (for loop) is created to loop through the list, as the fourth position is reached loop is stopped. temp1 iterates through the list and stops at the fourth node (i != 3); A new node temp2 is created; in next field of temp2 reference of 5th node (temp1.next) is stored, then in next field of 4th node (temp1.next), temp2 is stored. A node is inserted in the list.
The list traversed in the fifth loop (for loop), and data of list is stored in the array arr.
class node{
int data;
node next;
public node(){
next = null;
}
public node(int d){
data = d;
next = null;
}
public int show(){
//System.out.println(" "+data);
return data;
}
}
class linkedlist_demo{
public static void main(String[] ar){
node head = null, temp1,temp2=null;
int i=100;
int aar[] = new int [20],j=0;
//creating linked list wiht 10 elements;
while(i<110){
temp1 = new node(i);
if(head == null){
head = temp1;
temp2 = temp1;
//head.show();
}else{
temp2.next = temp1;
temp2 = temp1;
//temp2.show();
}
++i;
}
//display list
System.out.println("\nBefore inserting new node:--->");
for(temp1 = head;temp1!=null;temp1=temp1.next){
System.out.print(" "+ temp1.show());
}
//inserting new node after given position,
//here new node will be inserted after 4th node
i=0;
for(temp1 = head;i!=3;temp1=temp1.next){
i++;
}
temp2 = new node(9999);
temp2.next = temp1.next;
temp1.next = temp2;
System.out.println("\nAfter inserting new node:--->");
for(temp1 = head;temp1!=null;temp1=temp1.next){
System.out.print(" "+ temp1.show());
}
//coping contents of linked list to array
j=0;
for(temp1 = head;temp1!=null;temp1=temp1.next){
aar[j++] = temp1.show();
}
//Displaying content of array
System.out.println("\nPrinting content of array--> ");
for(i=0;i<j;i++)
System.out.print(" "+aar[i]);
}
}
Output:
Before inserting new node:--->
100 101 102 103 104 105 106 107 108 109
After inserting new node:--->
100 101 102 103 9999 104 105 106 107 108 109
Printing content of array-->
100 101 102 103 9999 104 105 106 107 108 109
thank so much sir for helping note plz sir gmail note send me sir