1.
Kruskal’s algorithm
#include <stdio.h>
#define MAX 100
#define INF 9999
int parent[MAX];
int find(int i) {
while (parent[i])
i = parent[i];
return i;
}
int unionSets(int i, int j) {
int u = find(i), v = find(j);
if (u != v) {
parent[v] = u;
return 1;
}
return 0;
}
int main() {
int cost[MAX][MAX], n, i, j, a, b, u, v, ne = 1, min, mincost = 0;
printf("Enter number 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]),
cost[i][j] = (cost[i][j] == 0) ? INF : cost[i][j];
printf("\nEdges in Minimum Spanning Tree:\n");
while (ne < n) {
min = INF;
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;
if (unionSets(u, v)) {
printf("Edge %d: (%d, %d) cost = %d\n", ne++, a, b, min);
mincost += min;
}
cost[a][b] = cost[b][a] = INF;
}
printf("\nMinimum Cost = %d\n", mincost);
return 0;
}
2.Prim’s algorithm
#include <stdio.h>
#define INF 99999
#define MAX 10
int G[MAX][MAX] = {
{0, 19, 8},
{21, 0, 13},
{15, 18, 0}
};
int S[MAX][MAX], n = 3;
int prims() {
int dist[MAX], from[MAX], visited[MAX] = {1}, min_cost = 0;
int i, j, u, v, min_dist, edges = n - 1;
for (i = 0; i < n; i++) {
dist[i] = G[0][i] ? G[0][i] : INF;
from[i] = 0;
for (j = 0; j < n; j++)
S[i][j] = 0;
}
while (edges--) {
min_dist = INF;
for (i = 1; i < n; i++)
if (!visited[i] && dist[i] < min_dist)
min_dist = dist[v = i];
u = from[v];
S[u][v] = S[v][u] = G[u][v];
min_cost += G[u][v];
visited[v] = 1;
for (i = 1; i < n; i++)
if (!visited[i] && G[v][i] && G[v][i] < dist[i]) {
dist[i] = G[v][i];
from[i] = v;
}
}
return min_cost;
}
int main() {
int i, j, cost = prims();
printf("Spanning tree:\n");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++)
printf("%d\t", S[i][j]);
printf("\n");
}
printf("Minimum cost = %d\n", cost);
return 0;
}
3a.Floyd’s algorithm
#include <stdio.h>
#define V 4
#define INF 9999
void floydWarshall(int graph[V][V]) {
int dist[V][V];
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
dist[i][j] = graph[i][j];
for (int k = 0; k < V; k++)
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
if (dist[i][k] != INF && dist[k][j] != INF &&
dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
if (dist[i][j] == INF)
printf("No path exists between %d and %d\n", i, j);
else
printf("Shortest path from %d to %d is %d\n", i, j, dist[i][j]);
}
int main() {
int graph[V][V] = {
{0, 1, INF, INF},
{INF, 0, 2, INF},
{6, INF, 0, 3},
{3, -5, INF, 0}
};
floydWarshall(graph);
return 0;
}
3b.Warshal’s algorithm
#include <stdio.h>
#define MAX 10
int n;
int adj[MAX][MAX], reach[MAX][MAX];
void warshall() {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
reach[i][j] = adj[i][j];
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (reach[i][k] && reach[k][j])
reach[i][j] = 1;
}
int main() {
printf("Enter number of nodes: ");
scanf("%d", &n);
printf("Enter the adjacency matrix:\n");
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf("%d", &adj[i][j]);
warshall();
printf("\nTransitive Closure Matrix:\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
printf("%d ", reach[i][j]);
printf("\n");
}
return 0;
}
4.Dijkstra’s algorithm
#include <stdio.h>
#include <stdbool.h>
#define V 5
#define INF 99999
int minDistance(int dist[], bool visited[]) {
int min = INF, min_index = -1;
for (int i = 0; i < V; i++)
if (!visited[i] && dist[i] < min)
min = dist[i], min_index = i;
return min_index;
}
void dijkstra(int graph[V][V], int src) {
int dist[V];
bool visited[V];
for (int i = 0; i < V; i++)
dist[i] = INF, visited[i] = false;
dist[src] = 0;
for (int i = 0; i < V - 1; i++) {
int u = minDistance(dist, visited);
visited[u] = true;
for (int v = 0; v < V; v++)
if (!visited[v] && graph[u][v] && dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
printf("Vertex\tDistance from Source\n");
for (int i = 0; i < V; i++)
printf("%d\t%d\n", i, dist[i]);
}
int main() {
int graph[V][V] = {
{0, 9, 6, 5, 3},
{9, 0, 0, 0, 0},
{6, 0, 0, 0, 0},
{5, 0, 0, 0, 0},
{3, 0, 0, 0, 0}
};
dijkstra(graph, 0);
return 0;
}
5.Topological algorithm
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
int adj[MAX][MAX];
int in_degree[MAX];
int n;
void topologicalSort() {
int queue[MAX], front = 0, rear = 0;
int count = 0;
for (int i = 0; i < n; i++) {
if (in_degree[i] == 0)
queue[rear++] = i;
}
printf("Topological Order: ");
while (front < rear) {
int v = queue[front++];
printf("%d ", v);
count++;
for (int i = 0; i < n; i++) {
if (adj[v][i] == 1) {
in_degree[i]--;
if (in_degree[i] == 0)
queue[rear++] = i;
}
}
}
if (count != n) {
printf("\nCycle detected! Topological sorting is not possible.\n");
}
printf("\n");
}
int main() {
int edges, u, v;
printf("Enter number of vertices: ");
scanf("%d", &n);
printf("Enter number of edges: ");
scanf("%d", &edges);
for (int i = 0; i < n; i++) {
in_degree[i] = 0;
for (int j = 0; j < n; j++) {
adj[i][j] = 0;
}
}
printf("Enter edges (u v) where u -> v:\n");
for (int i = 0; i < edges; i++) {
scanf("%d %d", &u, &v);
adj[u][v] = 1;
in_degree[v]++;
}
topologicalSort();
return 0;
}
6. 0/1 Knapsack
#include <stdio.h>
int weight[10], profit[10], n;
int max(int a, int b) {
return (a > b) ? a : b;
}
int knapsack(int capacity) {
int dp[10][20];
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= capacity; w++) {
if (i == 0 || w == 0)
dp[i][w] = 0;
else if (weight[i - 1] <= w)
dp[i][w] = max(dp[i - 1][w], profit[i - 1] + dp[i - 1][w - weight[i - 1]]);
else
dp[i][w] = dp[i - 1][w];
}
}
return dp[n][capacity];
}
int main() {
int capacity, max_profit;
printf("Enter number of items: ");
scanf("%d", &n);
printf("Enter profit and weight of each object:\n");
for (int i = 0; i < n; i++) {
printf("Item %d - Profit and Weight: ", i + 1);
scanf("%d %d", &profit[i], &weight[i]);
}
printf("Enter knapsack capacity: ");
scanf("%d", &capacity);
max_profit = knapsack(capacity);
printf("\nMaximum profit = %d\n", max_profit);
return 0;
}
7.discrete Knapsack
#include<stdio.h>
int main()
{
float weight[50],profit[50],ratio[50],Totalvalue,temp,capacity,amount;
int n,i,j;
printf("Enter the number of items :");
scanf("%d",&n);
for (i = 0; i < n; i++)
{
printf("Enter Weight and Profit for item[%d] :\n",i);
scanf("%f %f", &weight[i], &profit[i]);
}
printf("Enter the capacity of knapsack :\n");
scanf("%f",&capacity);
for(i=0;i<n;i++)
ratio[i]=profit[i]/weight[i];
for (i = 0; i < n; i++)
for (j = i + 1; j < n; j++)
if (ratio[i] < ratio[j])
{
temp = ratio[j];
ratio[j] = ratio[i];
ratio[i] = temp;
temp = weight[j];
weight[j] = weight[i];
weight[i] = temp;
temp = profit[j];
profit[j] = profit[i];
profit[i] = temp;
}
printf("Knapsack problems using Greedy Algorithm:\n");
for (i = 0; i < n; i++)
{
if (weight[i] > capacity)
break;
else
{
Totalvalue = Totalvalue + profit[i];
capacity = capacity - weight[i];
}
}
if (i < n)
Totalvalue = Totalvalue + (ratio[i]*capacity);
printf("\nThe maximum value is :%f\n",Totalvalue);
return 0;
}
8.Subset
#include <stdio.h>
#include <stdbool.h>
int set[100], subset[100];
int n, target;
bool found = false;
void findSubset(int index, int currSum, int subsetSize) {
if (currSum == target) {
found = true;
printf("Subset found: ");
for (int i = 0; i < subsetSize; i++) {
printf("%d ", subset[i]);
}
printf("\n");
return;
}
if (index >= n || currSum > target)
return;
subset[subsetSize] = set[index];
findSubset(index + 1, currSum + set[index], subsetSize + 1);
if (found) return;
findSubset(index + 1, currSum, subsetSize);
}
int main() {
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter the elements: ");
for (int i = 0; i < n; i++) {
scanf("%d", &set[i]);
}
printf("Enter the target sum: ");
scanf("%d", &target);
findSubset(0, 0, 0);
if (!found)
printf("No subset with sum %d found.\n", target);
return 0;
}
9.Selection Sort
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main() {
int a[10000], i, j, temp, num;
clock_t st, et;
printf("Enter the number of elements: ");
scanf("%d", &num);
for (i = 0; i < num; i++) {
a[i] = rand() % 10000;
}
printf("Array before sorting:\n");
for (i = 0; i < num; i++) {
printf("%d\t", a[i]);
}
printf("\n");
st = clock();
for (i = 0; i < num - 1; i++) {
for (j = i + 1; j < num; j++) {
if (a[i] > a[j]) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
et = clock();
printf("Array after sorting:\n");
for (i = 0; i < num; i++) {
printf("a[%d] = %d\n", i, a[i]);
}
double time_taken = ((double)(et - st)) * 1000 / CLOCKS_PER_SEC;
printf("Time taken: %.3f ms\n", time_taken);
return 0;
}
10.Quick Sort
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int partition(int arr[], int low, int high) {
int pivot = arr[low];
int i = low;
for (int j = low + 1; j <= high; j++) {
if (arr[j] <= pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i];
arr[i] = arr[low];
arr[low] = temp;
return i;
}
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 generateRandomNumbers(int arr[], int n) {
for (int i = 0; i < n; i++) {
arr[i] = rand() % 100000;
}
}
int main() {
int n_values[] = {5000, 10000, 20000, 50000, 100000};
int num_tests = sizeof(n_values) / sizeof(n_values[0]);
printf("n\tTime Taken (ms)\n");
for (int i = 0; i < num_tests; i++) {
int n = n_values[i];
int *arr = (int *)malloc(n * sizeof(int));
generateRandomNumbers(arr, n);
clock_t start = clock();
quickSort(arr, 0, n - 1);
clock_t end = clock();
double time_taken_ms = ((double)(end - start)) * 1000 / CLOCKS_PER_SEC;
printf("%d\t%.3f ms\n", n, time_taken_ms);
free(arr);
}
return 0;
}
11.Merge Sort
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1, n2 = r - m;
int L[n1], R[n2];
for (int i = 0; i < n1; i++) L[i] = arr[l + i];
for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
void generateRandomNumbers(int arr[], int n) {
srand(time(NULL));
for (int i = 0; i < n; i++)
arr[i] = rand() % 10000;
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int n;
printf("Enter the number of elements: ");
scanf("%d", &n);
int arr[n];
generateRandomNumbers(arr, n);
printf("\nUnsorted array:\n");
printArray(arr, n);
clock_t start = clock();
mergeSort(arr, 0, n - 1);
clock_t end = clock();
printf("\nSorted array:\n");
printArray(arr, n);
double time_taken = (double)(end - start) / CLOCKS_PER_SEC;
printf("\nTime taken to sort %d elements = %f seconds\n", n,
time_taken);
return 0;
}
12.N Queen’s
#include <stdbool.h>
#include <stdio.h>
#define N 8
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");
}
}
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)
return true;
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() {
int board[N][N] = { {0} };
if (solveNQUtil(board, 0) == false) {
printf("Solution does not exist");
return false;
}
printSolution(board);
return true;
}
int main() {
solveNQ();
return 0;
}
