1.

Kruskal:

#include <stdio.h>

int i, j, k, a, b, u, v, n, ne = 1;
int min, mincost = 0;

int find(int i, int parent[]) {

while (parent[i] != 0)
i = parent[i];
return i;
}

int uni(int i, int j, int parent[]) {

if (i != j) {
parent[j] = i;
return 1;
}
return 0;
}

int main() {
int cost[10][10];
int parent[10];

printf("Implementation of Kruskal's algorithm\n");

printf("Enter the number of vertices: ");
scanf("%d", &n);

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

parent[i] = 0;

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("The edges of Minimum Cost Spanning Tree are:\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, parent);
v = find(v, parent);
if (uni(u, v, parent) == 1) {
printf("Edge (%d, %d) = %d\n", a, b, min);
ne++;
mincost += min;
}
cost[a][b] = cost[b][a] = 999;
}

printf("Minimum cost = %d\n", mincost);

return 0;
}

2. Prims

#include <stdio.h>

int n, i, j, ne = 1;
int a, b, u, v;

int main() {
int visited[10];
int cost[10][10];
int min, mincost = 0;

printf("\n Enter the number of nodes: ");

scanf("%d", &n);

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

visited[i] = 0;

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;
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];
a = u = i;
b = v = j;
}
}
}
}
if (visited[u] == 0 || visited[v] == 0) {
printf(" Edge %d: %d,%d cost: %d\n", ne, u, v, min);
ne++;
mincost += min;
visited[b] = 1;
}
cost[a][b] = cost[b][a] = 999;
}
printf(" Minimum cost = %d\n", mincost);

return 0;
}

3a.Floyds

#include <stdio.h>
#include <limits.h>

#define MAX 10

void floyds(int cost[MAX][MAX], int n) {

int i, j, k;
for (k = 0; k < n; k++)
 for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (i == j)
cost[i][j] = 0;
else
cost[i][j] = (cost[i][j] < (cost[i][k] + cost[k][j])) ? cost[i][j] : (cost[i][k] + cost[k][j]);
}

int main() {
int cost[MAX][MAX];
int n, i, j;

printf("Enter the number of vertices: ");

scanf("%d", &n);

printf("Enter the cost matrix:\n");

for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
scanf("%d", &cost[i][j]);

floyds(cost, n);

printf("Transitive closure for the given cost matrix is:\n");

for (i = 0; i < n; i++) {
for (j = 0; j < n; j++)
printf("\t%d", cost[i][j]);
printf("\n");
}

return 0;
}

3b. Warshall's

#include <stdio.h>

#define MAX 10

void warshall(int graph[MAX][MAX], int n) {

int i, j, k;
int transitiveClosure[MAX][MAX];
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
 transitiveClosure[i][j] = graph[i][j];

for (k = 0; k < n; k++) {

for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
transitiveClosure[i][j] = transitiveClosure[i][j] || (transitiveClosure[i][k] &&
transitiveClosure[k][j]);
}
}
}

printf("Transitive closure of the given graph:\n");

for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
printf("%d ", transitiveClosure[i][j]);
}
printf("\n");
}
}

int main() {
int n, i, j;
int graph[MAX][MAX];

printf("Enter the number of vertices: ");

scanf("%d", &n);

printf("Enter the adjacency matrix:\n");

for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
scanf("%d", &graph[i][j]);
}
}

warshall(graph, n);

return 0;
}
4. Dijkstra's

#include <stdio.h>
#define MAX 20
#define INFINITY 9999

int n;
int cost[MAX][MAX];
int distance[MAX];
int visited[MAX];

void readMatrix() {
printf("Enter the number of vertices: ");
scanf("%d", &n);
printf("Enter the cost adjacency matrix:\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &cost[i][j]);
if (cost[i][j] == 0) {
cost[i][j] = INFINITY;
}
}
}
}

int extractMin() {
int min = INFINITY, minIndex = -1;
for (int i = 0; i < n; i++) {
if (!visited[i] && distance[i] < min) {
min = distance[i];
minIndex = i;
}
}
return minIndex;
}

void dijkstra(int startVertex) {

for (int i = 0; i < n; i++) {
distance[i] = cost[startVertex][i];
visited[i] = 0;
}
distance[startVertex] = 0;
visited[startVertex] = 1;
 for (int count = 1; count < n; count++) {
int u = extractMin();
visited[u] = 1;

for (int v = 0; v < n; v++) {

if (!visited[v] && distance[u] + cost[u][v] < distance[v]) {
distance[v] = distance[u] + cost[u][v];
}
}
}

printf("Vertex\tDistance from Source\n");

for (int i = 0; i < n; i++) {
printf("%d\t%d\n", i, distance[i]);
}
}

int main() {
readMatrix();
int startVertex;
printf("Enter starting vertex: ");
scanf("%d", &startVertex);
dijkstra(startVertex);
return 0;
}

5.Topological

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

// Adjacency list node

struct AdjListNode {
int dest;
struct AdjListNode* next;
};

// Adjacency list
struct AdjList {
struct AdjListNode *head;
};
// Graph structure
struct Graph {
int V;
struct AdjList* array;
};

// Create a new adjacency list node

struct AdjListNode* newAdjListNode(int dest) {
struct AdjListNode* newNode = (struct AdjListNode*) malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}

// Create a graph of V vertices

struct Graph* createGraph(int V) {
struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
graph->V = V;

graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));

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

graph->array[i].head = NULL;

return graph;
}

// Add an edge to a directed graph

void addEdge(struct Graph* graph, int src, int dest) {
struct AdjListNode* newNode = newAdjListNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
}

// A recursive function to perform DFS and push vertices to stack

void topologicalSortUtil(int v, int visited[], int stack, int *stackIndex, struct Graph graph) {
visited[v] = 1;
struct AdjListNode* node = graph->array[v].head;

while (node != NULL) {

if (!visited[node->dest])
topologicalSortUtil(node->dest, visited, stack, stackIndex, graph);
node = node->next;
}
 stack[*stackIndex] = v;
(*stackIndex)++;
}

// The function to perform Topological Sort

void topologicalSort(struct Graph* graph) {
int stack[MAX];
int stackIndex = 0;
int visited[MAX] = {0};

for (int i = 0; i < graph->V; i++) {

if (visited[i] == 0) {
topologicalSortUtil(i, visited, stack, &stackIndex, graph);
}
}

for (int i = stackIndex - 1; i >= 0; i--) {

printf("%d ", stack[i]);
}
}

int main() {
int V = 6; // Number of vertices
struct Graph* graph = createGraph(V);
addEdge(graph, 5, 2);
addEdge(graph, 5, 0);
addEdge(graph, 4, 0);
addEdge(graph, 4, 1);
addEdge(graph, 2, 3);
addEdge(graph, 3, 1);

printf("Topological sorting of the given graph is: \n");

topologicalSort(graph);

return 0;
}

6. 0/1 Knapsack

#include <stdio.h>

int max(int a, int b) {

 return (a > b) ? a : b;
}

int main() {
int p[20], w[20], v[20][20];
int i, j, n, W;

printf("Enter the number of items: ");

scanf("%d", &n);

for (i = 1; i <= n; i++) {

printf("Enter the weight and profit of item %d: ", i);
scanf("%d %d", &w[i], &p[i]);
}

printf("\nEnter the capacity of the knapsack: ");

scanf("%d", &W);

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

v[i][0] = 0;
}
for (j = 0; j <= W; j++) {
v[0][j] = 0;
}

for (i = 1; i <= n; i++) {

for (j = 1; j <= W; j++) {
if (w[i] > j) {
v[i][j] = v[i - 1][j];
} else {
v[i][j] = max(v[i - 1][j], v[i - 1][j - w[i]] + p[i]);
}
}
}

printf("The maximum profit is %d\n", v[n][W]);

printf("\nThe items selected are:\n");

j = W;
for (i = n; i >= 1; i--) {
if (v[i][j] != v[i - 1][j]) {
printf("\tItem: %d\n", i);
j = j - w[i];
}
 }

return 0;
}

7. Knapsack Greedy

#include <stdio.h>

#define MAX 20

typedef struct {
float w; // weight
float p; // profit
float r; // profit/weight ratio
} KObject;

int n;
float M;

void ReadObjects(KObject obj[]) {

KObject temp;
printf("Enter the max capacity of knapsack: ");
scanf("%f", &M);
printf("Enter Weights: ");
for (int i = 0; i < n; i++) {
scanf("%f", &obj[i].w);
}
printf("Enter Profits: ");
for (int i = 0; i < n; i++) {
scanf("%f", &obj[i].p);
}
for (int i = 0; i < n; i++) {
obj[i].r = obj[i].p / obj[i].w;
}
// sort objects in descending order, based on p/w ratio
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (obj[j].r < obj[j + 1].r) {
temp = obj[j];
obj[j] = obj[j + 1];
obj[j + 1] = temp;
}
}
 }
}

void Knapsack(KObject kobj[]) {

float x[MAX] = {0}; // solution vector
float totalProfit = 0;
float U = M; // remaining capacity
int i;
for (i = 0; i < n; i++) {
if (kobj[i].w > U) {
break;
} else {
x[i] = 1;
totalProfit += kobj[i].p;
U -= kobj[i].w;
}
}
if (i < n) {
x[i] = U / kobj[i].w;
totalProfit += x[i] * kobj[i].p;
}
printf("The Solution vector, x[]: ");
for (i = 0; i < n; i++) {
printf("%f ", x[i]);
}
printf("\nTotal profit is = %f\n", totalProfit);
}

int main() {
printf("Enter number of objects: ");
scanf("%d", &n);
KObject obj[n];
ReadObjects(obj);
Knapsack(obj);
return 0;
}

8. Subset

#include <stdio.h>

#define MAX 10

int d;
int s[MAX];
int x[MAX];

void sumOfSub(int m, int k, int r, int n) {

x[k] = 1;
if ((m + s[k]) == d) {
printf("Subset:\n");
for (int i = 1; i <= k; i++) {
if (x[i] == 1) {
printf("\t%d\n", s[i]);
}
}
} else {
if ((m + s[k] + s[k + 1]) <= d && (k + 1 <= n)) {
sumOfSub(m + s[k], k + 1, r - s[k], n);
}
if ((m + r - s[k] >= d) && (m + s[k + 1] <= d) && (k + 1 <= n)) {
x[k] = 0;
sumOfSub(m, k + 1, r - s[k], n);
}
}
}

int main() {
int n, sum = 0;
printf("Enter the size of the set: ");
scanf("%d", &n);

printf("\nEnter the set in increasing order:\n");

for (int i = 1; i <= n; i++) {
scanf("%d", &s[i]);
}

printf("\nEnter the value of d: ");

scanf("%d", &d);

for (int i = 1; i <= n; i++) {

sum += s[i];
}

if (sum < d || s[1] > d) {

printf("No subset possible\n");
} else {
sumOfSub(0, 1, sum, n);
 }

return 0;
}

9. Selection Sort

#include <stdio.h>
void selection_sort(int arr[], int n) {
int i, j, min_index;
for (i = 0; i < n - 1; i++) {
min_index = i;
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[min_index]) {
min_index = j;
}
}
int temp = arr[i];
arr[i] = arr[min_index];
arr[min_index] = temp;
}
}

int main() {
int n;
printf("Enter the number of elements: ");
scanf("%d", &n);
int array[n];
printf("Enter %d numbers:\n", n);
for (int i = 0; i < n; i++) {
scanf("%d", &array[i]);
}
selection_sort(array, n);
printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", array[i]);
}
printf("\n");
return 0;
}
10. Quick Sort

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_SIZE 1000

void input(int a[], int *n) {

printf("Enter the total numbers: ");
scanf("%d", n);
srand(time(NULL));
for (int i = 0; i < *n; i++) {
a[i] = rand() % 1000;
}
}

void display(int a[], int n) {

for (int i = 0; i < n; i++) {
printf("%d ", a[i]);
}
}

void quicksort(int a[], int left, int right);

void sort(int a[], int n) {

quicksort(a, 0, n - 1);
}

void quicksort(int a[], int left, int right) {

if (left < right) {
int pivot = a[left];
int i = left;
int j = right + 1;
do {
do {
i++;
} while (i < right && a[i] < pivot);
do {
j--;
} while (a[j] > pivot);
if (i < j) {
int temp = a[i];
a[i] = a[j];
 a[j] = temp;
}
} while (i < j);
int temp = a[left];
a[left] = a[j];
a[j] = temp;
quicksort(a, left, j - 1);
quicksort(a, j + 1, right);
}
}

int main() {
int a[MAX_SIZE];
int n;
input(a, &n);
printf("Array before sorting\n");
display(a, n);
clock_t startTime = clock();
sort(a, n);
clock_t endTime = clock();
double duration = ((double)(endTime - startTime)) * 1000 / CLOCKS_PER_SEC;
printf("\nArray After sorting\n");
display(a, n);
printf("\nTime for sorting is %.2f milli seconds\n", duration);
return 0;
}

11. Merge Sort

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void mergesort(int arr[], int left, int right);

void merge(int arr[], int left, int mid, int right);
void display(int arr[], int size);

int main() {
int n;
printf("Enter the total numbers: ");
scanf("%d", &n);
int arr[n];
srand(time(NULL));
for (int i = 0; i < n; i++) {
 arr[i] = rand() % 1000;
}
printf("Array before sorting\n");
display(arr, n);

clock_t start = clock();

mergesort(arr, 0, n - 1);
clock_t end = clock();
double duration = ((double) (end - start)) / CLOCKS_PER_SEC * 1000;

printf("\nArray after sorting\n");

display(arr, n);

printf("\nTime for sorting is %.6f milliseconds\n", duration);

return 0;
}

void mergesort(int arr[], int left, int right) {

if (left < right) {
int mid = left + (right - left) / 2;
mergesort(arr, left, mid);
mergesort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}

void merge(int arr[], int left, int mid, int right) {

int temp[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
for (i = left, k = 0; i <= right; i++, k++) {
arr[i] = temp[k];
 }
}

void display(int arr[], int size) {

for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

12. N Queens problem

#include <stdio.h>
#include <stdlib.h>

#define MAX 20

int board[MAX][MAX];

void printSolution(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%c ", board[i][j] ? 'Q' : '.');
}
printf("\n");
}
printf("\n");
}

int isSafe(int row, int col, int n) {

int i, j;
for (i = 0; i < col; i++) {
if (board[row][i]) {
return 0;
}
}
for (i = row, j = col; i >= 0 && j >= 0; i--, j--) {
if (board[i][j]) {
return 0;
}
}
for (i = row, j = col; j >= 0 && i < n; i++, j--) {
if (board[i][j]) {
return 0;
 }
}
return 1;
}

int solveNQUtil(int col, int n) {

if (col >= n) {
printSolution(n);
return 1;
}
int res = 0;
for (int i = 0; i < n; i++) {
if (isSafe(i, col, n)) {
board[i][col] = 1;
res = solveNQUtil(col + 1, n) || res;
board[i][col] = 0;
}
}
return res;
}

void solveNQ(int n) {
if (!solveNQUtil(0, n)) {
printf("Solution does not exist\n");
return;
}
}

int main() {
int n;
printf("Enter the number of queens: ");
scanf("%d", &n);
solveNQ(n);
return 0;
}