//IMPLEMENTATION OF QUICK SORT

#include<stdio.h>
void swap(int *a,int *b){
int t=*a;
*a=*b;*b=t;
}
int partition(int a[],int lb, int ub){
int i =lb,j=ub,pivot=a[lb];
while(i<j){
while(a[i]<=pivot)i++;
while(a[j]>pivot)j--;
if(i<=j){
swap(&a[i],&a[j]);
}
}
swap(&a[lb],&a[j]);
return j;
}
void Quick(int a[],int lb,int ub){
if(lb<ub){
int pivot=partition(a,lb,ub);
Quick(a,lb,pivot-1);
Quick(a,pivot+1,ub);
}
}
void main(){
int n;
printf("Number of elements in the array:");
scanf("%d",&n);
int a[n];
for(int i=0;i<n;scanf("%d",&a[i++]));
Quick(a,0,n-1);
printf("The sorted array:\n");
for(int i=0;i<n;printf("%d\t",a[i++]));
}

OUTPUT:

Number of elements in the array:6

12 7 6 5 4 3
The sorted array:
3 4 5 6 7 12
//IMPLEMENTATION OF MERGE SORT
#include<stdio.h>
void Merge(int a[],int lb,int mid,int ub)
{
int t[ub-lb+1],i=lb,j=mid+1,k=lb;
while(i<=mid && j<=ub)
{
if(a[i]<=a[j]) t[k]=a[i++];
else t[k]=a[j++];
k++;
}
while(j<=ub) t[k++]=a[j++];//remaining elements of right sub array
while(i<=mid) t[k++]=a[i++];//remaining elements of left sub array
for(k=lb;k<=ub;k++) a[k]=t[k];//copying the data from the temp array to original array
}
void Merge_sort(int a[],int lb,int ub)
{
int mid;
if(lb<ub)
{
mid=(lb+ub)/2;
Merge_sort(a,lb,mid);
Merge_sort(a,mid+1,ub);
Merge(a,lb,mid,ub);
}
}
void main()
{
int n;
printf("Enter the number of elements in the array:");
scanf("%d",&n);
int a[n];
printf("Enter the array Elements\n");
for(int i=0;i<n;scanf("%d",&a[i++]));
Merge_sort(a,0,n-1);
printf("\nThe sorted array:\n");
for(int i=0;i<n; printf("%d\t",a[i++]));
}

OUTPUT:
Enter the number of elements in the array:6
Enter the array Elements
23 45 3 2 1 4

The sorted array:

1 2 3 4 23 45
//IMPLEMENTATION OF HEAP SORT
#include<stdio.h>
void swap(int * a,int *b){
int t=*a;
*a=*b;
*b=t;
}
void heapify(int a[],int n,int i){
int p=i,l=2*p,r=l+1;
if(l<n && a[l]>=a[p])p=l;
if(r<n && a[r]>a[p])p=r;
if(p!=i){swap(&a[p],&a[i]);heapify(a,n,p);}
}
void heapsort(int a[],int n){
for(int i=n/2-1;i>=0;heapify(a,n,i--));
for(int i=n-1;i>=1;i--){
swap(&a[0],&a[i]);
heapify(a,i,0);
}
}
void main(){
int n;
printf("Number of elements in the array:");
scanf("%d",&n);
int a[n];
printf("Enter the array elements:\n");
for(int i=0;i<n;scanf("%d",&a[i++]));
heapsort(a,n);
printf("The sorted array :\n");
for(int i=0;i<n;printf("%d\t",a[i++]));
}

OUTPUT:

Number of elements in the array:5

Enter the array elements:
23 5 4 2 1
The sorted array :
1 2 4 5 23
//IMPLEMENTATION OF JOB SEQUENCING WITH DEADLINES
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct Job {

char jname[10]; // Job Id

int dline; // Deadline of job
int profit; // Profit if job is over before or on
// deadline
} Job;
int compare(const void* a, const void* b)
{
Job* temp1 = (Job*)a;
Job* temp2 = (Job*)b;
return (temp2->profit - temp1->profit);
}
int min(int num1, int num2)
{
return (num1 > num2) ? num2 : num1;
}

void JobScheduling(Job arr[], int n)

{
qsort(arr, n, sizeof(Job), compare);
int result[n];
bool timeslot[n];
for (int i = 0; i < n; i++)
timeslot[i] = false;
for (int i = 0; i < n; i++) {
for (int j = min(n, arr[i].dline) - 1; j >= 0; j--) {
if (timeslot[j] == false) {
result[j] = i; // Add this job to result
timeslot[j] = true; // Make this timeslot occupied
break;
}
}
}
for (int i = 0; i < n; i++)
if (timeslot[i])
printf("%s\t", arr[result[i]].jname);
}
int main()
{
int n;
printf("Enter number of jobs:");
scanf("%d",&n);
Job arr[n];
 int dmax;
for(int i=0;i<n;i++){
printf("Enter job name:");
scanf("%s",arr[i].jname);
printf("Enter %s profit:",arr[i].jname);
scanf("%d",&arr[i].profit);
printf("Enter %s deadline:",arr[i].jname);
scanf("%d",&arr[i].dline);
dmax=(dmax>=arr[i].dline)?dmax:arr[i].dline;
}
printf("Following is maximum profit sequence of jobs \n");
JobScheduling(arr, n);
return 0;
}

OUTPUT:

Enter number of jobs:6

Enter job name:j1
Enter j1 profit:20
Enter j1 deadline:3
Enter job name:j2
Enter j2 profit:15
Enter j2 deadline:1
Enter job name:j3
Enter j3 profit:10
Enter j3 deadline:1
Enter job name:j4
Enter j4 profit:7
Enter j4 deadline:3
Enter job name:j5
Enter j5 profit:5
Enter j5 deadline:1
Enter job name:j6
Enter j6 profit:3
Enter j6 deadline:3
Following is maximum profit sequence of jobs
j2 j4 j1
//IMPLEMENTATION OF 0/1 KNAPSACK PROBLEM
#include <stdio.h>
#define MAX(x, y) (((x) > (y)) ? (x) : (y))

int knapsack(int n, int W, int weight[], int value[])

{
//Create a 2D array that stores the optimum value for each item
int K[n+1][W+1];

//Initialize all values of K to 0

int i, w;
for (i = 0; i <= n; i++)
{
for (w = 0; w <= W; w++)
{
if (i==0 || w==0)
K[i][w] = 0;
else if (weight[i-1] <= w)
K[i][w] = MAX(value[i-1] + K[i-1][w-weight[i-1]], K[i-1][w]);
else
K[i][w] = K[i-1][w];
}
}
int select[n];
for(int i=0;i<n;select[i++]=0);
for(int i=0;i<=n;i++){
for(int j=0;j<=W;j++){
printf("%3d",K[i][j]);
}
printf("\n");
}
printf("\n");
i=n;
for(int j=W;j>0 && i>0;){
if(K[i][j]==K[i-1][j]){
select[i-1]=0;

}
else{
select[i-1]=1;
j-=weight[i-1];

}
i--;
}
printf("\n The selection vector:\n{");

for(int i=0;i<n;printf("%2d,",select[i++]));
printf("}\n");
return K[n][W];
}

int main()
{
int n, W;
printf("Enter the number of items: ");
scanf("%d",&n);
printf("Enter knapsack: ");
scanf("%d",&W);
int i;
int value[n], weight[n];
for(i=0;i<n;i++)
{
printf("Enter the weight and value of item %d: ",i+1);
scanf("%d%d",&weight[i],&value[i]);
}
printf("The maximum value of knapsack is: %d", knapsack(n, W, weight, value));

return 0;
}

OUTPUT:
Enter the number of items: 3
Enter knapsack: 3
Enter the weight and value of item 1: 1 2
Enter the weight and value of item 2: 2 3
Enter the weight and value of item 3: 3 4
0 0 0 0
0 2 2 2
0 2 3 5
0 2 3 5

The selection vector:

{ 1, 1, 0,}
The maximum value of knapsack is: 5
//IMPLEMENTATION OF ALL PAIR SHORTEST PATH ALGORITHM
#include<stdio.h>
#include<math.h>
void main(){
int n;
printf("Enter the number of vertices:");
scanf("%d",&n);
double A[n][n];
printf("Enter the values int in the adjacency matrix:\n");
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
scanf("%lf",&A[i][j]);
}
}
for(int i=0;i<n;i++)A[i][i]=0;
//all source shortes path calculation
for(int k=0;k<n;k++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
A[i][j]=(A[i][j]<(A[i][k]+A[k][j]))?A[i][j]:A[i][k]+A[k][j];
}
}
//the finalized shortest paths
printf("The all pairs shortest path of given graph is :\n");
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
printf("%.0lf\t",A[i][j]);
}
printf("\n");
}
}

OUTPUT

Enter the number of vertices:3

Enter the values int in the adjacency matrix:
285
308
inf 2 0
The all pairs shortest path of given graph is :
0 7 5
3 0 8
5 2 0
//IMPLEMENTATION OF TRAVELLING SALESPERSON PROBLEM
#include<stdio.h>
int a[10][10], visited[10], n, cost = 0;
void get() {
int i, j;
printf("Enter No. of Cities: ");
scanf("%d", &n);
printf("\nEnter Cost Matrix: \n");
for (i = 0; i < n; i++) {
printf("\n Enter Elements of Row# : %d\n", i + 1);
for (j = 0; j < n; j++)
scanf("%d", &a[i][j]);
visited[i] = 0;
}
printf("\n\nThe cost list is:\n\n");
for (i = 0; i < n; i++) {
printf("\n\n");
for (j = 0; j < n; j++)
printf("\t % d", a[i][j]);
}
}
int least(int c) {
int i, nc = 999;
int min = 999, kmin;
for (i = 0; i < n; i++) {
if ((a[c][i] != 0) && (visited[i] == 0))
if (a[c][i] < min) {
min = a[i][0] + a[c][i];
kmin = a[c][i];
nc = i;
}
}
if (min != 999)
cost += kmin;
return nc;
}
void mincost(int city) {
int i, ncity;
visited[city] = 1;
printf("%d –>", city + 1);
ncity = least(city);
if (ncity == 999) {
ncity = 0;
printf("%d", ncity + 1);
cost += a[city][ncity];
return;
}
mincost(ncity);
}
void put() {
printf("\n\nMinimum cost:");
printf("%d", cost);
}
void main() {
get();
printf("\n\nThe Path is:\n\n");
mincost(0);
put();
}
OUTPUT:
Enter No. of Cities: 4

Enter Cost Matrix:

Enter Elements of Row# : 1

0 10 15 21

Enter Elements of Row# : 2

5 0 9 10

Enter Elements of Row# : 3

6 13 0 12

Enter Elements of Row# : 4

8890

The cost list is:

0 10 15 21

5 0 9 10

6 13 0 12

8 8 9 0

The Path is:

1 –>2 –>4 –>3 –>1

Minimum cost:35
//IMPLEMENTATION OF PRIM'S ALGORITHM
#include<stdio.h>
#include<stdlib.h>
#define infinity 9999
#define MAX 20

int G[MAX][MAX],spanning[MAX][MAX],n;

int prims();

int main()
{
int i,j,total_cost;
printf("Enter no. of vertices:");
scanf("%d",&n);
printf("\nEnter the adjacency matrix:\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&G[i][j]);
total_cost=prims();
printf("\nspanning tree matrix:\n");
for(i=0;i<n;i++)
{
printf("\n");
for(j=0;j<n;j++)
printf("%d\t",spanning[i][j]);
}
printf("\n\nTotal cost of spanning tree=%d",total_cost);
return 0;
}

int prims()
{
int cost[MAX][MAX];
int u,v,min_distance,distance[MAX],from[MAX];
int visited[MAX],no_of_edges,i,min_cost,j;
//create cost[][] matrix,spanning[][]
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(G[i][j]==0)
cost[i][j]=infinity;
else
cost[i][j]=G[i][j];
spanning[i][j]=0;
}
//initialise visited[],distance[] and from[]
distance[0]=0;
 visited[0]=1;
for(i=1;i<n;i++)
{
distance[i]=cost[0][i];
from[i]=0;
visited[i]=0;
}
min_cost=0; //cost of spanning tree
no_of_edges=n-1; //no. of edges to be added
while(no_of_edges>0)
{
//find the vertex at minimum distance from the tree
min_distance=infinity;
for(i=1;i<n;i++)
if(visited[i]==0&&distance[i]<min_distance)
{
v=i;
min_distance=distance[i];
}
u=from[v];
//insert the edge in spanning tree
spanning[u][v]=distance[v];
spanning[v][u]=distance[v];
no_of_edges--;
visited[v]=1;
//updated the distance[] array
for(i=1;i<n;i++)
if(visited[i]==0&&cost[i][v]<distance[i])
{
distance[i]=cost[i][v];
from[i]=v;
}
min_cost=min_cost+cost[u][v];
}
return(min_cost);
}

OUTPUT:
Enter no. of vertices:7

Enter the adjacency matrix:

0 25 0 0 0 10 0
25 0 14 0 0 0 12
0 14 0 11 0 0 0
0 0 11 0 20 0 17
0 0 0 20 0 23 22
10 0 0 0 23 0 0
0 12 0 17 22 0 0
spanning tree matrix:

0 0 0 0 0 10 0
0 0 14 0 0 0 12
0 14 0 11 0 0 0
0 0 11 0 20 0 0
0 0 0 20 0 23 0
10 0 0 0 23 0 0
0 12 0 0 0 0 0

Total cost of spanning tree=90

//IMPLEMENTATION OF KRUSKAL’S ALGORITHM
#include<stdio.h>
#include<stdlib.h>
#define VAL 999
int i,j,k,a,b,u,v,n,ne=1;
int min,mincost=0,cost[9][9],parent[9];
// union - find
int find(int i)
{
while(parent[i])
i=parent[i];
return i;
}
int uni(int i,int j)
{
if(i!=j)
{
parent[j]=i;
return 1;
}
return 0;
}
int main()
{
printf("Implementation of Kruskal's algorithm\n");
printf("Enter the no. of vertices:");
scanf("%d",&n);
printf("Enter the cost adjacency matrix:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=VAL;
}
}
printf("The edges of Minimum Cost Spanning Tree are\n");
while(ne < n)
{
for(i=1,min=VAL;i<=n;i++)
{
for(j=1;j <= n;j++)
{
if(cost[i][j] < min)
{
min=cost[i][j];
 a=u=i;
b=v=j;
}
}
}
u=find(u);
v=find(v);
if(uni(u,v))
{
// printing edges
printf("%d edge (%d,%d) =%d\n",ne++,a,b,min);
mincost +=min;
}
cost[a][b]=cost[b][a]=999;
}
// minimum cost
printf("\n\tMinimum cost = %d\n",mincost);
return 0;
}

OUTPUT:
Implementation of Kruskal's algorithm
Enter the no. of vertices:7
Enter the cost adjacency matrix:
0 25 0 0 0 10 0
25 0 14 0 0 0 12
0 14 0 11 0 0 0
0 0 11 0 20 0 17
0 0 0 20 0 23 22
10 0 0 0 23 0 0
0 12 0 17 22 0 0
The edges of Minimum Cost Spanning Tree are
1 edge (1,6) =10
2 edge (3,4) =11
3 edge (2,7) =12
4 edge (2,3) =14
5 edge (4,5) =20
6 edge (5,6) =23

Minimum cost = 90
//IMPLEMENTATION OF SINGLE SOURCE SHORTEST PATH
#include<stdio.h>
#define INFINITY 9999
#define MAX 10

void dijikstra(int G[MAX][MAX], int n, int startnode);

void main(){
int G[MAX][MAX], i, j, n, u;
printf("\nEnter the no. of vertices:: ");
scanf("%d", &n);
printf("\nEnter the adjacency matrix::\n");
for(i=0;i < n;i++)
for(j=0;j < n;j++)
scanf("%d", &G[i][j]);
printf("\nEnter the starting node:: ");
scanf("%d", &u);
dijikstra(G,n,u);
}

void dijikstra(int G[MAX][MAX], int n, int startnode)

{
int cost[MAX][MAX], distance[MAX], pred[MAX];
int visited[MAX], count, mindistance, nextnode, i,j;
for(i=0;i < n;i++)
for(j=0;j < n;j++)
if(G[i][j]==0)
cost[i][j]=INFINITY;
else
cost[i][j]=G[i][j];

for(i=0;i< n;i++)
{
distance[i]=cost[startnode][i];
pred[i]=startnode;
visited[i]=0;
}
distance[startnode]=0;
visited[startnode]=1;
count=1;
while(count < n-1){
mindistance=INFINITY;
for(i=0;i < n;i++)
if(distance[i] < mindistance&&!visited[i])
{
mindistance=distance[i];
nextnode=i;
 }
visited[nextnode]=1;
for(i=0;i < n;i++)
if(!visited[i])
if(mindistance+cost[nextnode][i] < distance[i])
{
distance[i]=mindistance+cost[nextnode][i];
pred[i]=nextnode;
}
count++;
}

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

if(i!=startnode)
{
printf("\nDistance of %d = %d", i, distance[i]);
printf("\nPath = %d", i);
j=i;
do
{
j=pred[j];
printf(" <-%d", j);
}
while(j!=startnode);
}
}
OUTPUT:
Enter the no. of vertices:: 5

Enter the adjacency matrix::

03100
30751
17020
85201
01010

Enter the starting node:: 0

Distance of 1 = 3 3
Path = 1 <-0 3 1
2 5 4
Distance of 2 = 1 1
Path = 2 <-0 5
Distance of 3 = 3 1 7
Path = 3 <-2 <-0 7
Distance of 4 = 4
3 4
Path = 4 <-1 <-0[1 2
1 3
//IMPLEMENTATION OF SUM OF SUBSETS PROBLEM
#include<stdio.h>
#define TRUE 1
#define FALSE 0
int inc[50],w[50],sum,n;
void sumset(int i,int wt,int total);
int promising(int i,int wt,int total) {
return(((wt+total)>=sum)&&((wt==sum)||(wt+w[i+1]<=sum)));
}

void main() {
int i,j,n,temp,total=0;
printf("Enter how many numbers:\n");
scanf("%d",&n);
printf("Enter %d numbers to th set:\n",n);
for (i=0;i<n;i++) {
scanf("%d",&w[i]);
total+=w[i];
}
printf("Input the sum value to create sub set:\n");
scanf("%d",&sum);
for (i=0;i<=n;i++)
for (j=0;j<n-1;j++)
if(w[j]>w[j+1]) {
temp=w[j];
w[j]=w[j+1];
w[j+1]=temp;
}
printf("\n The given %d numbers in ascending order:\n",n);
for (i=0;i<n;i++)
printf("%d \t",w[i]);
if((total<sum))
printf("\n Subset construction is not possible"); else {
for (i=0;i<n;i++)
inc[i]=0;
printf("\n The solution using backtracking is:\n");
sumset(-1,0,total);
}

}
void sumset(int i,int wt,int total) {
int j;
if(promising(i,wt,total)) {
if(wt==sum) {
printf("\n{\t");
for (j=0;j<=i;j++)
 if(inc[j])
printf("%d\t",w[j]);
printf("}\n");
} else {
inc[i+1]=TRUE;
sumset(i+1,wt+w[i+1],total-w[i+1]);
inc[i+1]=FALSE;
sumset(i+1,wt,total-w[i+1]);
}
}
}

OUTPUT:

Enter how many numbers:

4
Enter 4 numbers to th set:
1345
Input the sum value to create sub set:
8

The given 4 numbers in ascending order:

1 3 4 5
The solution using backtracking is:

{ 1 3 4 }

{ 3 5 }
//IMPLEMENTATTION OF OPTIMAL BINARY SEARCH TREE
#include<stdio.h>
#define MAX 10

void main()
{
char ele[MAX][MAX];
int w[MAX][MAX], c[MAX][MAX], r[MAX][MAX], p[MAX], q[MAX];
int temp=0, root, min, min1, n;
int i,j,k,b;
printf("Enter the number of elements:");
scanf("%d",&n);
printf("\n");
for(i=1; i <= n; i++)
{
printf("Enter the Element of %d:",i);
scanf("%d",&p[i]);
}
printf("\n");
for(i=0; i <= n; i++)
{
printf("Enter the Probability of %d:",i);
scanf("%d",&q[i]);
}
printf("W\t\tC\t\tR\n");
for(i=0; i <= n; i++)
{
for(j=0; j <= n; j++)
{
if(i == j)
{
w[i][j] = q[i];
c[i][j] = 0;
r[i][j] = 0;
printf("W[%d][%d]: %d\tC[%d][%d]: %d\tR[%d][%d]: %d\
n",i,j,w[i][j],i,j,c[i][j],i,j,r[i][j]);
}
}
}
printf("\n");
for(b=0; b < n; b++)
{
for(i=0,j=b+1; j < n+1 && i < n+1; j++,i++)
{
if(i!=j && i < j)
{
w[i][j] = p[j] + q[j] + w[i][j-1];
 min = 30000;
for(k = i+1; k <= j; k++)
{
min1 = c[i][k-1] + c[k][j] + w[i][j];
if(min > min1)
{
min = min1;
temp = k;
}
}
c[i][j] = min;
r[i][j] = temp;
}
printf("W[%d][%d]: %d\tC[%d][%d]: %d\tR[%d][%d]: %d\n",i,j,w[i]
[j],i,j,c[i][j],i,j,r[i][j]);
}
printf("\n");
}
printf("Minimum cost = %d\n",c[0][n]);
root = r[0][n];
printf("Root = %d \n",root);
}

OUTPUT:
Enter the number of elements:4

Enter the Element of 1:3

Enter the Element of 2:3
Enter the Element of 3:1
Enter the Element of 4:1

Enter the Probability of 0:2

Enter the Probability of 1:3
Enter the Probability of 2:1
Enter the Probability of 3:1
Enter the Probability of 4:1
W C R
W[0][0]: 2 C[0][0]: 0 R[0][0]: 0
W[1][1]: 3 C[1][1]: 0 R[1][1]: 0
W[2][2]: 1 C[2][2]: 0 R[2][2]: 0
W[3][3]: 1 C[3][3]: 0 R[3][3]: 0
W[4][4]: 1 C[4][4]: 0 R[4][4]: 0

W[0][1]: 8 C[0][1]: 8 R[0][1]: 1

W[1][2]: 7 C[1][2]: 7 R[1][2]: 2
W[2][3]: 3 C[2][3]: 3 R[2][3]: 3
W[3][4]: 3 C[3][4]: 3 R[3][4]: 4
W[0][2]: 12 C[0][2]: 19 R[0][2]: 1
W[1][3]: 9 C[1][3]: 12 R[1][3]: 2
W[2][4]: 5 C[2][4]: 8 R[2][4]: 3

W[0][3]: 14 C[0][3]: 25 R[0][3]: 2

W[1][4]: 11 C[1][4]: 19 R[1][4]: 2

W[0][4]: 16 C[0][4]: 32 R[0][4]: 2

Minimum cost = 32
Root = 2
//IMPLEMENTATION OF HAMILTONIAN CYCLES
#include<stdio.h>
int NODE=5;
int graph[10][10];
int path[20];

void takeInput(){
int i,j;
printf("Enter the elements of the graph: \n");
scanf("%d",&NODE);
printf("Enter the adjacency matrix of graph:\n");
for(i = 0; i < NODE; i++){
for(j = 0; j < NODE; j++){
scanf("%d", &graph[i][j]);
}
}
}

void displayCycle() {
printf("Cycle: ");

for (int i = 0; i < NODE; i++)

printf("%d ", path[i]);
printf("%d\n", path[0]); //print the first vertex again
}

int isValid(int v, int k) {

if (graph [path[k-1]][v] == 0) //if there is no edge
return 0;

for (int i = 0; i < k; i++) //if vertex is already taken, skip that
if (path[i] == v)
return 0;
return 1;
}

int cycleFound(int k) {
if (k == NODE) { //when all vertices are in the path
if (graph[path[k-1]][ path[0] ] == 1 )
return 1;
else
return 0;
}

for (int v = 0; v < NODE; v++) { //for all vertices except starting point
if (isValid(v,k)) { //if possible to add v in the path
path[k] = v;
 if (cycleFound (k+1) == 1) {
displayCycle();
}
path[k] = -1; //when k vertex will not in the solution
}
}
return 0;
}

int hamiltonianCycle() {
for (int i = 0; i < NODE; i++)
path[i] = -1;
path[0] = 0; //first vertex as 0

if ( cycleFound(1) == 0 ) {
printf("No more solutions exist!\n");
return 0;
}

return 1;
}

int main() {
takeInput();
hamiltonianCycle();
}

OUTPUT:

Enter the elements of the graph:

4
Enter the adjacency matrix of graph:
0101
1010
0101
1010
Cycle: 0 1 2 3 0
Cycle: 0 3 2 1 0
No more solutions exist!
//IMPLEMENTATION OF NQUEEN PROBLEM
#include <stdbool.h>
#include <stdio.h>
int N;

/* A utility function to print solution */

void printSolution(int board[N][N])
{
// for (int i = 0; i < N; i++) {
// for (int j = 0; j < N; j++)
// printf(" %d ", board[i][j]);
// printf("\n");
// }
// printf("\n");
int index_arr[N];
for (int i = 0; i < N; i++) {
index_arr[i] = -1;
for (int j = 0; j < N; j++) {
if(board[i][j] == 1)
index_arr[i] = j+1;
}
}
for (int i = 0; i < N; i++)
printf(" %d ", index_arr[i]);
printf("\n");
printf("\n");
}

bool isSafe(int board[N][N], int row, int col)

{
int i, j;

for (i = 0; i < col; i++)

if (board[row][i])
return false;

for (i = row, j = col; i >= 0 && j >= 0; i--, j--)

if (board[i][j])
return false;

for (i = row, j = col; j >= 0 && i < N; i++, j--)

if (board[i][j])
return false;

return true;
}
bool solveNQUtil(int board[N][N], int col)
{
if (col >= N) {
printSolution(board);
return false;
}

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

if (isSafe(board, i, col)) {
board[i][col] = 1;
if (solveNQUtil(board, col + 1))
return true;
board[i][col] = 0;
}
}
return false;
}

bool solveNQ()
{
/* Declare the board and initialize all elements with 0's */
int board[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
board[i][j] = 0;
}

if (!solveNQUtil(board, 0)) {
printf("Solution does not exist");
return false;
}

return true;
}

int main()
{
printf("Number of queens:");
scanf("%d",&N);
solveNQ();
return 0;
}
OUTPUT:
Number of queens:5
1 4 2 5 3
1 3 5 2 4

3 1 4 2 5

4 1 3 5 2

2 4 1 3 5

5 3 1 4 2

2 5 3 1 4

5 2 4 1 3

4 2 5 3 1

3 5 2 4 1