C Code for Knapsack, MST, and Shortest Path Algorithms
1. Fractional Knapsack Problem (Greedy Approach)
This implementation solves the Fractional Knapsack Problem using a Greedy Approach. Items are sorted based on their profit-to-weight ratio to maximize the total profit within the given capacity.
C Implementation
#include <stdio.h>
#include <stdlib.h>
struct Item {
int weight, profit;
float ratio;
};
// Comparison function for qsort: sorts items by ratio in descending order
int compare(const void *a, const void *b) {
struct Item *i1 = (struct Item *)a;
struct Item *i2 = (struct Item *)b;
return (i2->ratio > i1->ratio) - (i2->ratio < i1->ratio);
}
void fractionalKnapsack(int n, int capacity, struct Item items[]) {
for (int i = 0; i < n; i++)
items[i].ratio = (float)items[i].profit / items[i].weight;
qsort(items, n, sizeof(struct Item), compare);
float totalProfit = 0.0;
for (int i = 0; i < n && capacity > 0; i++) {
if (items[i].weight <= capacity) {
totalProfit += items[i].profit;
capacity -= items[i].weight;
} else {
totalProfit += items[i].ratio * capacity;
break;
}
}
printf("Maximum profit: %.2f\n", totalProfit);
}
int main() {
struct Item items[] = {{10, 60}, {20, 100}, {30, 120}};
int n = 3, capacity = 50;
fractionalKnapsack(n, capacity, items);
return 0;
}2. Job Sequencing with Deadlines
This algorithm uses a Greedy Strategy to select jobs that maximize total profit, ensuring each job is completed by its deadline.
C Implementation
#include <stdio.h>
#include <stdlib.h>
struct Job {
char id;
int deadline;
int profit;
};
// Comparison function: sorts jobs by profit in descending order
int compare(const void *a, const void void *b) {
return ((struct Job *)b)->profit - ((struct Job *)a)->profit;
}
// Finds the latest possible time slot available before the deadline
int findSlot(int slots[], int deadline) {
for (int i = deadline - 1; i >= 0; i--) {
if (slots[i] == -1)
return i;
}
return -1;
}
void jobSequencing(struct Job jobs[], int n) {
qsort(jobs, n, sizeof(struct Job), compare);
int maxDeadline = 0;
for (int i = 0; i < n; i++)
if (jobs[i].deadline > maxDeadline)
maxDeadline = jobs[i].deadline;
int slots[maxDeadline];
for (int i = 0; i < maxDeadline; i++) slots[i] = -1;
int totalProfit = 0;
printf("Job sequence: ");
for (int i = 0; i < n; i++) {
int index = findSlot(slots, jobs[i].deadline);
if (index != -1) {
slots[index] = i;
totalProfit += jobs[i].profit;
printf("%c ", jobs[i].id);
}
}
printf("\nTotal Profit: %d\n", totalProfit);
}
int main() {
struct Job jobs[] = {{'a', 2, 100}, {'b', 1, 19}, {'c', 2, 27},
{'d', 1, 25}, {'e', 3, 15}};
int n = 5;
jobSequencing(jobs, n);
return 0;
}3. Kruskal’s Minimum Spanning Tree (MST) Algorithm
Kruskal’s algorithm finds the MST of a connected, undirected graph by selecting edges in increasing order of weight, ensuring no cycles are formed (using the Union-Find data structure).
C Implementation
#include <stdio.h>
#include <stdlib.h>
struct Edge {
int u, v, weight;
};
// Find operation with path compression
int find(int parent[], int i) {
if (parent[i] != i)
parent[i] = find(parent, parent[i]);
return parent[i];
}
// Union operation
void unionSet(int parent[], int x, int y) {
parent[find(parent, x)] = find(parent, y);
}
// Comparison function: sorts edges by weight (ascending)
int compareEdges(const void *a, const void *b) {
return ((struct Edge *)a)->weight - ((struct Edge *)b)->weight;
}
void kruskal(int V, int E, struct Edge edges[]) {
qsort(edges, E, sizeof(struct Edge), compareEdges);
int parent[V];
for (int i = 0; i < V; i++) parent[i] = i;
int totalCost = 0;
printf("Edges in MST:\n");
for (int i = 0; i < E; i++) {
int u = edges[i].u, v = edges[i].v;
if (find(parent, u) != find(parent, v)) {
printf("%d - %d : %d\n", u, v, edges[i].weight);
totalCost += edges[i].weight;
unionSet(parent, u, v);
}
}
printf("Total cost: %d\n", totalCost);
}
int main() {
int V = 4, E = 5;
struct Edge edges[] = {
{0, 1, 10}, {0, 2, 6}, {0, 3, 5},
{1, 3, 15}, {2, 3, 4}};
kruskal(V, E, edges);
return 0;
}4. Prim’s Minimum Spanning Tree (MST) Algorithm
Prim’s algorithm builds the MST by starting from an arbitrary vertex and iteratively adding the cheapest edge that connects a vertex already in the MST to a vertex outside the MST.
C Implementation
#include <stdio.h>
#include <limits.h>
#define V 5
// Utility function to find the vertex with the minimum key value
int minKey(int key[], int mstSet[]) {
int min = INT_MAX, minIndex;
for (int v = 0; v < V; v++)
if (!mstSet[v] && key[v] < min)
min = key[v], minIndex = v;
return minIndex;
}
void prim(int graph[V][V]) {
int parent[V], key[V], mstSet[V];
for (int i = 0; i < V; i++) key[i] = INT_MAX, mstSet[i] = 0;
key[0] = 0, parent[0] = -1;
for (int count = 0; count < V - 1; count++) {
int u = minKey(key, mstSet);
mstSet[u] = 1;
for (int v = 0; v < V; v++)
if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v])
parent[v] = u, key[v] = graph[u][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]]);
}
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}};
prim(graph);
return 0;
}5. Dijkstra’s Shortest Path Algorithm
Dijkstra’s algorithm finds the shortest paths from a single source vertex to all other vertices in a graph with non-negative edge weights.
C Implementation
#include <stdio.h>
#include <limits.h>
#define V 5
// Utility function to find the vertex with minimum distance value
int minDistance(int dist[], int visited[]) {
int min = INT_MAX, minIndex;
for (int v = 0; v < V; v++)
if (!visited[v] && dist[v] < min)
min = dist[v], minIndex = v;
return minIndex;
}
void dijkstra(int graph[V][V], int src) {
int dist[V], visited[V];
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, visited[i] = 0;
dist[src] = 0;
for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, visited);
visited[u] = 1;
for (int v = 0; v < V; v++)
if (!visited[v] && graph[u][v] && dist[u] != INT_MAX
&& dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
printf("Vertex \t Distance 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, 10, 0, 5, 0},
{0, 0, 1, 2, 0},
{0, 0, 0, 0, 4},
{0, 3, 9, 0, 2},
{7, 0, 6, 0, 0}};
dijkstra(graph, 0);
return 0;
}6. Floyd-Warshall All-Pairs Shortest Path Algorithm
The Floyd-Warshall algorithm computes the shortest paths between all pairs of vertices in a weighted graph. It handles both positive and negative edge weights (but no negative cycles).
C Implementation
#include <stdio.h>
#define V 4
#define INF 99999
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];
printf("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;
}