Bin Packing Algorithm – First Fit Algorithm

#include <stdio.h>
#include <conio.h>
#define MAX_ITEMS 100
#define MAX_BINS 100
int firstFit(int w[], int n, int cap)
{
int bins = 0;
int space[MAX_BINS];
int i, j, placed;
for(i = 0; i < n; i++)
{
placed = 0;
for(j = 0; j < bins; j++)
{
if(space[j] >= w[i])
{
space[j] = space[j] - w[i];
placed = 1;
break;
}
}
if(placed == 0)
{
space[bins] = cap - w[i];
bins++;
}
}
return bins;
}
int main()
{
int w[MAX_ITEMS], n, cap, i;
printf("Enter the number of items: ");
scanf("%d", &n);
printf("Enter the capacity of each bin: ");
scanf("%d", &cap);
printf("Enter the weights of the items:\n");
for(i = 0; i < n; i++)
{
scanf("%d", &w[i]);
}
printf("Minimum number of bins required: %d", firstFit(w, n, cap));
getch();
return 0;
}
======================================================================
Bin Packing Algorithm – Best Fit Algorithm
#include <stdio.h>
#include <conio.h>
#define MAX_ITEMS 100
#define MAX_BINS 100
int bestFit(int w[], int n, int cap)
{
int bins = 0;
int space[MAX_BINS];
int i, j, best, min;
for(i = 0; i < n; i++)
{
best = -1;
min = cap + 1;
 for(j = 0; j < bins; j++)
{
if(space[j] >= w[i] && space[j] - w[i] < min)
{
best = j;
min = space[j] - w[i];
}
}
if(best != -1)
{
space[best] = space[best] - w[i];
}
else
{
space[bins] = cap - w[i];
bins++;
}
}
return bins;
}
int main()
{
int w[MAX_ITEMS], n, cap, i;
printf("Enter the number of items: ");
scanf("%d", &n);
printf("Enter the capacity of each bin: ");
scanf("%d", &cap);
printf("Enter the weights of the items:\n");
for(i = 0; i < n; i++)
{
scanf("%d", &w[i]);
 }
printf("Minimum number of bins required: %d", bestFit(w, n, cap));
getch();
return 0;
}
======================================================================
Knapsack Problem
#include <stdio.h>
#include <conio.h>
int w[10], p[10], v[10][10], n, i, j, cap, x[10] = {0};
int max(int a, int b)
{
if(a > b)
return a;
else
return b;
}
int knap(int i, int j)
{
int value;
if(v[i][j] < 0)
{
if(j < w[i])
value = knap(i - 1, j);
else
value = max(knap(i - 1, j), p[i] + knap(i - 1, j - w[i]));
v[i][j] = value;
}
return v[i][j];
}
int main()
{
int profit, count = 0;
printf("Enter the number of objects ");
scanf("%d", &n);
printf("Enter the profit and weights of the elements\n");
for(i = 1; i <= n; i++)
{
printf("Enter profit and weight For object no %d :", i);
scanf("%d%d", &p[i], &w[i]);
}
printf("Enter the capacity ");
scanf("%d", &cap);
for(i = 0; i <= n; i++)
{
for(j = 0; j <= cap; j++)
{
if(i == 0 || j == 0)
v[i][j] = 0;
else
v[i][j] = -1;
}
}
profit = knap(n, cap);
i = n;
j = cap;
while(i != 0 && j != 0)
{
if(v[i][j] != v[i - 1][j])
{
x[i] = 1;
j = j - w[i];
 i--;
}
else
i--;
}
printf("object included are\n");
printf("[Link]\tweight\tprofit\n");
for(i = 1; i <= n; i++)
{
if(x[i])
printf("%d\t%d\t%d\n", ++count, w[i], p[i]);
}
printf("Total profit = %d", profit);
getch();
return 0;
}
======================================================================
Travelling Salesman Problem using Dynamic Programming
#include <stdio.h>
#include <conio.h>
int c[100][100], ver, s;
float optimum = 999, sum;
void swap(int v[], int i, int j)
{
int t;
t = v[i];
v[i] = v[j];
v[j] = t;
}
void brute_force(int v[], int n, int i)
{
int j, sum1 = 0, k;
if(i == n)
{
if(v[0] == s)
{
for(j = 0; j < n; j++)
{
printf("%d ", v[j]);
}
sum1 = 0;
for(k = 0; k < n - 1; k++)
{
sum1 = sum1 + c[v[k]][v[k + 1]];
}
sum1 = sum1 + c[v[n - 1]][s];
printf("sum = %d\n", sum1);
if(sum1 < optimum)
{
optimum = sum1;
}
}
}
else
{
for(j = i; j < n; j++)
{
swap(v, i, j);
brute_force(v, n, i + 1);
swap(v, i, j);
}
}
}
void nearest_neighbour(int ver)
{
int min, p, i, j, vis[20], from;
for(i = 1; i <= ver; i++)
{
vis[i] = 0;
}
vis[s] = 1;
from = s;
sum = 0;
for(j = 1; j < ver; j++)
{
min = 999;
for(i = 1; i <= ver; i++)
{
if(vis[i] != 1 && c[from][i] < min && c[from][i] != 0)
{
min = c[from][i];
p = i;
}
}
vis[p] = 1;
from = p;
sum = sum + min;
}
sum = sum + c[from][s];
}
int main()
{
int v[100], i, j;
 printf("Enter n : ");
scanf("%d", &ver);
for(i = 0; i < ver; i++)
{
v[i] = i + 1;
}
printf("Enter cost matrix\n");
for(i = 1; i <= ver; i++)
{
for(j = 1; j <= ver; j++)
{
scanf("%d", &c[i][j]);
}
}
printf("Enter source : ");
scanf("%d", &s);
brute_force(v, ver, 0);
printf("Optimum solution with brute force technique is = %f\n", optimum);
nearest_neighbour(ver);
printf("Solution with nearest neighbour technique is = %f\n", sum);
printf("The approximation value is = %f%%\n", ((sum / optimum) - 1) * 100);
getch();
return 0;
}
======================================================================
Binary Tree Traversal
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
typedef struct treeNode
{
 int data;
struct treeNode *left;
struct treeNode *right;
}treeNode;
treeNode* FindMin(treeNode *node)
{
if(node == NULL)
return NULL;
if(node->left)
return FindMin(node->left);
else
return node;
}
treeNode* insert(treeNode *node, int data)
{
if(node == NULL)
{
treeNode *temp;
temp = (treeNode*)malloc(sizeof(treeNode));
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
if(data > node->data)
node->right = insert(node->right, data);
else if(data < node->data)
node->left = insert(node->left, data);
return node;
}
treeNode* deletion(treeNode *node, int data)
{
treeNode *temp;
if(node == NULL)
{
printf("Element Not Found\n");
return NULL;
}
if(data < node->data)
node->left = deletion(node->left, data);
else if(data > node->data)
node->right = deletion(node->right, data);
else
{
if(node->left && node->right)
{
temp = FindMin(node->right);
node->data = temp->data;
node->right = deletion(node->right, temp->data);
}
else
{
temp = node;
if(node->left == NULL)
node = node->right;
else
node = node->left;
free(temp);
}
}
return node;
}
treeNode* search(treeNode *node, int data)
{
if(node == NULL)
return NULL;
if(data > node->data)
return search(node->right, data);
else if(data < node->data)
return search(node->left, data);
else
return node;
}
void inorder(treeNode *node)
{
if(node != NULL)
{
inorder(node->left);
printf("%d ", node->data);
inorder(node->right);
}
}
void preorder(treeNode *node)
{
if(node != NULL)
{
printf("%d ", node->data);
preorder(node->left);
preorder(node->right);
}
}
void postorder(treeNode *node)
{
 if(node != NULL)
{
postorder(node->left);
postorder(node->right);
printf("%d ", node->data);
}
}
int main()
{
treeNode *t, *root = NULL;
int ch, elt;
do
{
printf("\n ### Binary Search Tree Operations ###");
printf("\n Press 1 - Creation of BST");
printf("\n 2 - Deleting");
printf("\n 3 - Searching");
printf("\n 4 - Traverse in Inorder");
printf("\n 5 - Traverse in Preorder");
printf("\n 6 - Traverse in Postorder");
printf("\n 7 - Exit\n");
printf("\n Enter your choice: ");
scanf("%d", &ch);
switch(ch)
{
case 1:
printf("Enter element to be inserted: ");
scanf("%d", &elt);
root = insert(root, elt);
break;
case 2:
 printf("Enter element to be deleted: ");
scanf("%d", &elt);
root = deletion(root, elt);
break;
case 3:
printf("Enter element to be searched: ");
scanf("%d", &elt);
t = search(root, elt);
if(t == NULL)
printf("Element NOT found\n");
else
printf("Element found: %d\n", t->data);
break;
case 4:
printf("\nBST Traversal in INORDER: ");
inorder(root);
break;
case 5:
printf("\nBST Traversal in PREORDER: ");
preorder(root);
break;
case 6:
printf("\nBST Traversal in POSTORDER: ");
postorder(root);
break;
case 7:
printf("\n\nTerminating\n\n");
break;
default:
printf("\nInvalid Option!!! Try Again!!\n\n");
}
 }while(ch != 7);
getch();
return 0;
}
======================================================================
Graph Traversal Using BFS
#include <stdio.h>
#include <conio.h>
int a[20][20], q[20], visited[20], n, i, j, f = -1, r = 0;
void bfs(int v)
{
q[++r] = v;
visited[v] = 1;
while(f < r)
{
f++;
v = q[f];
for(i = 1; i <= n; i++)
{
if(a[v][i] && !visited[i])
{
visited[i] = 1;
q[++r] = i;
}
}
}
}
int main()
{
int v;
printf("Enter the number of vertices: ");
 scanf("%d", &n);
for(i = 1; i <= n; i++)
{
q[i] = 0;
visited[i] = 0;
}
printf("Enter graph data in matrix form:\n");
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
{
scanf("%d", &a[i][j]);
}
}
printf("Enter the starting vertex: ");
scanf("%d", &v);
bfs(v);
printf("The nodes which are reachable are:\n");
for(i = 1; i <= n; i++)
{
if(visited[i])
printf("%d\t", i);
}
getch();
return 0;
}
======================================================================
Graph Traversal Using DFS
#include <stdio.h>
#include <conio.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);
}
}
}
int main()
{
int i, j, count = 0;
printf("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("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("Graph is connected");
else
printf("Graph is not connected");
getch();
return 0;
}
======================================================================
Dijkestra’s Shortest Path Algorithm
#include <stdio.h>
#include <conio.h>
#define infinity 999
void dij(int n, int v, int cost[20][20], int dist[])
{
int i, u, count, w, flag[20], min;
for(i = 1; i <= n; i++)
{
flag[i] = 0;
dist[i] = cost[v][i];
}
count = 2;
 flag[v] = 1;
while(count <= n)
{
min = infinity;
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];
}
}
}
int main()
{
int n, v, i, j, cost[20][20], dist[20];
printf("Enter the number of nodes: ");
scanf("%d", &n);
printf("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("Enter the source node: ");
scanf("%d", &v);
dij(n, v, cost, dist);
printf("Shortest paths from node %d:\n", v);
for(i = 1; i <= n; i++)
{
if(i != v)
printf("%d -> %d, cost = %d\n", v, i, dist[i]);
}
getch();
return 0;
}
======================================================================
Minimum Spanning Tree Algorithm Using Prims
#include <stdio.h>
#include <conio.h>
int a, b, u, v, n, i, j, ne = 1;
int visited[10] = {0}, min, mincost = 0, cost[10][10];
int main()
{
printf("Enter the number of nodes: ");
scanf("%d", &n);
printf("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)
{
min = 999;
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
{
if(cost[i][j] < min)
{
if(visited[i] != 0)
{
min = cost[i][j];
u = i;
v = j;
}
}
}
}
if(visited[u] == 0 || visited[v] == 0)
{
printf("Edge %d: (%d %d) cost: %d\n", ne++, u, v, min);
mincost += min;
visited[v] = 1;
 }
cost[u][v] = cost[v][u] = 999;
}
printf("Minimum cost = %d", mincost);
getch();
return 0;
}
======================================================================
Minimum spanning tree using krushkals algorithm
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
int i, j, a, b, u, v, n, ne = 1, min, mincost = 0;
int cost[9][9], parent[9];
int find(int);
int uni(int, int);
int main()
{
printf("Implementation of Kruskal's Algorithm\n\n");
printf("Enter the number of vertices: ");
scanf("%d", &n);
printf("Enter the cost adjacency matrix (0 for no path):\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;
}
}
 for(i = 1; i <= n; i++)
parent[i] = 0;
printf("The edges of Minimum Cost Spanning Tree are:\n\n");
while(ne < n)
{
min = 999;
for(i = 1; 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("Edge %d: (%d, %d) = %d\n", ne++, a, b, min);
mincost += min;
}
cost[a][b] = cost[b][a] = 999;
}
printf("Minimum cost = %d\n", mincost);
getch();
return 0;
}
int find(int i)
{
while(parent[i] != 0)
i = parent[i];
return i;
}
int uni(int i, int j)
{
if(i != j)
{
parent[j] = i;
return 1;
}
return 0;
}
======================================================================
Topological Sorting
#include <stdio.h>
#include <conio.h>
int main()
{
int i, j, k, n, a[10][10], indeg[10], flag[10], count = 0;
printf("Enter the no of vertices:\n");
scanf("%d", &n);
printf("Enter the adjacency matrix:\n");
for(i = 0; i < n; i++)
{
printf("Enter row %d\n", i + 1);
for(j = 0; j < n; j++)
{
scanf("%d", &a[i][j]);
 }
}
for(i = 0; i < n; i++)
{
indeg[i] = 0;
flag[i] = 0;
}
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
indeg[j] += a[i][j];
printf("The topological order is: ");
while(count < n)
{
for(k = 0; k < n; k++)
{
if(indeg[k] == 0 && flag[k] == 0)
{
printf("%d ", k + 1);
flag[k] = 1;
for(i = 0; i < n; i++)
{
if(a[k][i] == 1)
indeg[i]--;
}
}
}
count++;
}
getch();
return 0;
}
======================================================================
Network Flow Diagram (cpp file)
#include <iostream>
#include <limits.h>
#include <string.h>
#include <queue>
using namespace std;
#define V 6

bool bfs(int rGraph[V][V], int s, int t, int parent[])

{
bool visited[V];
memset(visited, 0, sizeof(visited));
queue<int> q;
[Link](s);
visited[s] = true;
parent[s] = -1;
while(![Link]())
{
int u = [Link]();
[Link]();
for(int v = 0; v < V; v++)
{
if(!visited[v] && rGraph[u][v] > 0)
{
parent[v] = u;
if(v == t)
return true;
[Link](v);
visited[v] = true;
}
 }
}
return false;
}

int fordFulkerson(int graph[V][V], int s, int t)

{
int u, v;
int rGraph[V][V];
for(u = 0; u < V; u++)
for(v = 0; v < V; v++)
rGraph[u][v] = graph[u][v];

int parent[V];
int max_flow = 0;

while(bfs(rGraph, s, t, parent))
{
int path_flow = INT_MAX;
for(v = t; v != s; v = parent[v])
{
u = parent[v];
path_flow = min(path_flow, rGraph[u][v]);
}

for(v = t; v != s; v = parent[v])
{
u = parent[v];
rGraph[u][v] -= path_flow;
rGraph[v][u] += path_flow;
}
 max_flow += path_flow;
}
return max_flow;
}

int main()
{
int graph[V][V] = { {0, 16, 13, 0, 0, 0},
{0, 0, 10, 12, 0, 0},
{0, 4, 0, 0, 14, 0},
{0, 0, 9, 0, 0, 20},
{0, 0, 0, 7, 0, 4},
{0, 0, 0, 0, 0, 0} };

cout << "The maximum possible flow is " << fordFulkerson(graph, 0, 5) << endl;
return 0;
}