Algorithms: Prim’s, Kruskal’s, Dijkstra’s, Quick Sort, Merge Sort, Knapsack
Posted on Nov 28, 2024 in Computers
Prim’s Algorithm
C Implementation
#include <stdio.h>
#include <limits.h>
#include <stdbool.h>
#define V 5 // Number of vertices
int findMinVertex(int key[], bool 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 primMST(int graph[V][V]) {
int parent[V], key[V];
bool mstSet[V] = {false};
for (int i = 0; i < V; i++)
key[i] = INT_MAX;
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < V - 1; count++) {
int u = findMinVertex(key, mstSet);
mstSet[u] = true;
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}
};
primMST(graph);
return 0;
}
Algorithm Steps
- Initialization:
key[]: Minimum weight edge to MST. Initialized to infinity, except key[0] = 0.parent[]: Parent of each vertex in MST. Initialized to -1.mstSet[]: Tracks vertices in MST. Initialized to false.
- MST Construction:
- Repeat
V-1 times: - Select vertex
u with smallest key[] not in mstSet[]. - Add
u to mstSet[]. - Update
key[] and parent[] of adjacent vertices of u if a shorter path is found.
- Output: Print the MST edges and weights.
Kruskal’s Algorithm
C Implementation
#include <stdio.h>
#include <stdlib.h>
#define V 5 // Number of vertices
#define E 7 // Number of edges
typedef struct {
int u, v, w;
} Edge;
Edge edges[E], mst[V - 1];
int cmp(const void *a, const void *b) {
return ((Edge *)a)->w - ((Edge *)b)->w;
}
int find(int p[], int i) {
return (p[i] == i) ? i : (p[i] = find(p, p[i]));
}
void kruskal() {
int p[V], c = 0;
for (int i = 0; i < V; i++) p[i] = i;
qsort(edges, E, sizeof(Edge), cmp);
for (int i = 0; i < E && c < V - 1; i++) {
int u = find(p, edges[i].u);
int v = find(p, edges[i].v);
if (u != v) {
mst[c++] = edges[i];
p[u] = v;
}
}
printf("Edge \tWeight\n");
for (int i = 0; i < c; i++)
printf("%d - %d \t%d\n", mst[i].u, mst[i].v, mst[i].w);
}
int main() {
edges[0] = (Edge){0, 1, 2};
edges[1] = (Edge){0, 3, 6};
edges[2] = (Edge){1, 3, 8};
edges[3] = (Edge){1, 2, 3};
edges[4] = (Edge){1, 4, 5};
edges[5] = (Edge){2, 4, 7};
edges[6] = (Edge){3, 4, 9};
kruskal();
return 0;
}
Algorithm Steps
- Input: Graph represented as a list of edges with vertices and weights.
- Sort Edges: Sort edges by weight in non-decreasing order.
- Initialize Subsets: Each vertex starts as its own subset (parent of itself).
- Add Edges to MST:
- Iterate through sorted edges.
- If edge connects vertices in different subsets, add it to MST and merge subsets.
- Stop when MST has
V-1 edges.
- Output: Print MST edges and weights.
Dijkstra’s Algorithm
C Implementation
#include <stdio.h>
#include <limits.h>
#include <stdbool.h>
#define V 5 // Number of vertices
#define INF INT_MAX
int findMinDist(int dist[], bool sptSet[]) {
int min = INF, minIndex;
for (int v = 0; v < V; v++)
if (!sptSet[v] && dist[v] <= min) {
min = dist[v];
minIndex = v;
}
return minIndex;
}
void dijkstra(int graph[V][V], int src) {
int dist[V];
bool sptSet[V] = {false};
for (int i = 0; i < V; i++)
dist[i] = INF;
dist[src] = 0;
for (int count = 0; count < V - 1; count++) {
int u = findMinDist(dist, sptSet);
sptSet[u] = true;
for (int v = 0; v < V; v++)
if (!sptSet[v] && graph[u][v] && dist[u] != INF &&
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, 10, 0, 0, 5},
{0, 0, 1, 0, 2},
{0, 0, 0, 4, 0},
{7, 0, 6, 0, 0},
{0, 3, 9, 2, 0}
};
int src = 0;
dijkstra(graph, src);
return 0;
}
Algorithm Steps
- Input: Graph as adjacency matrix, source vertex
src. - Initialization:
dist[]: Shortest distance from src. Initialized to infinity, except dist[src] = 0.sptSet[]: Tracks finalized shortest paths. Initialized to false.
- Shortest Path Calculation:
- Repeat
V-1 times: - Find vertex
u with smallest dist[] not in sptSet[]. - Add
u to sptSet[]. - Update
dist[] of adjacent vertices if a shorter path is found through u.
- Output: Print shortest distances from source to all vertices.
Quick Sort
C Implementation
#include <stdio.h>
#define swap(x, y) { int temp = x; x = y; y = temp; }
int partition(int arr[], int low, int high) {
int pivot = arr[high], i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot)
swap(arr[++i], arr[j]);
}
swap(arr[i + 1], arr[high]);
return i + 1;
}
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);
}
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("Sorted array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
Algorithm Steps
- Input: Array
arr[], indices low and high. - Partition:
- Choose pivot (last element).
- Place elements smaller than pivot before it, and larger elements after it.
- Return pivot’s index.
- Recursion: Recursively sort subarrays before and after pivot.
- Base Case: Subarray with 0 or 1 element is sorted.
- Output: Sorted array.
Merge Sort
C Implementation
#include <stdio.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);
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, n - 1);
printf("Sorted array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
Algorithm Steps
- Input: Array
arr[], indices l and r. - Divide: Divide array into two halves recursively.
- Merge: Merge sorted halves into a single sorted array.
- Base Case: Subarray with one element is sorted.
- Output: Sorted array.
Knapsack Problem
C Implementation
#include <stdio.h>
#define MAX_ITEMS 100
#define MAX_CAPACITY 100
int max(int a, int b) {
return (a > b) ? a : b;
}
int knapSack(int W, int wt[], int val[], int n) {
int dp[n + 1][W + 1];
for (int i = 0; i <= n; ++i) {
for (int w = 0; w <= W; ++w) {
if (i == 0 || w == 0)
dp[i][w] = 0;
else if (wt[i - 1] <= w)
dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);
else
dp[i][w] = dp[i - 1][w];
}
}
return dp[n][W];
}
int main() {
int values[] = {3, 4, 5, 6};
int weight[] = {2, 3, 4, 5};
int W = 8;
int n = sizeof(values) / sizeof(values[0]);
printf("Maximum value that can be put in knapsack: %d\n", knapSack(W, weight, values, n));
return 0;
}
Algorithm Steps
- Input:
values[], weight[], capacity W, number of items n. - Initialize DP Table:
dp[n+1][W+1], base cases dp[0][w] = 0 and dp[i][0] = 0. - Iterate: For each item and weight, calculate maximum value by either including or excluding the item.
- Output:
dp[n][W] contains the maximum knapsack value. - Return: Print the maximum value.
