SELECTION SORT

void sort(int arr[], int size)

{
int temp = 0;
for (int i = 0; i < size-1; i++)
{
temp = i;
for (int j = i+1; j < size; j++)
{
if (arr[temp] > arr[j])
{
temp = j;
}
}
swap(arr[temp], arr[i]);
}
}

BUBBLE SORT
void sort(int arr[], int size)
{

for (int i = 0; i < size-1; i++)

{
for (int j = i+1; j < size; j++)
{
if (arr[i] > arr[j])
{
swap(arr[i], arr[j]);
}
}
}
}
 INSERTION SORT
void sort(int arr[], int size)
{
int i,temp,j;
for (i = 1; i < size; i++)
{
temp = arr[i];
j = i - 1;
while( j >= 0 && arr[j]>temp)
{
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j+1] = temp;
}
}

BUBBLE SORT SINGLY LINKEDLIST

void Bubblesort()
{
temp = head;
while(temp->next!=NULL)
{
tail = temp->next;
while (tail!=NULL)
{
if (temp->data > tail->data)
{
swap(temp->data, tail->data);
}
tail = tail->next;
}
temp = temp->next;
}
}
 SELECTION SORT IN SINGLY LINKEDLIST
void Selectionsort()
{
temp = head;
Node* x;
while (temp->next!=NULL)
{
x = temp;
tail = temp->next;
while (tail!=NULL)
{
if (tail->data < x->data)
{
x = tail;
}
tail = tail->next;
}
swap(x->data, temp->data);
temp = temp->next;
}
}
 BACK TRACKING MID 1 QUESTION 2
#include<iostream>
using namespace std;
int s(int i, int j, char arr[][5])
{
static int count = 0;
if (i == 5)
{
exit;
}
else if (j == 5)
{
s(i + 1, 0, arr);
}
else
{
if (arr[i][j] == 'f')
{
if (arr[i][j + 1] == 'o' )
{
if (arr[i][j + 2] == 'o' )
{
if (arr[i][j + 3] == 't' )
{
count=count+1;
cout << "\n(" << i << "," << j << ") to " << "(" <<
i << "," << j + 3 << ") position";
}
}
}
}
if (arr[i][j] == 'f')
{
if (arr[i + 1][j] == 'o')
{
if (arr[i + 2][j] == 'o')
{
if ( arr[i + 3][j] == 't')
{
count = count + 1;
cout << "\n(" << i << "," << j << ") to " << "(" <<
i+3 << "," << j << ") position";
}
}
}
}
else if (arr[i][j] == 't')
 {
if (arr[i][j - 1] == 'o' )
{
if (arr[i][j -2] == 'o' )
{
if (arr[i][j - 3] == 'f' )
{
count++;
cout << "\n(" << i << "," << j << ") to " << "(" <<
i << "," << j - 3 << ") position";
}
}
}
}
else if (arr[i][j] == 't')
{
if ( arr[i - 1][j] == 'o')
{
if ( arr[i - 2][j] == 'o')
{
if ( arr[i - 3][j] == 'f')
{
count++;
cout << "\n(" << i << "," << j << ") to " << "(" <<
i-3 << "," << j << ") position";
}
}
}
}
s(i, j + 1, arr);
return count;
}

}
int main()
{
char a[5][5] = { 'o','f','o','o','t','v','o','q','u','o','e','o','i','h','o','r','t','g','h','f' };
int r=s(0, 0, a);
cout << "\n" << r << " ";
}
 SINGLY LINKEDLIST SIMPLE FUNCTIONS
#include<iostream>
using namespace std;
class Node
{
public:
int data;
int key;
Node* next;
Node()
{
data = 0;
key = 0;
next = NULL;
}
Node(int data)
{
this->data = data;
key = 0;
next = NULL;
}
Node(int data, int key)
{
this->data = data;
this->key = key;
next = NULL;
}
};
class ll
{
public:
Node* head;
Node* temp;
Node* tail;
ll()
{
head = NULL;
temp = NULL;
tail = NULL;
}
void append(int data)
{
Node* newn = new Node(data);
if (head == NULL)
{
head = newn;
temp = newn;
 tail = newn;
}
else
{
temp->next = newn;
temp = temp->next;
}
}
void prepend(int data)
{
Node* newn = new Node(data);
if (head == NULL)
{
head = newn;
temp = newn;
tail = newn;
}
else
{
newn->next = head;
head = newn;
}
}
void insert(int data, int key)
{
int count = 0;
Node* newn = new Node(data, key);
if (key < 0)
{
cout << "\nKey is not correct\n";
}
else if (head == NULL && key > 0)
{
cout << "\n Can be inserted at head but not on your designated position";
}
else if (head == NULL)
{
head = newn;
temp = newn;
}
else if (key == 0)
{
newn->next=head;
head = newn;
}
else
{
 temp = head;
while (count < key)
{
tail = temp;
temp = temp->next;
count++;
}
tail->next = newn;
newn->next = temp;
}
}
void Delete(int key)
{
int count = 0;

if (key < 0)
{
cout << "\nKey is not correct\n";
}
else if (head == NULL && key > 0)
{
cout << "\nlist is empty\n";
}
else if (head == NULL)
{
cout << "\nhead is empty\n";
}
else if (key == 0)
{
temp = head->next;
delete head;
head = temp;

}
else
{
temp = head;
while (count < key)
{
tail = temp;
temp = temp->next;
count++;
}
tail->next = temp->next;
delete temp;
}
}
 void print()
{
temp = head;
while (temp != NULL)
{
cout << temp->data << "->";
temp = temp->next;
}
cout << "NULL\n";
}
};
int main()
{
ll ob;
ob.append(2);
ob.append(1);
ob.append(7);
cout << "Append: ";
ob.print();
ob.prepend(8);
ob.prepend(9);
cout << "prepend: ";
ob.print();
ob.insert(5, 2);
ob.insert(8, 4);
cout << "Insert: ";
ob.print();
ob.Delete(2);
cout << "Delete: ";
ob.print();

}
 QUICK SORT
#include<iostream>
using namespace std;
int partition(int arr[], int low, int high);
void sort(int arr[], int low, int high)
{
if (high <= low)
{
return;
}
else {
int z = partition(arr, low, high);
sort(arr, low, z - 1);
sort(arr, z + 1,high);
}
}
int partition(int arr[], int low,int high)
{
int x = low;
int j = high + 1;
int a = arr[x];
while (true)
{
while (arr[++x] < a)
{
if (x == high)
{
break;
}
}
while (a < arr[--j])
{
if (j == low)
{
break;
}
}
if (x >= j)
 {
break;
}
swap(arr[x], arr[j]);
}
swap(arr[low], arr[j]);
return j;
}
void printing(int arr[], int low, int high)
{
for (int i = 0; i <= high; i++)
{
cout << arr[i] << " ";
}
}
int main()
{
int arr[] = { 35,33,42,10,14,19,27,44,26,31};
cout << "UNSORTED ARRAY: ";
int low = 0;
int high = sizeof(arr) / sizeof(int) - 1;
for (int i = 0; i <= high; i++)
{
cout << arr[i] << " ";
}
sort(arr, low, high);
cout << "\nSORTED ARRAY: ";
for (int i = 0; i <= high; i++)
{
cout << arr[i] << " ";
}

}
 MERGE SORT
#include<iostream>
using namespace std;
void merge(int arr[], int low, int mid, int high) {
int n1 = mid - low + 1;
int n2 = high - mid;

int leftArray['n1'];
int rightArray['n2'];

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

leftArray[i] = arr[low + i];
}

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

rightArray[i] = arr[mid + 1 + i];
}

int i = 0, j = 0, k = low;

while (i < n1 && j < n2) {

if (leftArray[i] <= rightArray[j]) {
arr[k] = leftArray[i];
i++;
}
else {
arr[k] = rightArray[j];
j++;
}
k++;
}

while (i < n1) {

arr[k] = leftArray[i];
i++;
k++;
}
 while (j < n2) {
arr[k] = rightArray[j];
j++;
k++;
}
}
void mergesort(int arr[], int low, int high)
{
if (low < high)
{
int mid = low + (high - low) / 2;
mergesort(arr, low, mid);
mergesort(arr, mid + 1, high);
merge(arr, low, mid, high);
}

}
int main()
{
int arr[] = { 3, 1, 6, 8, 4, 5, 7, 2 };
int high = sizeof(arr) / sizeof(int) -1;
int low = 0;
cout << "Unsorted array: ";
for (int i = 0; i < high; i++)
{
cout << arr[i] << " ";
}
mergesort(arr, low, high);
cout << "\nsorted array: ";
for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
{
cout << arr[i] << " ";
}
}
 RADIX SORT
#include<iostream>
using namespace std;
void radixsort(int arr[], int n,int max,int temp[])
{
int Newarr['n'] = { 0 };
for (int i = 0; i < n; i++)
{
Newarr[i] = arr[i];
}
while (max > 0)
{
for (int j = 0; j < n; j++)
{
temp[j] = Newarr[j] % 10;
Newarr[j] = Newarr[j] / 10;
}
for (int i = 0; i < n - 1; i++)
{
for (int j = i; j < n; j++)
{
if (temp[i] > temp[j])
{
swap(temp[i], temp[j]);
swap(Newarr[i], Newarr[j]);
swap(arr[i], arr[j]);
}
}
}

max = max / 10;

}
}
int main()
{
int arr[] = { 149,500,220,132,335,459,663 };
int n = sizeof(arr) / sizeof(int);
int temp['n'];
 int max = arr[0];
cout << "\nUNSORTED ARR: ";
for (int i = 0; i < n; i++)
{
if (max < arr[i])
{
max = arr[i];
}
cout << arr[i] << " ";
}
radixsort(arr, n,max,temp);
cout << "\nsorted arr : ";
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}

}
 BINARY SEARCH
#include<iostream>
using namespace std;
void binarysearch(int arr[], int low, int high)
{

if (low <= high)

{
int mid = low+ (high-low) / 2;
if (arr[mid] == 58)
{
cout << "\n58 FOUND AT " << mid << " position\n";
return;
}
else if (arr[mid] < 58)
{
binarysearch(arr, mid+1,high);
}
else if (arr[mid] > 58)
{
binarysearch(arr, low, mid-1);
}
}
else
{
cout << "\nYour Roll Number ending with 58 not found.";
arr[high+1]=58;
cout <<"\n58 is inserted into array at last position";
}
}
int main()
{
int arr[] = { 1,6,8,10,13,18,58,92,100 };
int i = 0;
int low = 0;
bool rollfound=false;
int high = sizeof(arr) / sizeof(int)-1;
binarysearch(arr, low, high);
}

INTERPOLATION SEARCH
#include<iostream>
using namespace std;
void interpolationsearch(int arr[], int low, int high, int target)
{
int mid = low + ((high - low) / (arr[high] - arr[low])) * (target -
arr[low]);
if (arr[mid] == target)
{
cout << "\n" << target << " FOUND AT " << mid << "
position\n";
return;
}
else if (arr[mid] < target)
{
interpolationsearch(arr, mid + 1, high, target);
}
else if (arr[mid] > target)
{
interpolationsearch(arr, low, mid - 1, target);
}
else
{
cout << target << " NOT FOUND.";
}
}
int main()
{
int arr[] = { 1,6,8,10,13,18,58,92,100};
int i = 0;
int low = 0;
int target = 0;
int high = sizeof(arr) / sizeof(int)-1;
cout << "enter the target: ";
cin >> target;
interpolationsearch(arr, low, high,target);
}

AVL TREE INSERTION

#include<iostream>
using namespace std;
class Node
{
public:
int key;
int height;
Node* right;
Node* left;
Node(int key)
{
this->key = key;
this->height = 1;
left = NULL;
right = NULL;
}
};

class AVL
{
public:

int getheight(Node* node)

{
if (node == NULL)
{
return 0;
}
return node->height;
}

int getbalancefactor(Node* node)

{
if (node == NULL)
{
return 0;
}
return getheight(node->left) - getheight(node->right);
}

Node* leftrotate(Node* node)

 {
Node* newn = node->right;
Node* new2 = newn->left;

newn->left = node;
node->right = new2;

node->height = max(getheight(node->left), getheight(node-

>right)) + 1;
newn->height = max(getheight(newn->left), getheight(newn-
>right)) + 1;
return newn;
}

Node* rightrotate(Node* node)

{
Node* newn = node->left;
Node* new2 = newn->right;

newn->right = node;
node->left = new2;

node->height = max(getheight(node->left), getheight(node-

>right)) + 1;
newn->height = max(getheight(newn->left), getheight(newn-
>right)) + 1;
return newn;
}

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(getheight(node->left), getheight(node-

>right));

int balance = getbalancefactor(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)

{
node->right = rightrotate(node->right);
return leftrotate(node);
}

return node;
}
 void preorder(Node* root)
{
if (root != NULL)
{
cout << root->key << "->";
preorder(root->left);
preorder(root->right);
}
}
};

int main()
{
Node* root = NULL;
AVL avl;
root = avl.insert(root, 1);
root = avl.insert(root, 2);
root = avl.insert(root, 3);
root = avl.insert(root, 4);
root = avl.insert(root, 5);
root = avl.insert(root, 6);
root = avl.insert(root, 7);
cout << "AVL TREE: ";
avl.preorder(root);
}

AVL TREE DELETION

#include<iostream>
using namespace std;
class Node
{
public:
int key;
int height;
Node* right;
Node* left;
Node(int key)
{
this->key = key;
this->height = 1;
left = NULL;
right = NULL;
}
};

class AVL
{
public:

int getheight(Node* node)

{
if (node == NULL)
{
return 0;
}
return node->height;
}

int getbalancefactor(Node* node)

{
if (node == NULL)
{
return 0;
}
return getheight(node->left) - getheight(node->right);
}

Node* leftrotate(Node* node)

 {
Node* newn = node->right;
Node* new2 = newn->left;

newn->left = node;
node->right = new2;

node->height = max(getheight(node->left), getheight(node-

>right)) + 1;
newn->height = max(getheight(newn->left), getheight(newn-
>right)) + 1;
return newn;
}

Node* rightrotate(Node* node)

{
Node* newn = node->left;
Node* new2 = newn->right;

newn->right = node;
node->left = new2;

node->height = max(getheight(node->left), getheight(node-

>right)) + 1;
newn->height = max(getheight(newn->left), getheight(newn-
>right)) + 1;
return newn;
}

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(getheight(node->left), getheight(node-

>right));

int balance = getbalancefactor(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)

{
node->right = rightrotate(node->right);
return leftrotate(node);
}

return node;
}
Node* minValueNode(Node* node)
{
Node* current = node;
while (current->left != NULL)
current = current->left;
return current;
}

Node* deleteNode(Node* root, int key)

{
if (root == NULL)
return root;

if (key < root->key)

root->left = deleteNode(root->left, key);

else if (key > root->key)

root->right = deleteNode(root->right, key);

else
{
if ((root->left == NULL) || (root->right == NULL))
{
Node* temp;
if (root->left != NULL)
{
temp = root->left;
}
else
{
temp = root->right;
}
if (temp == NULL)
{
temp = root;
root = NULL;
}
else
*root = *temp;
 delete temp;
}
else
{
Node* temp = minValueNode(root->right);
root->key = temp->key;
root->right = deleteNode(root->right, temp->key);
}
}

if (root == NULL)
return root;

root->height = 1 + max(getheight(root->left), getheight(root-

>right));
int balance = getbalancefactor(root);

if (balance > 1 && getbalancefactor(root->left) >= 0)

return rightrotate(root);

if (balance > 1 && getbalancefactor(root->left) < 0)

{
root->left = leftrotate(root->left);
return rightrotate(root);
}

if (balance < -1 && getbalancefactor(root->right) <= 0)

return leftrotate(root);

if (balance < -1 && getbalancefactor(root->right) > 0)

{
root->right = rightrotate(root->right);
return leftrotate(root);
}

return root;
}
void preorder(Node* root)
 {
if (root != NULL)
{
cout << root->key << "->";
preorder(root->left);
preorder(root->right);
}
}
};

int main()
{
Node* root = NULL;
AVL avl;
root = avl.insert(root, 1);
root = avl.insert(root, 2);
root = avl.insert(root, 3);
root = avl.insert(root, 4);
root = avl.insert(root, 5);
root = avl.insert(root, 6);
root = avl.insert(root, 7);
cout << "AVL TREE: ";
avl.preorder(root);
avl.deleteNode(root, 3);
cout << "\nAVL TREE AFTER DELETING 3: ";
avl.preorder(root);

MAX HEAP
#include <iostream>
using namespace std;
class MaxHeap {
private:
int* array;
int capacity;
int size;

void swap(int& a, int& b) {

int temp = a;
a = b;
b = temp;
}

void heapify(int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;

if (left < size && array[left] > array[largest]) {

largest = left;
}

if (right < size && array[right] > array[largest]) {

largest = right;
}

if (largest != i) {
swap(array[i], array[largest]);
heapify(largest);
}
}

public:
MaxHeap(int cap) : capacity(cap), size(0) {
array = new int[cap];
}

void insert(int value) {

if (size == capacity) {
cout << "Heap is full. Cannot insert more elements." << endl;
 return;
}

int i = size;
size = size + 1;
array[i] = value;

while (i != 0 && array[(i - 1) / 2] < array[i]) {

swap(array[i], array[(i - 1) / 2]);
i = (i - 1) / 2;
}
}

int extractMax() {
if (size == 0) {
cout << "Heap is empty. Cannot extract maximum element." <<
endl;
return -1;
}

int max = array[0];

array[0] = array[size - 1];
size = size - 1;
heapify(0);
return max;
}

int deleteMax() {
return extractMax();
}

void printHeap() {
cout << "Heap elements: ";
for (int i = 0; i < size; i++) {
cout << array[i] << " ";
}
cout << endl;
}
 ~MaxHeap() {
delete[] array;
}
};

int main() {
MaxHeap heap(10);
heap.insert(35);
heap.insert(33);
heap.insert(42);
heap.insert(10);
heap.insert(14);
heap.insert(19);
heap.insert(27);
heap.insert(44);
heap.insert(26);
heap.insert(31);
heap.printHeap();

return 0;
}

MIN HEAP
#include <iostream>
using namespace std;

class MaxHeap {
private:
 int* array;
int capacity;
int size;

void swap(int& a, int& b) {

int temp = a;
a = b;
b = temp;
}

void heapify(int i) {
int lowest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;

if (left < size && array[left] < array[lowest]) {

lowest = left;
}

if (right < size && array[right] < array[lowest]) {

lowest = right;
}

if (lowest != i) {
swap(array[i], array[lowest]);
heapify(lowest);
}
}

public:
MaxHeap(int cap) : capacity(cap), size(0) {
array = new int[cap];
}

void insert(int value) {

if (size == capacity) {
cout << "Heap is full. Cannot insert more elements." << endl;
return;
}
 int i = size;
size = size + 1;
array[i] = value;

while (i != 0 && array[(i - 1) / 2] > array[i]) {

swap(array[i], array[(i - 1) / 2]);
i = (i - 1) / 2;
}
}

void printHeap() {
cout << "Heap elements: ";
for (int i = 0; i < size; i++) {
cout << array[i] << " ";
}
cout << endl;
}

~MaxHeap() {
delete[] array;
}
};

int main() {
MaxHeap heap(10);
heap.insert(35);
heap.insert(33);
heap.insert(42);
heap.insert(10);
heap.insert(14);
heap.insert(19);
heap.insert(27);
heap.insert(44);
heap.insert(26);
 heap.insert(31);
heap.printHeap();

return 0;
}

ADJACENCY LIST
#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* next;
 Node(int value) : data(value), next(nullptr) {}
};

class Graph {
private:
int V;
Node** adj;

public:
Graph(int vertices) {
V = vertices;
adj = new Node * [V];
for (int i = 0; i < V; i++) {
adj[i] = nullptr;
}
}

void addEdge(int u, int v) {

Node* newNode = new Node(v);
newNode->next = adj[u];
adj[u] = newNode;

newNode = new Node(u);

newNode->next = adj[v];
adj[v] = newNode;
}

void printAdjacencyList() {
for (int i = 0; i < V; ++i) {
cout << "Adjacency list of vertex " << i << ": ";
Node* temp = adj[i];
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
}
};
int main() {
Graph g(4);
g.addEdge(0, 2);
g.addEdge(0, 1);
g.addEdge(1, 2);
g.addEdge(1, 3);

g.printAdjacencyList();

return 0;
}

BFS TRAVERSING IN GRAPH

#include<iostream>
using namespace std;

class queue
{
public:
int front;
int rear;
int arr[20];
queue()
{
front = 0;
rear = 0;
for (int i = 0; i < 20; i++)
{
arr[i] = 0;
}
}
bool isempty()
{
if (rear == 0 || front == rear)
{
return true;
}
return false;
}
bool isfull()
{
if (rear == 20)
{
return true;
}
return false;
}
void enqueue(int val)
{
if (isempty())
{
arr[front] = val;
rear++;
}
else if (isfull()) {
cout << "\nQUEUE IS FULL\n";
}
else
{
 arr[rear] = val;
rear++;
}
}
int dequeue()
{
int a=0;
if (isempty())
{
cout << "\nUEUE IS EMPTY\n";
}
else
{
a = arr[front];
front++;
}
return a;
}
};

class Graph
{
public:
int v;
int adj['v']['v'];
Graph(int v)
{
this->v = v;
for (int i = 0; i < v; i++)
{
for (int j = 0; j < v; j++)
{
adj[i][j] = 0;
}
}
}
void addedge(int source, int dest)
{
adj[source][dest] = 1;
 adj[dest][source] = 1;
}
void printadj()
{
for (int i = 0; i < v; i++)
{
for (int j = 0; j < v; j++)
{
cout << adj[i][j] << " ";
}
cout << endl;
}
}
void bfs(int v,int n)
{
bool visited[7] = { false };
cout << n << " ";
visited[n] = true;
queue obj;
obj.enqueue(n);
while (!obj.isempty())
{
int x = obj.dequeue();
for (int i = 0; i < v; i++)
{
if (adj[x][i] == 1 && visited[i] == false)
{
cout << i << " ";
visited[i] = true;
obj.enqueue(i);
}
}

}
};

int main()
{
Graph ob(7);
int node=0;
ob.addedge(0, 1);
ob.addedge(0, 2);
ob.addedge(0, 3);
ob.addedge(1, 3);
ob.addedge(2, 3);
ob.addedge(2, 4);
ob.addedge(3, 4);
ob.addedge(4, 5);
ob.addedge(4, 6);
ob.bfs(7, 0);
}

DFS TRAVERSAL CODE

void DFS(int v, int n)
{
static bool visited[7] = { false };
cout << n << " ";
visited[n] = true;
for (int j = 0; j < v; j++)
{
 if (adj[n][j] == 1 && visited[j] != true)
{
DFS(v,j);
}
}

BFS TRAVERSAL CODE

void bfs(int v,int n)
{
bool visited[7] = { false };
cout << n << " ";
visited[n] = true;
queue obj;
obj.enqueue(n);
while (!obj.isempty())
{
int x = obj.dequeue();
for (int i = 0; i < v; i++)
{
if (adj[x][i] == 1 && visited[i] == false)
{
cout << i << " ";
visited[i] = true;
obj.enqueue(i);
}
}

}
};
 DIJKSTRA’s ALGORITHM
#include <iostream>;
using namespace std;
#include <limits.h>
#define V 9
int minDistance(int dist[], bool sptSet[])
{
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
 if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}

void printSolution(int dist[])

{
cout << " Vertex \t Distance from Source " << endl;
for (int i = 0; i < V; i++)
cout << i << " \t\t" << dist[i] << endl;
}
void dijkstra(int graph[V][V], int src)
{
int dist[V];
bool sptSet[V];
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, sptSet[i] = false;
dist[src] = 0;
for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, sptSet);
sptSet[u] = true;
for (int v = 0; v < V; v++)
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
&& dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
printSolution(dist);
}
int main()
{
int graph[V][V] = {
{ 0, 4, 0, 0, 0, 0, 0, 8, 0 },
{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
 { 0, 0, 2, 0, 0, 0, 6, 7, 0 } };

dijkstra(graph, 0);
return 0;
}

PRIMS ALGORITHM
#include <iostream>
#include <climits>

#define V 5
class Graph {
int graph[V][V];
public:
Graph(int g[][V]) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
graph[i][j] = g[i][j];
}
}
}

int minKey(int key[], bool mstSet[]) {

int min = INT_MAX, min_index;

for (int v = 0; v < V; v++)

if (mstSet[v] == false && key[v] < min)
 min = key[v], min_index = v;

return min_index;
}

void primMST() {
int parent[V];
int key[V];
bool mstSet[V];
for (int i = 0; i < V; i++)
key[i] = INT_MAX, mstSet[i] = false;

key[0] = 0;
parent[0] = -1;
for (int count = 0; count < V - 1; count++) {
int u = minKey(key, mstSet);

mstSet[u] = true;

for (int v = 0; v < V; v++)

if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])

parent[v] = u, key[v] = graph[u][v];
}

printMST(parent);
}

void printMST(int parent[]) {

std::cout << "Edge \tWeight\n";
for (int i = 1; i < V; i++)
std::cout << parent[i] << " - " << i << " \t" << graph[i][parent[i]]
<< " \n";
}
};

int main() {
/* Let us create the following graph
2 3
 (0)---(1)---(2)
| / \ |
6| 8/ \5 |7
|/ \ |
(3)---------(4)
9 */
int graph[V][V] = { { 0, 2, 0, 6, 0 },
{ 2, 0, 3, 8, 5 },
{ 0, 3, 0, 0, 7 },
{ 6, 8, 0, 0, 9 },
{ 0, 5, 7, 9, 0 } };

Graph g(graph);
g.primMST();

return 0;
}