1.

MST Using Kruskals Algorithm

#include <stdio.h>

#include <stdlib.h>

int comparator(const void* p1, const void* p2)

const int(*x)[3] = p1;

const int(*y)[3] = p2;

return (*x)[2] - (*y)[2];

void makeSet(int parent[], int rank[], int n)

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

parent[i] = i;

rank[i] = 0;

int findParent(int parent[], int component)

if (parent[component] == component)

return component;

return parent[component]

= findParent(parent, parent[component]);

void unionSet(int u, int v, int parent[], int rank[], int n)

u = findParent(parent, u);

v = findParent(parent, v);

if (rank[u] < rank[v]) {

parent[u] = v;

else if (rank[u] > rank[v]) {

 parent[v] = u;

else {

parent[v] = u;

rank[u]++;

void kruskalAlgo(int n, int edge[n][3])

qsort(edge, n, sizeof(edge[0]), comparator);

int parent[n];

int rank[n];

makeSet(parent, rank, n);

int minCost = 0;

printf(

"Following are the edges in the constructed MST\n");

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

int v1 = findParent(parent, edge[i][0]);

int v2 = findParent(parent, edge[i][1]);

int wt = edge[i][2];

if (v1 != v2) {

unionSet(v1, v2, parent, rank, n);

minCost += wt;

printf("%d -- %d == %d\n", edge[i][0],

edge[i][1], wt);

printf("Minimum Cost Spanning Tree: %d\n", minCost);

}
int main()

int edge[5][3] = { { 0, 1, 10 },

{ 0, 2, 6 },

{ 0, 3, 5 },

{ 1, 3, 15 },

{ 2, 3, 4 } };

kruskalAlgo(5, edge);

return 0;

2.MST using Prims Algorithm

#include <limits.h>

#include <stdbool.h>

#include <stdio.h>

#define V 5

int minKey(int key[], bool mstSet[])

int min = INT_MAX, min_index;

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

if (mstSet[v] == false && key[v] < min)

min = key[v], min_index = v;

return min_index;

int printMST(int parent[], int graph[V][V])

printf("Edge \tWeight\n");

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

printf("%d - %d \t%d \n", parent[i], i,

graph[i][parent[i]]);

}
void primMST(int graph[V][V])

int parent[V];

int key[V];

bool mstSet[V];

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

key[i] = INT_MAX, mstSet[i] = false;

key[0] = 0;

parent[0] = -1;

for (int count = 0; count < V - 1; count++) {

int u = minKey(key, mstSet);

mstSet[u] = true;

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

if (graph[u][v] && mstSet[v] == false

&& graph[u][v] < key[v])

parent[v] = u, key[v] = graph[u][v];

printMST(parent, graph);

int main()

int graph[V][V] = { { 0, 2, 0, 6, 0 },
 { 2, 0, 3, 8, 5 },

{ 0, 3, 0, 0, 7 },

{ 6, 8, 0, 0, 9 },

{ 0, 5, 7, 9, 0 } };

primMST(graph);

return 0;

3a.Floyds Algorithm

#include <stdio.h>

#define V 4

#define INF 99999

void printSolution(int dist[][V]);

void floydWarshall(int dist[][V])

int i, j, k;

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

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

for (j = 0; j < V; j++) {

if (dist[i][k] + dist[k][j] < dist[i][j])

dist[i][j] = dist[i][k] + dist[k][j];

printSolution(dist);

void printSolution(int dist[][V])

printf(

"The following matrix shows the shortest distances"

" between every pair of vertices \n");

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

 for (int j = 0; j < V; j++) {

if (dist[i][j] == INF)

printf("%7s", "INF");

else

printf("%7d", dist[i][j]);

printf("\n");

int main()

int graph[V][V] = { { 0, 5, INF, 10 },

{ INF, 0, 3, INF },

{ INF, INF, 0, 1 },

{ INF, INF, INF, 0 } };

floydWarshall(graph);

return 0;

3b.Warshalls Using C++

#include<stdio.h>

#define V 4

void printSolution(int reach[][V]);

void transitiveClosure(int graph[][V])

int reach[V][V], i, j, k;

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

for (j = 0; j < V; j++)

reach[i][j] = graph[i][j];

for (k = 0; k < V; k++)

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

for (j = 0; j < V; j++)

reach[i][j] = reach[i][j] ||

(reach[i][k] && reach[k][j]);

 }

printSolution(reach);

void printSolution(int reach[][V])

printf ("Following matrix is transitive");

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

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

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

if(i == j)

printf("1 ");

else

printf ("%d ", reach[i][j]);

printf("\n");

int main()

int graph[V][V] = { {1, 1, 0, 1},

{0, 1, 1, 0},

{0, 0, 1, 1},

{0, 0, 0, 1}

};

transitiveClosure(graph);

return 0;

4.Dijkistras Algorithm

#include <limits.h>

#include <stdbool.h>

#include <stdio.h>
#define V 9

int minDistance(int dist[], bool sptSet[])

int min = INT_MAX, min_index;

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

if (sptSet[v] == false && dist[v] <= min)

min = dist[v], min_index = v;

return min_index;

void printSolution(int dist[])

printf("Vertex \t\t Distance from Source\n");

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

printf("%d \t\t\t\t %d\n", i, dist[i]);

void dijkstra(int graph[V][V], int src)

int dist[V];

bool sptSet[V];

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

dist[i] = INT_MAX, sptSet[i] = false;

dist[src] = 0;

for (int count = 0; count < V - 1; count++) {

int u = minDistance(dist, sptSet);

sptSet[u] = true;

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

if (!sptSet[v] && graph[u][v]

&& dist[u] != INT_MAX

&& dist[u] + graph[u][v] < dist[v])

dist[v] = dist[u] + graph[u][v];

printSolution(dist);
}

int main()

int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },

{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },

{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },

{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },

{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },

{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },

{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },

{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },

{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } };

dijkstra(graph, 0);

return 0;

5. Topological Sort
#include <stdbool.h>

#include <stdio.h>

#include <stdlib.h>

struct Stack {

int data;

struct Stack* next;

};

struct Graph {

int V;

struct List* adj;

};

struct List {

int data;
 struct List* next;

};

struct Stack* createStackNode(int data)

struct Stack* newNode

= (struct Stack*)malloc(sizeof(struct Stack));

newNode->data = data;

newNode->next = NULL;

return newNode;

struct List* createListNode(int data)

struct List* newNode

= (struct List*)malloc(sizeof(struct List));

newNode->data = data;

newNode->next = NULL;

return newNode;

struct Graph* createGraph(int V)

struct Graph* graph

= (struct Graph*)malloc(sizeof(struct Graph));

graph->V = V;

graph->adj

= (struct List*)malloc(V * sizeof(struct List));

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

graph->adj[i].next = NULL;

return graph;

}
void addEdge(struct Graph* graph, int v, int w)

struct List* newNode = createListNode(w);

newNode->next = graph->adj[v].next;

graph->adj[v].next = newNode;

void topologicalSortUtil(struct Graph* graph, int v,

bool visited[],

struct Stack** stack)

visited[v] = true;

struct List* current = graph->adj[v].next;

while (current != NULL) {

int adjacentVertex = current->data;

if (!visited[adjacentVertex]) {

topologicalSortUtil(graph, adjacentVertex,

visited, stack);

current = current->next;

struct Stack* newNode = createStackNode(v);

newNode->next = *stack;

*stack = newNode;

void topologicalSort(struct Graph* graph)

struct Stack* stack = NULL;

bool* visited = (bool*)malloc(graph->V * sizeof(bool));

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

visited[i] = false;

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

if (!visited[i]) {

topologicalSortUtil(graph, i, visited, &stack);

while (stack != NULL) {

printf("%d ", stack->data);

struct Stack* temp = stack;

stack = stack->next;

free(temp);

free(visited);

free(graph->adj);

free(graph);

int main()

struct Graph* g = createGraph(6);

addEdge(g, 5, 2);

addEdge(g, 5, 0);

addEdge(g, 4, 0);

addEdge(g, 4, 1);

addEdge(g, 2, 3);

addEdge(g, 3, 1);
 printf("Topological Sorting Order: ");

topologicalSort(g);

return 0;

6.Knapsack 0/1 using dynamic memory method

#include <stdio.h>

int max(int a, int b) { return (a > b) ? a : b; }

int knapSack(int W, int wt[], int val[], int n)

if (n == 0 || W == 0)

return 0;

if (wt[n - 1] > W)

return knapSack(W, wt, val, n - 1);

else

return max(

val[n - 1]

+ knapSack(W - wt[n - 1], wt, val, n - 1),

knapSack(W, wt, val, n - 1));

int main()

int profit[] = { 60, 100, 120 };

int weight[] = { 10, 20, 30 };

int W = 50;

int n = sizeof(profit) / sizeof(profit[0]);

printf("%d", knapSack(W, weight, profit, n));

return 0;

7. Discrete and continuous knapsack

#include <bits/stdc++.h>

using namespace std;

struct Item {

double ratio;
 int index;

};

bool compare(Item a, Item b) { return a.ratio > b.ratio; }

int knapsack_greedy(int N, int W, vector<int>& values,

vector<int>& weights)

vector<Item> ratios(N);

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

ratios[i].ratio

= static_cast<double>(values[i]) / weights[i];

ratios[i].index = i;

sort(ratios.begin(), ratios.end(), compare);

int total_value = 0;

int total_weight = 0;

for (const auto& item : ratios) {

int index = item.index;

if (total_weight + weights[index] <= W) {

total_value += values[index];

total_weight += weights[index];

return total_value;

int main()

int N = 3;

int W = 4;

vector<int> values = { 1, 2, 3 };

vector<int> weights = { 4, 5, 1 };

int result = knapsack_greedy(N, W, values, weights);

 cout << result << endl;

return 0;

8. Subset of a given set

#include <stdio.h>

#include <stdbool.h>

bool isSubsetSum(int set[], int n, int sum)

if (sum == 0)

return true;

if (n == 0)

return false;

if (set[n - 1] > sum)

return isSubsetSum(set, n - 1, sum);

return isSubsetSum(set, n - 1, sum)

|| isSubsetSum(set, n - 1, sum - set[n - 1]);

int main()

int set[] = { 3, 34, 4, 12, 5, 2 };

int sum = 9;

int n = sizeof(set) / sizeof(set[0]);

if (isSubsetSum(set, n, sum) == true)

printf("Found a subset with given sum");

else

printf("No subset with given sum");

return 0;