// bfs program
#include <stdio.h>
int a[20][20],q[20],visited[20],n,i,j,f=0,r=-1;
void bfs(int v)
{
visited[v]=1;
printf("%d\t",v);
while(1)
{
for(i=1;i<=n;i++)
{
if(a[v][i]!=0 && visited[i]==0)
{
visited[i]=1;
q[++r]=i;
}
}
if(f>r)
break;
v=q[f++];
printf("%d\t",v);
}
}
int main()
{
int v;
printf("\n Enter the number of vertices:");
scanf("%d",&n);
printf("\n Enter graph data in matrix form:\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
for(i=1;i<=n;i++)
visited[i]=0;
printf("\n Enter the starting vertex:");
scanf("%d",&v);
printf("\n The nodes which are reachable are:\n");
bfs(v);
}
Output:
Enter the number of vertices:5
Enter graph data in matrix form:
01100
10010
10011
01101
00110
Enter the starting vertex:1
The nodes which are reachable are:
1 2 3 4 5
//dfs
#include<stdio.h>
int a[20][20],reach[20],n;
void dfs(int v)
{
int i; reach[v]=1;
for(i=1;i<=n;i++)
if(a[v][i] && !reach[i])
{
printf("\n %d->%d",v,i); dfs(i);
}
}
void main()
{
int i,j,count=0;
printf("\n Enter number of vertices:"); scanf("%d",&n);
for(i=1;i<=n;i++)
{
reach[i]=0;
for(j=1;j<=n;j++)
a[i][j]=0;
}
printf("\n Enter the adjacency matrix:\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
dfs(1);
printf("\n");
for(i=1;i<=n;i++)
{
if(reach[i])
count++;
}
if(count==n)
printf("\n Graph is connected");
else
printf("\n Graph is NOT connected");
}
Output:
Enter number of vertices:5
Enter the adjacency matrix:
01100
10010
10011
01101
00110
1->2
2->4
4->3
3->5
Graph is connected
//mergesort
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void Merge(int a[], int low, int mid, int high) {
int i = low, j = mid + 1, k = 0;
int temp[high - low + 1];
while (i <= mid && j <= high) {
if (a[i] < a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
while (i <= mid)
temp[k++] = a[i++];
while (j <= high)
temp[k++] = a[j++];
for (i = low, k = 0; i <= high; i++, k++)
a[i] = temp[k];
}
void MergeSort(int a[], int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
MergeSort(a, low, mid);
MergeSort(a, mid + 1, high);
Merge(a, low, mid, high);
}
}
int main() {
int n, a[100];
clock_t st, et;
double ts;
srand(time(0));
printf("\nEnter how many numbers: ");
scanf("%d", &n);
printf("\nThe Random Numbers are:\n");
for (int k = 0; k < n; k++) {
a[k] = rand() % (100 - 50 + 1) + 50;
printf("%d\t", a[k]);
}
st = clock();
for (int k = 0; k < 10000; k++)
MergeSort(a, 0, n - 1);
et = clock();
ts = (double)(et - st) / CLOCKS_PER_SEC / 10000;
printf("\n\nSorted Numbers are:\n");
for (int k = 0; k < n; k++)
printf("%d\t", a[k]);
printf("\n\nAverage Time Taken: %e sec\n", ts);
return 0;
}
Output:
Enter how many numbers: 8
The Random Numbers are:
95 100 74 72 53 66 89 75
Sorted Numbers are:
53 66 72 74 75 89 95 100
Average Time Taken: 2.652000e-07 sec
//quicksort
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void Exch(int *p, int *q) {
int temp = *p;
*p = *q;
*q = temp;
}
int partition(int a[], int low, int high) {
int pivot = a[low];
int i = low + 1;
int j = high;
while (1) {
while (i <= high && a[i] <= pivot)
i++;
while (a[j] > pivot)
j--;
if (i < j)
Exch(&a[i], &a[j]);
else
break;
}
Exch(&a[low], &a[j]);
return j;
}
void QuickSort(int a[], int low, int high) {
if (low < high) {
int p = partition(a, low, high);
QuickSort(a, low, p - 1);
QuickSort(a, p + 1, high);
}
}
int main() {
int n, a[100];
clock_t st, et;
double ts;
srand(time(0));
printf("\nEnter how many numbers: ");
scanf("%d", &n);
printf("\nThe Random Numbers are:\n");
for (int k = 0; k < n; k++) {
a[k] = rand() % (100 - 50 + 1) + 50;
printf("%d\t", a[k]);
}
st = clock();
for (int k = 0; k < 10000; k++)
QuickSort(a, 0, n - 1);
et = clock();
ts = (double)(et - st) / CLOCKS_PER_SEC / 10000;
printf("\n\nSorted Numbers are:\n");
for (int k = 0; k < n; k++)
printf("%d\t", a[k]);
printf("\n\nAverage Time Taken: %e sec\n", ts);
return 0;
}
0utput:
Enter how many numbers: 8
The Random Numbers are:
81 83 84 61 71 50 74 50
Sorted Numbers are:
50 50 61 71 74 81 83 84
Average Time Taken: 1.297000e-07 sec
//travelling sales man using bruteforce
#include<stdio.h>
int main()
{
int a[5][5];
printf("enter cost adjacency matrix of a graph with 4 vertices\n");
for(int i=1;i<5;i++)
{ for(int j=1;j<5;j++)
{ scanf("%d",&a[i][j]);
}
}
int temp[6][5]={{1,2,3,4,1},{1,2,4,3,1},{1,3,2,4,1},{1,3,4,2,1},{1,4,3,2,1},{1,4,2,3,1}};
int mincost=100000;
int minr=0;
for(int i=0;i<6;i++)
{
int cost=0,flag=1;
for(int j=0;j<4;j++)
{
if(a[temp[i][j]][temp[i][j+1]]!=0)
{
cost=cost+a[temp[i][j]][temp[i][j+1]];
}
else
{
flag=0;
break;
}
}
if(flag)
{
if(mincost>cost)
{
mincost=cost;
minr=i;
}
}
}
printf("Minimum cost path: ");
for(int i=0;i<5;i++)
{
printf("->% d",temp[minr][i]);
}
printf("\nMinimum cost: %d\n",mincost);
return 0;
}
Output:
enter cost adjacency matrix of a graph with 4 vertices
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0
Minimum cost path: -> 1-> 2-> 4-> 3-> 1
Minimum cost: 80
//knapsack using bruteforce
#include<stdio.h>
#include<math.h>
int knapsack(float p[],float w[],float Capacity,int n)
{
int bestChoice[20],A[20],i,k;
float bestWeight,bestValue,tempWeight,tempValue;
for(i=1 ;i<=pow(2,n) ;i++)
{ int j=n-1;
float tempWeight= 0 ,tempValue = 0 ;
while ( A[j] != 0 && j > 0)
{
A[j] = 0;
j=j-1;
}
A[j] = 1 ;
for ( k=0;k<n;k++)
{
if (A[k] == 1)
{
tempWeight=tempWeight+w[k] ; ;
tempValue = tempValue + p[k];
}
}
if ((tempValue > bestValue) && (tempWeight<=Capacity))
{
bestValue = tempValue;
bestWeight =tempWeight;
for(k;k>=0;k--)
bestChoice[k] = A[k];
}
}
printf("solution vector:\n{");
for(i=0;i<n;i++)
{
printf(" %d, ",bestChoice[i]);
}
printf("}");
return bestValue;
}
int main()
{
float weight[20], profit[20], capacity,bestprofit;
int n, i, j,k;
printf("\nEnter the no. of objects:- ");
scanf("%d", &n);
printf("\nEnter the weights of %d objects :-\n",n);
for (i = 0; i < n; i++)
scanf("%f", &weight[i]);
printf("\nEnter the profits of %d objects :-\n",n);
for (i = 0; i < n; i++)
scanf("%f", &profit[i]);
printf("\nEnter the capacityacity of knapsack:- ");
scanf("%f", &capacity);
bestprofit=knapsack(profit,weight,capacity,n);
printf(" \nProfit : %f\n",bestprofit);
return 0;
}
Output:
Enter the no. of objects:- 3
Enter the weights of 3 objects :-
234
Enter the profits of 3 objects :-
345
Enter the capacityacity of knapsack:- 5
solution vector:
{ 1, 1, 0, }
Profit : 7.000000
//knapsack using greedy method
# include<stdio.h>
void knapsack(int n, float weight[], float profit[], float capacity)
{
float x[20], tp = 0;
int i, j;
float u;
u = capacity;
for (i = 0; i < n; i++)
x[i] = 0.0;
for (i = 0; i < n; i++)
{
if (weight[i] > u)
break;
else
{
x[i] = 1.0;
tp = tp + profit[i];
u = u - weight[i];
}
if (i < n)
x[i] =( u / weight[i]);
tp = tp + (x[i] * profit[i]);
printf("\nThe result vector is:- ");
for (i = 0; i < n; i++)
printf("%f\t", x[i]);
printf("\nMaximum profit is:- %f", tp);
int main()
{
float weight[20], profit[20], capacity;
int num, i, j;
float ratio[20], temp;
printf("\nEnter the no. of objects:- ");
scanf("%d", &num);
printf("\nEnter the weights of %d objects :- ",num);
for (i = 0; i < num; i++)
scanf("%f", &weight[i]);
printf("\nEnter the profits of %d objects :- ",num);
for (i = 0; i < num; i++)
scanf("%f", &profit[i]);
printf("\nEnter the capacityacity of knapsack:- ");
scanf("%f", &capacity);
for (i = 0; i < num; i++)
ratio[i] = profit[i] / weight[i];
for (i = 0; i < num; i++)
{
for (j = 0; j < num-i-1; j++)
{
if (ratio[j] < ratio[j+1])
{
temp = ratio[j];
ratio[j] = ratio[j+1];
ratio[j+1] = temp;
temp = weight[j];
weight[j] = weight[j+1];
weight[j+1] = temp;
temp = profit[j];
profit[j] = profit[j+1];
profit[j+1] = temp;
}
}
}
/* printf("\n weights of %d objects :- ",num);
for (i = 0; i < num; i++)
printf("%f\t", weight[i]);
printf("\nProfits of %d objects :- ",num);
for (i = 0; i < num; i++)
printf("%f\t", profit[i]);*/
knapsack(num, weight, profit, capacity);
return(0);
}
Output:
//minimumcost spanning trees
//prims algorithms
#include<stdio.h>
int a,b,u,v,n,i,j,ne=1;
int visited[10]={0},min,mincost=0,cost[10][10];
void main()
{
printf("\n Enter the number of nodes:");
scanf("%d",&n);
printf("\n Enter the 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]=999;
}
visited[1]=1;
printf("\n");
while(ne<n)
{
for(i=1,min=999;i<=n;i++)
for(j=1;j<=n;j++)
if(cost[i][j]<min)
if(visited[i]!=0)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
if(visited[u]==0 || visited[v]==0)
{
printf("\n Edge %d:(%d %d) cost:%d",ne++,a,b,min);
mincost+=min;
visited[b]=1;
}
cost[a][b]=cost[b][a]=999;
}
printf("\n Minimun cost=%d",mincost);
}
Output:
//kruskals algorithm
#include<stdio.h>
#include<stdlib.h>
int i,j,k,a,b,u,v,n,ne=1;
int min,mincost=0,cost[9][9],parent[9];
int find(int);
int uni(int,int);
void main()
{
printf("\n\n\tImplementation of Kruskal's algorithm\n\n");
printf("\nEnter the no. of vertices\n");
scanf("%d",&n);
printf("\nEnter 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]=999;
}
}
printf("\nThe edges of Minimum Cost Spanning Tree are\n\n");
while(ne<n)
{
for(i=1,min=999;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))
{
printf("\n%d edge (%d,%d) =%d\n",ne++,a,b,min);
mincost +=min;
}
cost[a][b]=cost[b][a]=999;
}
printf("\n\tMinimum cost = %d\n",mincost);
}
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;
}
Output:
//singlesource shortestpath
#include<stdio.h>
#define infinity 999
void dijkstra(int n,int v,int cost[10][10],int dist[100])
{
int i,u,count,w,flag[10],min;
for(i=1;i<=n;i++)
flag[i]=0,dist[i]=cost[v][i];
count=2;
while(count<=n)
{
min=99;
for(w=1;w<=n;w++)
if(dist[w]<min && !flag[w])
min=dist[w],u=w;
flag[u]=1;
count++;
for(w=1;w<=n ;w++)
if((dist[u]+cost[u][w]<dist[w]) && !flag[w])
dist[w]=dist[u]+cost[u][w];
}
}
void main()
{
int n,v,i,j,cost[10][10],dist[10];
printf("\n Enter the number of nodes:");
scanf("%d",&n);
printf("\n Enter the cost 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]=infinity;
}
printf("\n Enter the source Vertex:");
scanf("%d",&v);
dijkstra(n,v,cost,dist);
printf("\n Shortest path:\n");
for(i=1;i<=n;i++)
if(i!=v)
printf("%d->%d,cost=%d\n",v,i,dist[i]);
}
Output: