MANIKANTA UYYALA

FINAL
PROJECT
REPORT
SUBMITTED TO THE
VIT-AP UNIVERSITY FOR FULLFILLMENT
DEGREEOF

BTECH
IN
COMPUTER SCIENCE & ENGINEERING

GUIDED BY

Dr. Anil Vitthalrao

Turukmane
(Professor,SCOPE)

COURSE:
DATA
STRUCTURE
AND
ALGORITM

COURSE CODE: CSE2002

SUBMITTED BY

U.MANIKANTA 21BCE9726

SCHOOL OF COMPUTER SCIENCE & ENGINEERING, VIT-AP

UNIVERSITYDECEMBER 2022

21BCE97
 MANIKANTA UYYALA

EXPERIMENT-1

Write a Program to find the factorial of a given number using recursion andanalyze the time
complexity.
CODE:

import java.util.*;
public class Dsa_1 {
public static void main(String[]args) { long start=
System.nanoTime(); Scanner sc= new
Scanner(System.in); System.out.print("Enter a number:
");int n= sc.nextInt();
long req = fact(n);
long end=System.nanoTime(); System.out.println("The Factorial of "+ n +" is
"+req);
System.out.println("The time complexity is "
+ (end-start));
}
public static long fact(int n) {
if(n==0) {
return 1;
}
else{
return n*fact(n-1);
}
}
}

OUTPUT:

21BCE97
 MANIKANTA

Write a Program to find the transpose of a given matrix and display its timecomplexity.
Sol) CODE:

import java.util.*;
public class prog1{
public static void main(String[]args) {
long start= System.nanoTime();
int a,b;
Scanner sc=new Scanner(System.in); System.out.println("Enter No of rows:");a=sc.nextInt();
System.out.println("Enter No of columns:");b=sc.nextInt();
int[][]A= new int[a][b];for(int i=0;i<a;i+
+) {
for(int j=0;j<b;j++) { System.out.print("Enter the Element A["
+(i)+"]"+"[" +(j)+"]:");
A[i][j]=sc.nextInt();
}
}
sc.close();
System.out.println("The transpose is :");
for(int i=0;i<b;i++) {
for(int j=0;j<a;j++) { System.out.println(A[j][i]+" ");
}
System.out.println();
}
long end= System.nanoTime(); System.out.println("The time
complexity is : "+
(end-start));
}
}

OUTPUT:

21BCE97
 MANIKANTA

Challenging:
1) Write a Program to illustrate the difference between recursion anditeration
by giving its time complexities.
Sol)
RECURSION:
CODE:

import java.util.*;
public class prog3 {
public static void main(String[]args) { long start=
System.nanoTime(); Scanner sc= new
Scanner(System.in); System.out.print("Enter a number:
");int n= sc.nextInt();
long req = fact(n);
long end=System.nanoTime(); System.out.println("The Factorial of
"+ n +"
is "+req);
System.out.println("The time complexity is "
+ (end-
start));
} public static long fact(int n) {
if(n==0) {
return 1;
}

21BCE97
 MANIKANTA

else{
return n*fact(n-1);
}
}
}
OUTPUT:

ITERATION:
CODE:

import java.util.*;
public class prog3
{
public static void main(String args[]) {long start=
System.nanoTime(); Scanner sc= new Scanner(System.in);
int i,fact=1;
int number=sc.nextInt(); for(i=1;i<=number;i++) { fact=
fact*i;
}
System.out.println("Factorial of the given numberis:"+fact);
long end= System.nanoTime();
System.out.println("The time complexity is : "+ (end-start));
}
}
OUTPUT:
 MANIKANTA

EXPIREMENT-2

1. Write a Program to implement single linked list and its operations .

CODE:

import java.io.*;

// Java program to implement

// a Singly Linked List public

class LinkedList { Node

head;

// head of list

// Linked list Node.

// This inner class is made static

// so that main() can access it

static class Node { int data; Node

next;

// Constructor

Node(int d)

data = d; next

= null;

}
 MANIKANTA

// Method to insert a new node public static

LinkedList insert(LinkedList list, int data)

// Create a new node with given dataNode

new_node = new Node(data);

// If the Linked List is empty,

// then make the new node as headif

(list.head == null) { list.head

= new_node;

} else

// Else traverse till the last node

// and insert the new_node there

Node last = list.head; while

(last.next != null) { last = last.next;

// Insert the new_node at last node last.next

= new_node;

// Return the list by head return

list;

}
 MANIKANTA

// Method to print the LinkedList.

publicstatic void printList(LinkedList list)

Node currNode = list.head;

System.out.print("LinkedList: "); //

Traverse through the LinkedListwhile

(currNode != null) {

// Print the data at current node

System.out.print(currNode.data + " ");

// Go to next node currNode =currNode.next;

// Driver code public static void

main(String[] args)

/* Start with the empty list. */

LinkedList list = new

LinkedList();

//

// ******INSERTION******

//

// Insert the values list

= insert(list, 1); list =

 MANIKANTA

insert(list, 2); list =

insert(list, 3); list =

insert(list, 4); list =

insert(list, 5); list =

insert(list, 6); list =

insert(list, 7); list =

insert(list, 8);

// Print the LinkedList printList(list);

OUTPUT:

LinkedList: 1 2 3 4 5 6 7 8

2. Write a Program to implement doubly linked list and its operation

CODE:
public class DLL {
 MANIKANTA

Node head;
class Node { int
data;
Node prev;

Node next;

Node(int d) { data = d; }

public void push(int new_data)

Node new_Node = new Node(new_data);

new_Node.next = head; new_Node.prev
= null;

if (head != null)

head.prev = new_Node; head

= new_Node;

public void InsertBefore(Node next_node, int new_data)

if(next_node == null)

System.out.println("The given next node can not be NULL"); return;

Node new_node = new Node(new_data);

new_node.prev = next_node.prev; next_node.prev =
new_node; new_node.next
 MANIKANTA

= next_node; if(new_node.prev !=
null) new_node.prev.next =
new_node;
else

head = new_node;

public void InsertAfter(Node prev_Node, int new_data)

if (prev_Node == null) {

System.out.println("The given previous node cannot be NULL ");return;

Node new_node = new

Node(new_data); new_node.next =
prev_Node.next; prev_Node.next =
new_node; new_node.prev =
prev_Node;
if (new_node.next != null)
new_node.next.prev = new_node;

void append(int new_data)

Node new_node = new

Node(new_data);Node last = head;
new_node.next = null; if (head == null) {
new_node.prev = null; head

= new_node;
return;

}
 MANIKANTA

while (last.next != null) last

= last.next;

last.next = new_node; new_node.prev

= last;

public void printlist(Node node)

Node last = null;

System.out.println("Traversal in forward Direction"); while

(node != null) { System.out.print(node.data + " "); last =
node; node = node.next;

System.out.println();

System.out.println("Traversal in reverse direction");while (last !=

null) {
System.out.print(last.data + " "); last

= last.prev;

public static void main(String[] args)

DLL dll = new DLL(); dll.append(6);

dll.push(7); dll.push(1); dll.append(4);
dll.InsertAfter(dll.head.next, 8);
System.out.println("Created DLL is: ");
dll.printlist(dll.head);

}
 MANIKANTA

OUTPUT:
Created DLL is:

Traversal in forward Direction1 7

864
Traversal in reverse direction4 6
871

3. Write a Program to implement stack operations using arrays.

CODE:
import java.io.*;
import java.util.*;
class stack<T> {
ArrayList<T> A; int
top = -1; int size;
stack(int size)

{
 MANIKANTA

this.size = size; this.A = new

ArrayList<T>(size);

void push(T X)

if (top + 1 == size) {
System.out.println("Stack Overflow");

else { top = top

+ 1; if (A.size() >
top) A.set(top,
X); else A.add(X);
}

T top()

if (top == -1) {

System.out.println("Stack Underflow"); returnnull;

else
return
A.get(top
);
}

void pop()

if (top == -1) {
 MANIKANTA

System.out.println("Stack Underflow");

else top--;

boolean empty() { return top == -1; } public

String toString()

String Ans = "";

for (int i = 0; i < top; i++) {

Ans += String.valueOf(A.get(i)) + "->";

Ans += String.valueOf(A.get(top)); returnAns;

}

public class GFG { public static void

main(String[] args)

stack<Integer> s1 = new stack<>(3);

s1.push(10); s1.push(20); s1.push(30);
System.out.println("s1 after pushing 10, 20 and 30 :\n" + s1);s1.pop();
System.out.println("s1 after pop :\n" + s1);
stack<String> s2 = new stack<>(3);
s2.push("hello"); s2.push("world");
s2.push("java");
 MANIKANTA

System.out.println("\ns2 after pushing 3 elements :\n" + s2);

System.out.println("s2 after pushing 4th element :"); s2.push("GFG");
stack<Float> s3 = new stack<>(2); s3.push(100.0f); s3.push(200.0f);
System.out.println("\ns3 after pushing 2 elements :\n" + s3);
System.out.println("top element of s3:\n"+ s3.top());
}

}
OUTPUT:
s1 after pushing 10, 20 and 30 :

10->20->30

s1 after pop : 10->20 s2 after

pushing 3 elements :
hello->world->java s2 after
pushing 4th element :
Stack Overflow s3 after
pushing 2 elements :
100.0->200.0 top

element of s3:
200.0
 MANIKANTA

4. Write a Program to implement queue operations using linked list.

CODE:
class QNode {

int key;

QNode next; publicQNode(int

key) {

this.key = key; this.next

= null;

class Queue {
QNode front, rear;
public Queue()
{

this.front = this.rear = null;

}
 MANIKANTA

void enqueue(int key)

QNode temp = new

QNode(key);if (this.rear == null) {
this.front
= this.rear = temp; return;

this.rear.next = temp; this.rear

= temp;

void dequeue()

if (this.front == null)
return; QNode temp =
this.front;

this.front = this.front.next;

if (this.front == null) this.rear

= null;

public class Test { public static void

main(String[] args)

Queue q = new Queue();

q.enqueue(10);
q.enqueue(20);
q.dequeue();
q.dequeue();
 MANIKANTA

q.enqueue(30);
q.enqueue(40);
q.enqueue(50);
q.dequeue();
System.out.println("Queue Front : " + q.front.key);
System.out.println("Queue Rear : " + q.rear.key);
}

}
OUTPUT:
Queue Front : 40
Queue Rear : 50
 MANIKANTA

EXPIREMENT-3.1

Write a program to implement Representation of Binary tree with linked list

Code:

import java.util.*;
class ListNode
{
int data;
ListNode next;
ListNode(int d)
{
data = d;
next =
null;
}
}
class BinaryTreeNode
{
int data;
BinaryTreeNode left, right = null;
BinaryTreeNode(int data)
{
this.data = data;
left = right =
null;
}
}
class BinaryTree
{
ListNode head;
BinaryTreeNode root;
void push(int
new_data)
{
ListNode new_node = new ListNode(new_data);
new_node.next = head;
head = new_node;
}
BinaryTreeNode convertList2Binary(BinaryTreeNode node)
{
 MANIKANTA

Queue<BinaryTreeNode> q =
new LinkedList<BinaryTreeNode>();
if (head == null)
{
node =
null;return
null;
}
node = new
BinaryTreeNode(head.data); q.add(node);
head = head.next;
while (head != null)
{
BinaryTreeNode parent = q.peek();
BinaryTreeNode leftChild = null, rightChild =
null; leftChild = new
BinaryTreeNode(head.data); q.add(leftChild);
head = head.next;
if (head != null)
{
rightChild = new
BinaryTreeNode(head.data); q.add(rightChild);
head = head.next;
}
parent.left = leftChild;
parent.right = rightChild;
q.poll(); }
return node;
}
void inorderTraversal(BinaryTreeNode node)
{
if (node != null)
{
inorderTraversal(node.left);
System.out.print(node.data + " ");
inorderTraversal(node.right);
}
}
public static void main(String[] args)
{
BinaryTree tree = new
BinaryTree(); tree.push(36);
tree.push(30); tree.push(25);
 MANIKANTA

tree.push(15);
tree.push(12
);tree.push(10);
BinaryTreeNode node = tree.convertList2Binary(tree.root); System.out.println("Inorder Traversal
of the"+ " constructed Binary Tree is:");
tree.inorderTraversal(node);
}
}
Output:
Inorder Traversal of the constructed Binary Tree is:25
12 30 10 36 15

21BCE97
 MANIKANTA

EXPIREMENT-3.2

Write a program to implement Binary tree traversals- In-order, Pre-order,Post-order using

recursion.

Code:
// Java program for different tree traversals

class Node
{int key;
Node left, right;

public Node(int item)

{
key = item;
left = right = null;
}
}

class BinaryTree {

Node root;

BinaryTree() { root = null; }

void printPostorder(Node node)

{
if (node == null)
return;

21BCE97
 MANIKANTA

// first recur on left subtree

printPostorder(node.left);

// then recur on right subtree

printPostorder(node.right);

// now deal with the node

System.out.print(node.key + "
");
}

/* Given a binary tree, print its nodes in inorder*/void

printInorder(Node node)
{
if (node == null)
return;

printInorder(node.left);

System.out.print(node.key + " ");

printInorder(node.right);
}

/* Given a binary tree, print its nodes in preorder*/void

printPreorder(Node node)
{
if (node == null)
return;

21BCE97
 MANIKANTA

System.out.print(node.key + " ");

printPreorder(node.left);

printPreorder(node.right);
}

void printPostorder() { printPostorder(root); }void

printInorder() { printInorder(root); }
void printPreorder() { printPreorder(root); }

public static void main(String[] args)

{
BinaryTree tree = new BinaryTree();
tree.root = new Node(1); tree.root.left =
new Node(2); tree.root.right = new
Node(3); tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);

System.out.println(
"Preorder traversal of binary tree is ");
tree.printPreorder();

System.out.println(
"\nInorder traversal of binary tree is ");
tree.printInorder();

System.out.println(
"\nPostorder traversal of binary tree is ");
tree.printPostorder();
}
}

21BCE97
 MANIKANTA

Output:
Preorder traversal of binary tree is1 2 4 5 3
Inorder traversal of binary tree is4 2 5 1 3
Postorder traversal of binary tree is4 5 2 3 1

21BCE97
 MANIKANTA

EXPIREMENT-3.3

1. Write a program to implement AVL Tree

Code:

// Java program for insertion in AVL

Tree class Node {
int key, height;
Node left, right;

Node(int d) {
key = d;
height =
1;
}
}

class AVLTree {

Node root;

int height(Node N) {
if (N == null)
return 0;

return N.height;
}

int max(int a, int b) {

return (a > b) ? a : b;
}

Node rightRotate(Node y) {
Node x = y.left; Node
T2 = x.right;

x.right = y;
y.left = T2;

y.height = max(height(y.left), height(y.right)) + 1;

x.height = max(height(x.left), height(x.right)) + 1;

return x;
}

21BCE97
 MANIKANTA

Node leftRotate(Node x) {
Node y =
x.right;
Node T2 =
y.left;

y.left = x;
x.right = T2;

x.height = max(height(x.left), height(x.right)) + 1;

y.height = max(height(y.left), height(y.right)) + 1;

return y;
}

int getBalance(Node N) {
if (N == null)
return 0;

return height(N.left) - height(N.right);

}

Node insert(Node node, int key) {

if (node == null)
return (new Node(key));

if (key < node.key)

node.left = insert(node.left, key);
else if (key > node.key)
node.right = insert(node.right, key);
else
return node;

node.height = 1 + max(height(node.left),
height(node.right));

int balance = getBalance(node);

if (balance > 1 && key < node.left.key)

return rightRotate(node);

if (balance < -1 && key > node.right.key)

return leftRotate(node);

if (balance > 1 && key > node.left.key) {

node.left = leftRotate(node.left);
return rightRotate(node);
}

if (balance < -1 && key < node.right.key) {

21BCE97
 MANIKANTA

node.right = rightRotate(node.right);
return leftRotate(node);
}

return node;
}

void preOrder(Node node) {if

(node != null) {
System.out.print(node.key + " ");
preOrder(node.left);
preOrder(node.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);
}
}

Output:
Preorder traversal of the constructed AVL tree
is 30 20 10 25 40 50

21BCE97
MANIKANTA

21BCE97
 MANIKANTA

EXPIREMENT-4.1

1. Write a program to implement quicksort

Code:
// Java program for quicksort

import

java.io.*;class

QuickSort {

// A utility function to swap two elementsstatic void

swap(int[] arr, int i, int j)
{
int temp =
arr[i];arr[i] =
arr[j]; arr[j] =
temp;
}

/* This function takes last element as pivot, placesthe pivot element

at its correct position in sorted array, and places all smaller (smaller
than pivot) to left of pivot and all greater elements to right
of pivot */
static int partition(int[] arr, int low, int high)
{

// pivot
int pivot = arr[high];

// Index of smaller element and

// indicates the right position
// of pivot found so far
int i = (low - 1);

for (int j = low; j <= high - 1; j++) {

21BCE97
 MANIKANTA UYYALA

// If current element is smaller

// than the
pivotif (arr[j] <
pivot) {

// Increment index of
// smaller
elementi++;
swap(arr, i, j);
}
}
swap(arr, i + 1,
high);return (i + 1);
}

/* The main function that implements QuickSortarr[] --

> Array to be sorted,
low --> Starting
index,high --> Ending
index
*/
static void quickSort(int[] arr, int low, int high)
{
if (low < high) {

// pi is partitioning index, arr[p]

// is now at right place
int pi = partition(arr, low, high);

// Separately sort elements before

// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

// Function to print an array

static void printArray(int[] arr, int size)
{
for (int i = 0; i < size; i++)
System.out.print(arr[i] + " ");

21BCE97
 MANIKANTA

System.out.println();
}

// Driver Code
public static void main(String[] args)
{
int[] arr = { 10, 7, 8, 9, 1, 5 };
int n = arr.length;

quickSort(arr, 0, n - 1);
System.out.println("Sorted array: ");
printArray(arr, n);
}
}

OUTPUT:

21BCE97
 MANIKANTA

EXPERIMENT-4.2

Write a program that takes the details of Students (name, roll number, address, CGPA) and
sort it in a non-decreasing order using Selection sort based onCGPA.

Code:

import java.io.*;

public class CGPA {

public static double cgpacalc(int[] marks, int n)

double cgpa, sum = 0;

double grade[]=new double[n];

for (int i = 0; i < n; i++) {

grade[i] = (marks[i] / 10);

for (int i = 0; i < n; i++) {

sum += grade[i];

cgpa = sum /

n;return cgpa;

public static void print(String[] a,String[] b,double[] c,int n ) {

System.out.println(" Name | Regd.no | cgpa ");for(int

i=0;i<n;i++) {

System.out.printf("%-10s|%-12s|%.2f\n",a[i],b[i],c[i]);

public static void main(String args[]) throws NumberFormatException, IOException {

21BCE97
 MANIKANTA

BufferedReader bi = new BufferedReader(new InputStreamReader(System.in));

System.out.println("Enter no of students details you are entering: ");

int n=Integer.parseInt(bi.readLine());

String names[]=new String[n];

String regd[]=new String[n];

int marks[][]=new int[n][5];

double cgpa[]=new double[n];

for(int i=0;i<n;i++) {

System.out.println("Enter name of student: ");

names[i]=bi.readLine(); System.out.println("Enter

regd no. of student: ");regd[i]=bi.readLine();

System.out.println("Enter marks divided with spaces: ");

String[] input=bi.readLine().split(" ");

for(int j=0;j<5;j++) {

marks[i][j]=Integer.parseInt(input[j]);

for(int i=0;i<n;i++) {

cgpa[i]=cgpacalc(marks[i],5);

System.out.println("before sorting");

print(names,regd,cgpa,n);

//selection sort

int

remaining=n;

for(int i=0;i<n;i++) {

21BCE97
 MANIKANTA

double max=0;

int

max_index=0;

for(int j=0;j<remaining;j++) {

if(cgpa[j]>max) {

max=cgpa[j]

max_index=

j;

Double temp1=cgpa[remaining-1];

cgpa[remaining-1]=max;

cgpa[max_index]=temp1;

String temp2=names[remaining-1];

names[remaining-1]=names[max_index];

names[max_index]=temp2;

String temp3=regd[remaining-1];

regd[remaining-1]=regd[max_index];

regd[max_index]=temp3;

remaining--;

System.out.println("After sorting");

print(names,regd,cgpa,n);

OUTPUT:

21BCE97
MANIKANTA

21BCE97
 MANIKANTA

EXPIREMENT-5.1

LINEAR SEARCH:

CODE:

public class LinearSearchExample{

public static int linearSearch(int[] arr, int
key){for(int i=0;i<arr.length;i++){
if(arr[i] ==
key){return
i;
}
}
return -1;
}
public static void main(String
a[]){int[] a1=
{10,20,30,50,70,90};
int key = 50;
System.out.println(key+" is found at index: "+linearSearch(a1, key));
}

OUTPUT:

21BCE97
 MANIKANTA

BINARY SEARCH:

CODE:
class BinarySearch {
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) /
2;if (arr[mid] == x)
return
mid; if
(arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
}
return -1;
}
public static void main(String args[])
{
BinarySearch ob = new BinarySearch();
int arr[] = { 2, 3, 4, 10, 40 };
int n =
arr.length;int x
= 10;
int result = ob.binarySearch(arr, 0, n - 1, x);if
(result == -1)
System.out.println("Element not present");
else
System.out.println("Element found at index "
+ result);
}
}

21BCE97
 MANIKANTA

OUTPUT:

21BCE97
 MANIKANTA

EXPIREMENT-5.2

Aim: Write a Program implements basic Hashing Techniques.

Code:

import java.util.*;

public class HashTableDemo

/* Driver Code */

public static void main(String args[])

/* Create a HashTable to store String values corresponding to integer keys */

Hashtable<Integer, String> hm = new Hashtable<Integer, String>();

/* Input the values */

hm.put(3, "You are

visiting");hm.put(5,

"Hello");

hm.put(1, "website");

hm.put(2, "Javatpoint");

/* Display the

Hashtable */

System.out.println(

hm);

21BCE97
 MANIKANTA

OUTPUT:

21BCE97
MANIKANTA

21BCE97
 MANIKANTA

EXPIREMENT-6.1

Aim: write a program to implement DFS algorithm

Code:

import java.io.*;
import java.util.*;

class Graph {
private int V; // No. of

vertices private

LinkedList<Integer> adj[];

@SuppressWarnings("unchecked") Graph(int v)
{
V = v;
adj = new
LinkedList[v];for
(int i = 0; i < v; ++i)
adj[i] = new LinkedList();
}

void addEdge(int v, int w)

{
adj[v].add(w); // Add w to v's list.
}

void DFSUtil(int v, boolean visited[])

{
visited[v] = true;
System.out.print(v + " ");

Iterator<Integer> i =
adj[v].listIterator();while
(i.hasNext()) {
int n =
i.next();if
(!visited[
n])
DFSUtil(n, visited);
}
}

void DFS(int v)
{
boolean visited[] = new boolean[V];

DFSUtil(v, visited);
}

public static void main(String args[])

{
Graph g = new Graph(4);

21BCE97
 MANIKANTA

g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);

21BCE97
 MANIKANTA

g.addEdge(3, 3);

System.out.println(
"Following is Depth First Traversal "
+ "(starting from vertex 2)");

g.DFS(2);
}
}

OUTPUT:

21BCE97
 MANIKANTA

EXPIREMENT-6.2

Aim: Java program to print BFS traversal from a given source vertex. BFS(int s) traverses vertices
reachable froms.

Code:

import java.io.*;
import
java.util.*;

// This class represents a directed graph using adjacency list

//
representa
tionclass
Graph
{
private int V; // No. of vertices
private LinkedList<Integer> adj[]; //Adjacency Lists

Graph(int v)
{
V = v;
adj = new
LinkedList[v];for
(int i=0; i<v; ++i)
adj[i] = new LinkedList();
}

void addEdge(int v,int w)

{
adj[v].add(w);
}

void BFS(int s)
{

boolean visited[] = new boolean[V];

LinkedList<Integer> queue = new

LinkedList<Integer>();visited[s]=true;
queue.add(s);

while (queue.size() != 0)
{

s = queue.poll();
System.out.print(s+" ");

Iterator<Integer> i =
adj[s].listIterator();while

21BCE97
 MANIKANTA

(i.hasNext())
{
int n =
i.next();
if (!
visite
d[n])

21BCE97
 MANIKANTA

{
visited[n]
= true;
queue.ad
d(n);
}
}
}
}

public static void main(String args[])

{
Graph g = new Graph(4);

g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);

System.out.println("Following is Breadth First Traversal "+

"(starting from vertex 2)");

g.BFS(2);
}
}

21BCE97
 MANIKANTA

OUTPUT:

21BCE97