MAHARSHI DAYANAND

UNIVERSITY

DESIGN AND ANALYSIS OF

ALGORITHM LAB
• SUBMITTED BY :-
• SUBJECT CODE :-
• REGISTRATION NO. :-
• COURSE :- B.TECH CSE
Name: REGISTRATION NO.: -

INDEX
S.NO DATE PRACTICAL SIGN
1 21/08/2024 WAP in C++ for iterative and recursive
Binary Search.
2 28/08/2024 WAP in C++ to sort a given set of elements
using the Quick sort/Merge sort/Selection
sort and determine the time required to
sort the elements.
3 03/09/2024 WAP in C++ for implementation of
fractional knapsack problem using greedy
method and 0/1 knapsack problem using
dynamic programming.
4 04/09/2024 WAP to find the shortest path from a given
vertex to other vertices in a weighted
connected graph using Dijkstra’s
algorithm.
5 10/09/2024 WAP in C++ to find the minimum spanning
tree of a given undirected graph using
Kruskal’s algorithm /Prim’s algorithm.
6 17/09/2024 WAP in C++ to implement N-queens
problem using backtracking.
7 25/09/2024 WAP in C++ to check whether the given
graph is connected or not using DFS
method.
8 01/10/2024 WAP to implement the Travelling
Salesman Problem (TSP).
9 06/11/2024 WAP in C++ to check whether undirected
graph is connected using DFS.
10 09/11/2024 WAP in C++ to implement the subset sum
problem.

Page No.- 2
Name: REGISTRATION NO.: -

PROGRAM 1
Aim: Write a Program in C++ for iterative and recursive Binary Search
Code
Iterative:
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node *left, *right;};
bool iterativeSearch(struct Node* root, int key)
{while (root != NULL) {
if (key > root->data)
root = root->right;
else if (key < root->data)
root = root->left;
else
return true;}
return false;}
struct Node* newNode(int item)
{struct Node* temp = new Node;
temp->data = item;
temp->left = temp->right = NULL;
return temp;}
struct Node* insert(struct Node* Node, int data)
{ if (Node == NULL)
return newNode(data);
if (data < Node->data)
Node->left = insert(Node->left, data);
else if (data > Node->data)
Node->right = insert(Node->right, data);
return Node;}
int main()
{ struct Node* root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);

Page No.- 3
Name: REGISTRATION NO.: -

insert(root, 80);
if (iterativeSearch(root, 10))
cout<< "Yes, Element present at index ";
else
cout<< "No, Element not present";
return 0;}
Output:

Recursive
#include <iostream>
using namespace std;
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;}
int main(void)
{ int arr[] = { 2, 3, 4, 10, 40 };
int x = 4;
int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, 0, n - 1, x);
(result == -1)
? cout<< "Element not present in array"
: cout<< "Element present at " << result;
return 0;}

Page No.- 4
Name: REGISTRATION NO.: -

OUTPUT:

Explanation: Begin with the mid element of the whole array as a search key.
• If the value of the search key is equal to the item, then return an index of the search key.
• Or if the value of the search key is less than the item in the middle of the interval, narrow
the interval to the lower half.
• Otherwise, narrow it to the upper half.
• Repeatedly check from the second point until the value is found or the interval is empty.

COMPLEXITY- O(log n)

Page No.- 5
Name: REGISTRATION NO.: -

PROGRAM 2
Aim: WAP in C++ to sort a given set of elements using the Quick sort/Merge sort/Selection
sort and determine the time required to sort the elements.
Code:
Quick Sort

#include <iostream>
using namespace std;
void swap(int* a, int* b)
{int t = *a;
*a = *b;
*b = t;}
int partition (int arr[], int low, int high)
{int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++)
{ if (arr[j] < pivot)
{ i++;
swap(&arr[i], &arr[j]); }}
swap(&arr[i + 1], &arr[high]);
return (i + 1) }
void quickSort(int arr[], int low, int high)
{ if (low < high)
{ int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);}}
void printArray(int arr[], int size)
{int i;
for (i = 0; i< size; i++)
cout<<arr[i] << " ";
cout<<endl;}
int main()
{ int arr[] = {11, 6, 8, 9, 2, 4};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"Original Array:\n";
printArray(arr,n);
quickSort(arr, 0, n - 1);
cout<< "\nSorted Array: \n";
printArray(arr, n);
return 0;}
Explanation:
The Quick Sort algorithm is a Divide and Conquer algorithm. It initially selects an element as a
pivot element and partitions the given array around the picked pivot. There are many different
versions of quickSort that pick pivot in different ways.

Page No.- 6
Name: REGISTRATION NO.: -

• Always pick the first element as a pivot (implemented below).

• Always pick the last element as the pivot.
• Pick a random element as a pivot.
• Pick median as a pivot.
The key process in quickSort is the partition() process. The aim of the partition() function is to
receive an array and an element x of the array as a pivot, put x at its correct position in a sorted
array and then put all smaller elements (smaller than x) before x, and put all greater elements
(greater than x) after x.
Complexity- O(n*log(n))

OUTPUT:

Merge Sort
#include <iostream>
using namespace std;
void merge(int array[], int const left, int const mid, int const right)
{ auto const subArrayOne = mid - left + 1;
auto const subArrayTwo = right - mid;
auto *leftArray = new int[subArrayOne],
*rightArray = new int[subArrayTwo];
for (auto i = 0; i < subArrayOne; i++)
leftArray[i] = array[left + i];
for (auto j = 0; j < subArrayTwo; j++)
rightArray[j] = array[mid + 1 + j];
auto indexOfSubArrayOne = 0,
indexOfSubArrayTwo = 0;
int indexOfMergedArray = left;
while (indexOfSubArrayOne < subArrayOne && indexOfSubArrayTwo < subArrayTwo)
{ if (leftArray[indexOfSubArrayOne] <= rightArray[indexOfSubArrayTwo]) {
array[indexOfMergedArray] = leftArray[indexOfSubArrayOne];
indexOfSubArrayOne++;}
else {
array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo];

Page No.- 7
Name: REGISTRATION NO.: -

indexOfSubArrayTwo++; }
indexOfMergedArray++; }
while (indexOfSubArrayOne < subArrayOne) {
array[indexOfMergedArray] = leftArray[indexOfSubArrayOne];
indexOfSubArrayOne++;
indexOfMergedArray++; }
while (indexOfSubArrayTwo < subArrayTwo) {
array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo];
indexOfSubArrayTwo++;
indexOfMergedArray++; } }
void mergeSort(int array[], int const begin, int const end)
{ if (begin >= end)
return;
auto mid = begin + (end - begin) / 2;
mergeSort(array, begin, mid);
mergeSort(array, mid + 1, end);
merge(array, begin, mid, end);}
void printArray(int A[], int size)
{ for (auto i = 0; i < size; i++)
cout << A[i] << " "; }
int main()
{ int arr[] = { 9, 10, 12, 4, 6, 8 };
auto arr_size = sizeof(arr) / sizeof(arr[0]);
cout << "Original Array:\n";
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
cout << "\nSorted Array:\n";
printArray(arr, arr_size);
return 0;}
Explanation:
Think of it as a recursive algorithm continuously splits the array in half until it cannot be further
divided. This means that if the array becomes empty or has only one element left, the dividing
will stop, i.e. it is the base case to stop the recursion. If the array has multiple elements, split the
array into halves and recursively invoke the merge sort on each of the halves. Finally, when both
halves are sorted, the merge operation is applied. Merge operation is the process of taking two
smaller sorted arrays and combining them to eventually make a larger one.

Complexity: – O(n*log(n))

Page No.- 8
Name: REGISTRATION NO.: -

OUTPUT:

Selection Sort
#include <iostream>
using namespace std;
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void printArray(int array[], int size)
{
for (int i = 0; i < size; i++)
{
cout << array[i] << " ";
}
cout << endl;
}
void selectionSort(int array[], int size)
{
for (int step = 0; step < size - 1; step++)
{
int min_idx = step;
for (int i = step + 1; i < size; i++)
{
if (array[i] < array[min_idx])
min_idx = i;
}
swap(&array[min_idx], &array[step]);
}
}
int main()
{
int data[] = {20, 12, 10, 15, 2};

Page No.- 9
Name: REGISTRATION NO.: -

int size = sizeof(data) / sizeof(data[0]);

selectionSort(data, size);
cout << "Sorted array in Acsending Order:\n";
printArray(data, size);
}
OUTPUT:

Explanation:
The selection sort algorithm sorts an array by repeatedly finding the minimum element
(considering ascending order) from the unsorted part and putting it at the beginning.

The algorithm maintains two subarrays in a given array.

• The subarray which already sorted.

• The remaining subarray was unsorted.

In every iteration of the selection sort, the minimum element (considering ascending order) from
the unsorted subarray is picked and moved to the sorted subarray.

Complexity :– O(n2)

Page No.- 10
Name: REGISTRATION NO.: -

PROGRAM 3
Aim: WAP in C++ for implementation of fractional knapsack problem using greedy method
and 0/1 knapsack problem using dynamic programming
Code:
Fractional Knapsack
#include <iostream>
using namespace std;
struct Item {
int value, weight;
Item(int value, int weight)
: value(value), weight(weight)
{
} };
bool cmp(struct Item a, struct Item b)
{
double r1 = (double)a.value / a.weight;
double r2 = (double)b.value / b.weight;
return r1 > r2;
}
double fractionalKnapsack(struct Item arr[], int N, int size)
{
sort(arr, arr + size, cmp);
int curWeight = 0;
double finalvalue = 0.0;
for (int i = 0; i < size; i++) {
if (curWeight + arr[i].weight <= N) {
curWeight += arr[i].weight;
finalvalue += arr[i].value; }
else { int remain = N - curWeight;
finalvalue += arr[i].value* ((double)remain/ arr[i].weight);
break; } }
return finalvalue;
}
int main()
{ int N = 60;
Item arr[] = { { 100, 10 }, { 280, 40 }, { 120, 20 }, { 120, 24 } };
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum profit earned = "
<< fractionalKnapsack(arr, N, size);
return 0;
}

Page No.- 11
Name: REGISTRATION NO.: -

OUTPUT:

Explanation:
The basic idea of the greedy approach is to calculate the ratio value/weight for each item and sort
the item on the basis of this ratio. Then take the item with the highest ratio and add them until we
can’t add the next item as a whole and at the end add the next item as much as we can.
Complexity - O(N * log N)

0/1 Knapsack
#include <iostream>
using namespace std;
int max(int a, int b) { return (a > b) ? a : b; }
int knapSack(int W, int wt[], int val[], int n)
{
if (n == 0 || W == 0)
return 0;
if (wt[n - 1] > W)
return knapSack(W, wt, val, n - 1);
else
return max(val[n - 1]+ knapSack(W - wt[n - 1],wt, val, n - 1),knapSack(W, wt,
val, n - 1));
}
int main()
{
int val[] = { 60, 100, 120 };
int wt[] = { 10, 20, 30 };
int W = 50;
int n = sizeof(val) / sizeof(val[0]);
cout << knapSack(W, wt, val, n);

Page No.- 12
Name: REGISTRATION NO.: -

return 0;
}

OUTPUT:

EXPLANATION
In the Dynamic programming we will work considering the same cases as mentioned in the
recursive approach. In a DP[][] table let’s consider all the possible weights from ‘1’ to ‘W’ as the
columns and weights that can be kept as the rows.

Complexity - O(N*W)

Page No.- 13
Name: REGISTRATION NO.: -

PROGRAM 4
Aim: WAP to find the shortest path from a given vertex to other vertices in a weighted
connected graph using Dijkstra’s algorithm.
Code
#include<iostream>
using namespace std;
int miniDist(int distance[], bool Tset[]) // finding minimum distance
{int minimum=INT_MAX,ind;
for(int k=0;k<6;k++)
{if(Tset[k]==false && distance[k]<=minimum)
{minimum=distance[k];
ind=k;}}
return ind;}
void DijkstraAlgo(int graph[6][6],int src) // adjacency matrix
{int distance[6]; // // array to calculate the minimum distance for each node
bool Tset[6];// boolean array to mark visited and unvisited for each node
for(int k = 0; k<6; k++)
{distance[k] = INT_MAX;
Tset[k] = false;}
distance[src] = 0; // Source vertex distance is set 0
for(int k = 0; k<6; k++)
{int m=miniDist(distance,Tset);
Tset[m]=true;
for(int k = 0; k<6; k++)
{ if(!Tset[k] && graph[m][k] && distance[m]!=INT_MAX &&
distance[m]+graph[m][k]<distance[k])
distance[k]=distance[m]+graph[m][k] }}
cout<<"Vertex\t\tDistance from source vertex"<<endl;
for(int k = 0; k<6; k++)
{ char str=65+k;
cout<<str<<"\t\t\t"<<distance[k]<<endl;}}
int main()
{int graph[6][6]={
{0, 1, 2, 0, 0, 0},
{1, 0, 0, 5, 1, 0},
{2, 0, 0, 2, 3, 0},
{0, 5, 2, 0, 2, 2},
{0, 1, 3, 2, 0, 1},
{0, 0, 0, 2, 1, 0}};

Page No.- 14
Name: REGISTRATION NO.: -

DijkstraAlgo(graph,0);
return 0;}
OUTPUT:

Explanation:- Create a set sptSet (shortest path tree set) that keeps track of vertices included
in the shortest-path tree, i.e., whose minimum distance from the source is calculated and
finalized. Initially, this set is empty.
•Assign a distance value to all vertices in the input graph. Initialize all distance values as
INFINITE. Assign the distance value as 0 for the source vertex so that it is picked first.
• While sptSet doesn’t include all vertices
• Pick a vertex u which is not there in sptSet and has a minimum distance value.
• Include u to sptSet.
• Then update distance value of all adjacent vertices of u.
• To update the distance values, iterate through all adjacent vertices.
• For every adjacent vertex v, if the sum of the distance value of u (from source) and
weight of edge u-v, is less than the distance value of v, then update the distance value of
v.
Complexity:- O(V2)

Page No.- 15
Name: REGISTRATION NO.: -

PROGRAM 5
Aim: WAP in C++ to find the minimum cost spanning tree (MST)of a given undirected graph
using Kruskal’s algorithm/Prim’s algorithm.
Code
Krushkal’s Method
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> iPair;
struct Graph
{
int V, E;
vector< pair<int, iPair> > edges;
Graph(int V, int E)
{
this->V = V;
this->E = E;
}
void addEdge(int u, int v, int w)
{
edges.push_back({w, {u, v}});
}
int kruskalMST();
};
struct DisjointSets
{
int *parent, *rnk;
int n;
DisjointSets(int n)
{ this->n = n;
parent = new int[n+1];
rnk = new int[n+1];
for (int i = 0; i <= n; i++)
{
rnk[i] = 0;
parent[i] = i;
}
}
int find(int u)
{ if (u != parent[u])
parent[u] = find(parent[u]);
return parent[u];
}

Page No.- 16
Name: REGISTRATION NO.: -

void merge(int x, int y)

{
x = find(x), y = find(y);
if (rnk[x] > rnk[y])
parent[y] = x;
else
parent[x] = y;
if (rnk[x] == rnk[y])
rnk[y]++; } };
int Graph::kruskalMST()
{
int mst_wt = 0;
sort(edges.begin(), edges.end());
DisjointSets ds(V);
vector< pair<int, iPair> >::iterator it;
for (it=edges.begin(); it!=edges.end(); it++)
{ int u = it->second.first;
int v = it->second.second;
int set_u = ds.find(u);
int set_v = ds.find(v);
if (set_u != set_v)
{ cout << u << " - " << v << endl;
mst_wt += it->first;
ds.merge(set_u, set_v);
}
}
return mst_wt;
}
int main()
{
int V = 9, E = 14;
Graph g(V, E);
g.addEdge(0, 1, 4);
g.addEdge(0, 7, 8);
g.addEdge(1, 2, 8);
g.addEdge(1, 7, 11);
g.addEdge(2, 3, 7);
g.addEdge(2, 8, 2);
g.addEdge(2, 5, 4);
g.addEdge(3, 4, 9);
g.addEdge(3, 5, 14);
g.addEdge(4, 5, 10);
g.addEdge(5, 6, 2);

Page No.- 17
Name: REGISTRATION NO.: -

g.addEdge(6, 7, 1);
g.addEdge(6, 8, 6);
g.addEdge(7, 8, 7);
cout << "Edges of MST are \n";
cout << "Edges of MST -\n";
int mst_wt = g.kruskalMST();
cout << "\nWeight of MST - " << mst_wt;
return 0;
}
Output:

Explanation
Given a connected and undirected graph, a spanning tree of that graph is a subgraph that is a tree
and connects all the vertices together. A single graph can have many different spanning trees. A
minimum spanning tree (MST) or minimum weight spanning tree for a weighted, connected,
undirected graph is a spanning tree with a weight less than or equal to the weight of every other
spanning tree. The weight of a spanning tree is the sum of weights given to each edge of the
spanning tree.

Below are the steps for finding MST using Kruskal’s algorithm:

• Sort all the edges in non-decreasing order of their weight.

• Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If
cycle is not formed, include this edge. Else, discard it.
• Repeat step#2 until there are (V-1) edges in the spanning tree.

Complexity- O(ElogE) or O(ElogV)

Page No.- 18
Name: REGISTRATION NO.: -

Prim’s Method
#include <iostream>
using namespace std;
#define V 5
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 printMST(int parent[], int graph[V][V])
{
cout<<"Edge \tWeight\n";
for (int i = 1; i < V; i++)
cout<<parent[i]<<" - "<<i<<" \t"<<graph[i][parent[i]]<<" \n";
}
void primMST(int graph[V][V])
{ 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, graph);
}
int main()
{
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 } };
primMST(graph);
return 0;
}

Page No.- 19
Name: REGISTRATION NO.: -

Output:

Explanation
The idea behind Prim’s algorithm is simple, a spanning tree means all vertices must be
connected. So the two disjoint subsets (discussed above) of vertices must be connected to make a
Spanning Tree. And they must be connected with the minimum weight edge to make it a
Minimum Spanning Tree.

Follow the given steps to find MST using Prim’s Algorithm:

• Create a set mstSet that keeps track of vertices already included in MST.
• Assign a key value to all vertices in the input graph. Initialize all key values as
INFINITE. Assign the key value as 0 for the first vertex so that it is picked first.
• While mstSet doesn’t include all vertices
• Pick a vertex u which is not there in mstSet and has a minimum key value.
• Include u in the mstSet.
• Update the key value of all adjacent vertices of u. To update the key values, iterate
through all adjacent vertices. For every adjacent vertex v, if the weight of edge u-v is less
than the previous key value of v, update the key value as the weight of u-v

The idea of using key values is to pick the minimum weight edge from the cut. The key values
are used only for vertices that are not yet included in MST, the key value for these vertices
indicates the minimum weight edges connecting them to the set of vertices included in MST.

Complexity- O(V2)

Page No.- 20
Name: REGISTRATION NO.: -

PROGRAM 6
Aim: WAP in C++ to implement N-queens problem using backtracking
Code:
#include<iostream>
using namespace std;
int grid[10][10];
//print the solution
void print(int n) {
for (int i = 0;i <= n-1; i++) {
for (int j = 0;j <= n-1; j++) {
cout <<grid[i][j]<< " ";
}
cout<<endl;
}
cout<<endl;
cout<<endl;
}
//function for check the position is safe or not
//row is indicates the queen no. and col represents the possible positions
bool isSafe(int col, int row, int n) {
//check for same column
for (int i = 0; i < row; i++) {
if (grid[i][col]) {
return false;
}
}
//check for upper left diagonal
for (int i = row,j = col;i >= 0 && j >= 0; i--,j--) {
if (grid[i][j]) {
return false;
}
}
//check for upper right diagonal
for (int i = row, j = col; i >= 0 && j < n; j++, i--) {
if (grid[i][j]) {
return false;
}
}
return true;

Page No.- 21
Name: REGISTRATION NO.: -

}
//function to find the position for each queen
//row is indicates the queen no. and col represents the possible positions
bool solve (int n, int row) {
if (n == row) {
print(n);
return true;
}
//variable res is use for possible backtracking
bool res = false;
for (int i = 0;i <=n-1;i++) {
if (isSafe(i, row, n)) {
grid[row][i] = 1;
//recursive call solve(n, row+1) for next queen (row+1)
res = solve(n, row+1) || res;//if res ==false then backtracking will occur
//by assigning the grid[row][i] = 0

grid[row][i] = 0;
}
}
return res;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cout<<"Enter the number of queen"<<endl;
cin >> n;
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
grid[i][j] = 0;
}
}
bool res = solve(n, 0);
if(res == false) {
cout << -1 << endl; //if there is no possible solution
} else {
cout << endl;
}

Page No.- 22
Name: REGISTRATION NO.: -

return 0;
}
Output:

Explanation
The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two
queens attack each other. For example, the following is a solution for the 4 Queen problem.
Backtracking Algorithm
The idea is to place queens one by one in different columns, starting from the leftmost column.
When we place a queen in a column, we check for clashes with already placed queens. In the
current column, if we find a row for which there is no clash, we mark this row and column as
part of the solution. If we do not find such a row due to clashes, then we backtrack and return
false.

Complexity- O(N!)

Page No.- 23
Name: REGISTRATION NO.: -

Program 7
Aim: WAP in C++ to check whether the given graph is connected or not using DFS method
Code:
#include <iostream>
using namespace std;
#define N 100000
vector<int> gr1[N], gr2[N];
bool vis1[N], vis2[N];
void Add_edge(int u, int v)
{
gr1[u].push_back(v);
gr2[v].push_back(u);
}
void dfs1(int x)
{
vis1[x] = true;
for (auto i : gr1[x])
if (!vis1[i])
dfs1(i);
}
// DFS function
void dfs2(int x)
{
vis2[x] = true;
for (auto i : gr2[x])
if (!vis2[i])
dfs2(i);
}
bool Is_Connected(int n)
{
memset(vis1, false, sizeof vis1);
dfs1(1);
memset(vis2, false, sizeof vis2);
dfs2(1);
for (int i = 1; i <= n; i++) {
if (!vis1[i] and !vis2[i])
return false; }
return true;
}

Page No.- 24
Name: REGISTRATION NO.: -

int main()
{
int n = 4;
Add_edge(1, 2);
Add_edge(1, 3);
Add_edge(2, 3);
Add_edge(3, 4);
if (Is_Connected(n))
cout << "Graph connected.";
else
cout << "Graph not connected";
return 0;
}
Output:

Explanation
• Take two bool arrays vis1 and vis2 of size N (number of nodes of a graph) and keep false
in all indexes.
• Start at a random vertex v of the graph G, and run a DFS(G, v).
• Make all visited vertices v as vis1[v] = true.
• Now reverse the direction of all the edges.
• Start DFS at the vertex which was chosen at step 2.
• Make all visited vertices v as vis2[v] = true.
• If any vertex v has vis1[v] = false and vis2[v] = false then the graph is not connected.

Complexity- O(V+E)

Page No.- 25
Name: REGISTRATION NO.: -

PROGRAM 8
Aim: WAP to implement the Travelling Salesman Problem (TSP)
Code
#include <bits/stdc++.h>
using namespace std;
#define V 4
// implementation of traveling Salesman Problem
int travllingSalesmanProblem(int graph[][V], int s)
{
// store all vertex apart from source vertex
vector<int> vertex;
for (int i = 0; i < V; i++)
if (i != s)
vertex.push_back(i);
// store minimum weight Hamiltonian Cycle.
int min_path = INT_MAX;
do {
// store current Path weight(cost)
int current_pathweight = 0;
// compute current path weight
int k = s;
for (int i = 0; i < vertex.size(); i++) {
current_pathweight += graph[k][vertex[i]];
k = vertex[i];
}
current_pathweight += graph[k][s];
// update minimum
min_path = min(min_path, current_pathweight);
} while (
next_permutation(vertex.begin(), vertex.end()));
return min_path;
}
// Driver Code
int main()
{
// matrix representation of graph
int graph[][V] = { { 0, 10, 15, 20 },
{ 10, 0, 35, 25 },
{ 15, 35, 0, 30 },

Page No.- 26
Name: REGISTRATION NO.: -

{ 20, 25, 30, 0 } };

int s = 0;
cout << travllingSalesmanProblem(graph, s) << endl;
return 0;}
Output:

Explanation
Given a set of cities and distances between every pair of cities, the problem is to find the shortest
possible route that visits every city exactly once and returns to the starting point.

Note the difference between Hamiltonian Cycle and TSP. The Hamiltonian cycle problem is to
find if there exists a tour that visits every city exactly once. Here we know that Hamiltonian Tour
exists (because the graph is complete) and in fact, many such tours exist, the problem is to find a
minimum weight Hamiltonian Cycle.

For example, consider the graph shown in the figure on the right side. A TSP tour in the graph is
1-2-4-3-1. The cost of the tour is 10+25+30+15 which is 80.

The problem is a famous NP-hard problem. There is no polynomial-time known solution for this
problem.

In this post, the implementation of a simple solution is discussed.

1. Consider city 1 as the starting and ending point. Since the route is cyclic, we can consider
any point as a starting point.
2. Generate all (n-1)! permutations of cities.
3. Calculate the cost of every permutation and keep track of the minimum cost permutation.
4. Return the permutation with minimum cost.

Complexity- The complexity of TSP using Greedy will be O(N^2LogN) and using DP will be
O(N^22^N).

Page No.- 27
Name: REGISTRATION NO.: -

PROGRAM 9
Aim: WAP in C++ to check whether undirected graph is connected using DFS.
Code
#include <iostream>
#include <list>
#include <stack>
using namespace std;
class Graph
{
private:
int V;
list<int> *adj;
void DFSUtil(int v, bool visited[]);
public:
Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
~Graph()
{
delete [] adj;
}
void addEdge(int v, int w);
bool isConnected();
Graph getTranspose();
};
void Graph::DFSUtil(int v, bool visited[])
{
visited[v] = true;
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i, visited);
}
Graph Graph::getTranspose()
{
Graph g(V);
for (int v = 0; v < V; v++)

Page No.- 28
Name: REGISTRATION NO.: -

{
list<int>::iterator i;
for(i = adj[v].begin(); i != adj[v].end(); ++i)
{
g.adj[*i].push_back(v);
}
}
return g;
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
adj[w].push_back(v);
}
bool Graph::isConnected()
{
bool visited[V];
for (int i = 0; i < V; i++)
visited[i] = false;
DFSUtil(0, visited);
for (int i = 0; i < V; i++)
if (visited[i] == false)
return false;
Graph gr = getTranspose();
for(int i = 0; i < V; i++)
visited[i] = false;
gr.DFSUtil(0, visited);
for (int i = 0; i < V; i++)
if (visited[i] == false)
return false;
return true;
}
int main()
{
Graph g1(5);
g1.addEdge(0, 1);
g1.addEdge(1, 2);
g1.addEdge(2, 3);
g1.addEdge(3, 0);
g1.addEdge(2, 4);

Page No.- 29
Name: REGISTRATION NO.: -

g1.addEdge(4, 2);
if (g1.isConnected())
cout<<"The Graph is Conneted"<<endl;
else
cout<<"The Graph is not Connected"<<endl;
Graph g2(4);
g2.addEdge(0, 1);
g2.addEdge(1, 2);
g2.addEdge(2, 3);
if (g2.isConnected())
cout<<"The Graph is Connected"<<endl;
else
cout<<"The Graph is not Connected"<<endl;
return 0;}

OUTPUT:

Page No.- 30
Name: REGISTRATION NO.: -

PROGRAM 10
Aim: WAP in C++ to implement the subset sum problem.
Code
#include<iostream>
using namespace std;
void solve(int a[], int n, int sum)
{
int i,j;
int dp[n+1][sum+1];
for(i=0;i<=n;i++)
dp[i][0]=1;
for(j=0;j<=n;j++)
dp[0][j]=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=sum;j++)
{
if(j<a[i])
dp[i][j]=dp[i-1][j];
else
dp[i][j]=dp[i-1][j] || dp[i-1][j-a[i]];
}
}
if(dp[n][sum]==1)
cout<<"Possible"<<endl;

else
cout<<"Not Possible"<<endl;
}
int main()
{
int n;
cin>>n;
int a[n];
for(long i=0;i<n;i++)
{
cin>>a[i];
}
int sum;

Page No.- 31
Name: REGISTRATION NO.: -

cin>>sum;
solve(a,n,sum);}

OUTPUT:

Explanation:
1. Consider the last element and now the required sum = target sum – value of ‘last’ element
and number of elements = total elements – 1
2. Leave the ‘last’ element and now the required sum = target sum and number of elements
= total elements – 1

Complexity:
The above solution may try all subsets of given set in worst case. Therefore time complexity of
the above solution is exponential. The problem is in-fact NP-Complete (There is no known
polynomial time solution for this problem).

Page No.- 32