Graph Algorithms and Sorting Algorithms: A Comparative Analysis
Graph Algorithms
1. Kruskal’s Algorithm
Kruskal’s algorithm finds the minimum spanning tree (MST) of a weighted undirected graph. It iteratively adds the edge with the smallest weight to the MST, ensuring that adding the edge doesn’t create a cycle.
#include<stdio.h>
#define INF 999
#define MAX 100
int p[MAX], c[MAX][MAX], t[MAX][2];
int find(int v) {
while (p[v])
v = p[v];
return v;
}
void union1(int i, int j) {
p[j] = i;
}
void kruskal(int n) {
int i, j, k, u, v, min, res1, res2, sum = 0;
for (k = 1; k < n; k++) {
min = INF;
for (i = 1; i < n - 1; i++) {
for (j = 1; j <= n; j++) {
if (i == j) continue;
if (c[i][j] < min) {
u = find(i);
v = find(j);
if (u != v) {
res1 = i;
res2 = j;
min = c[i][j];
}
}
}
}
union1(res1, find(res2));
t[k][1] = res1;
t[k][2] = res2;
sum = sum + min;
}
printf("\nCost of spanning tree is=%d", sum);
printf("\nEdges of spanning tree are:\n");
for (i = 1; i < n; i++)
printf("%d -> %d\n", t[i][1], t[i][2]);
}
int main() {
int i, j, n;
printf("\nEnter the n value:");
scanf("%d", &n);
for (i = 1; i <= n; i++)
p[i] = 0;
printf("\nEnter the graph data:\n");
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
scanf("%d", &c[i][j]);
kruskal(n);
return 0;
}
2. Prim’s Algorithm
Prim’s algorithm is another greedy algorithm for finding the MST of a weighted undirected graph. It starts with a single vertex and iteratively adds the edge with the smallest weight that connects a vertex in the MST to a vertex outside the MST.
#include<stdio.h>
#define INF 999
int prim(int c[10][10], int n, int s) {
int v[10], i, j, sum = 0, ver[10], d[10], min, u;
for (i = 1; i <= n; i++) {
ver[i] = s;
d[i] = c[s][i];
v[i] = 0;
}
v[s] = 1;
for (i = 1; i <= n - 1; i++) {
min = INF;
for (j = 1; j <= n; j++) {
if (v[j] == 0 && d[j] < min) {
min = d[j];
u = j;
}
}
v[u] = 1;
sum = sum + d[u];
printf("\n%d -> %d sum=%d", ver[u], u, sum);
for (j = 1; j <= n; j++) {
if (v[j] == 0 && c[u][j] < d[j]) {
d[j] = c[u][j];
ver[j] = u;
}
}
}
return sum;
}
void main() {
int c[10][10], i, j, res, s, n;
printf("\nEnter n value:");
scanf("%d", &n);
printf("\nEnter the graph data:\n");
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
scanf("%d", &c[i][j]);
printf("\nEnter the source node:");
scanf("%d", &s);
res = prim(c, n, s);
printf("\nCost=%d", res);
}
3. Floyd-Warshall Algorithm
The Floyd-Warshall algorithm finds the shortest paths between all pairs of vertices in a weighted graph. It can handle both positive and negative edge weights but not negative cycles.
3A. Shortest Path Matrix
#include<stdio.h>
#define INF 999
int min(int a, int b) {
return (a < b) ? a : b;
}
void floyd(int p[][10], int n) {
int i, j, k;
for (k = 1; k <= n; k++)
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
p[i][j] = min(p[i][j], p[i][k] + p[k][j]);
}
int main() {
int a[10][10], n, i, j;
printf("\nEnter the n value:");
scanf("%d", &n);
printf("\nEnter the graph data:\n");
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
scanf("%d", &a[i][j]);
floyd(a, n);
printf("\nShortest path matrix\n");
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++)
printf("%d ", a[i][j]);
printf("\n");
}
return 0;
}
3B. Resultant Path Matrix
#include<stdio.h>
void warsh(int p[][10], int n) {
int i, j, k;
for (k = 1; k <= n; k++)
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
p[i][j] = p[i][j] || (p[i][k] && p[k][j]);
}
int main() {
int a[10][10], n, i, j;
printf("\nEnter the n value:");
scanf("%d", &n);
printf("\nEnter the graph data:\n");
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
scanf("%d", &a[i][j]);
warsh(a, n);
printf("\nResultant path matrix\n");
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++)
printf("%d ", a[i][j]);
printf("\n");
}
return 0;
}
4. Dijkstra’s Algorithm
Dijkstra’s algorithm finds the shortest paths from a single source vertex to all other vertices in a weighted graph with non-negative edge weights.
#include<stdio.h>
#define INF 999
void dijkstra(int c[10][10], int n, int s, int d[10]) {
int v[10], min, u, i, j;
for (i = 1; i <= n; i++) {
d[i] = c[s][i];
v[i] = 0;
}
v[s] = 1;
for (i = 1; i <= n; i++) {
min = INF;
for (j = 1; j <= n; j++) {
if (v[j] == 0 && d[j] < min) {
min = d[j];
u = j;
}
}
v[u] = 1;
for (j = 1; j <= n; j++) {
if (v[j] == 0 && (d[u] + c[u][j]) < d[j]) {
d[j] = d[u] + c[u][j];
}
}
}
}
int main() {
int c[10][10], d[10], i, j, s, sum, n;
printf("\nEnter n value:");
scanf("%d", &n);
printf("\nEnter the graph data:\n");
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
scanf("%d", &c[i][j]);
printf("\nEnter the source node:");
scanf("%d", &s);
dijkstra(c, n, s, d);
for (i = 1; i <= n; i++)
printf("\nShortest distance from %d to %d is %d", s, i, d[i]);
return 0;
}
5. Topological Sort
Topological sort is a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge (u, v), vertex u comes before vertex v in the ordering.
#include<stdio.h>
int temp[10], k = 0;
void sort(int a[][10], int id[], int n) {
int i, j;
for (i = 1; i <= n; i++) {
if (id[i] == 0) {
id[i] = -1;
temp[++k] = i;
for (j = 1; j <= n; j++) {
if (a[i][j] == 1 && id[j] != -1) {
id[j]--;
}
}
i = 0;
}
}
}
void main() {
int a[10][10], id[10], n, i, j;
printf("\nEnter the n value:");
scanf("%d", &n);
for (i = 1; i <= n; i++)
id[i] = 0;
printf("\nEnter the graph data:\n");
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++) {
scanf("%d", &a[i][j]);
if (a[i][j] == 1) {
id[j]++;
}
}
sort(a, id, n);
if (k != n) {
printf("\nTopological ordering not possible");
} else {
printf("\nTopological ordering is:");
for (i = 1; i <= k; i++)
printf("%d ", temp[i]);
}
}
Knapsack Problem
6. 0/1 Knapsack Problem (Recursive)
The 0/1 knapsack problem involves finding the most valuable subset of items to include in a knapsack with a maximum weight capacity. Each item can either be fully included or excluded (0/1).
#include<stdio.h>
int w[10], p[10], n;
int max(int a, int b) {
return a > b ? a : b;
}
int knap(int i, int m) {
if (i == n) return w[i] > m ? 0 : p[i];
if (w[i] > m) return knap(i + 1, m);
return max(knap(i + 1, m), knap(i + 1, m - w[i]) + p[i]);
}
int main() {
int m, i, max_profit;
printf("\nEnter the no. of objects:");
scanf("%d", &n);
printf("\nEnter the knapsack capacity:");
scanf("%d", &m);
printf("\nEnter profit followed by weight:\n");
for (i = 1; i <= n; i++)
scanf("%d %d", &p[i], &w[i]);
max_profit = knap(1, m);
printf("\nMax profit=%d", max_profit);
return 0;
}
7. Fractional Knapsack Problem (Greedy)
The fractional knapsack problem is similar to the 0/1 knapsack problem, but items can be partially included in the knapsack.
#include <stdio.h>
#define MAX 50
int p[MAX], w[MAX], x[MAX];
double maxprofit;
int n, m, i;
void greedyKnapsack(int n, int w[], int p[], int m) {
double ratio[MAX];
for (i = 0; i < n; i++) {
ratio[i] = (double)p[i] / w[i];
}
for (i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (ratio[i] < ratio[j]) {
double temp = ratio[i];
ratio[i] = ratio[j];
ratio[j] = temp;
int temp2 = w[i];
w[i] = w[j];
w[j] = temp2;
temp2 = p[i];
p[i] = p[j];
p[j] = temp2;
}
}
}
int currentWeight = 0;
maxprofit = 0.0;
for (i = 0; i < n; i++) {
if (currentWeight + w[i] <= m) {
x[i] = 1;
currentWeight += w[i];
maxprofit += p[i];
} else {
x[i] = (m - currentWeight) / (double)w[i];
maxprofit += x[i] * p[i];
break;
}
}
printf("Optimal solution for greedy method: %.1f\n", maxprofit);
printf("Solution vector for greedy method: ");
for (i = 0; i < n; i++)
printf("%d\t", x[i]);
}
int main() {
printf("Enter the number of objects: ");
scanf("%d", &n);
printf("Enter the objects' weights: ");
for (i = 0; i < n; i++)
scanf("%d", &w[i]);
printf("Enter the objects' profits: ");
for (i = 0; i < n; i++)
scanf("%d", &p[i]);
printf("Enter the maximum capacity: ");
scanf("%d", &m);
greedyKnapsack(n, w, p, m);
return 0;
}
8. Sum of Subsets Problem (Backtracking)
The sum of subsets problem involves finding all possible subsets of a given set of numbers that add up to a target sum.
#include<stdio.h>
#define MAX 10
int s[MAX], x[MAX], d;
void sumofsub(int p, int k, int r) {
int i;
x[k] = 1;
if ((p + s[k]) == d) {
for (i = 1; i <= k; i++)
if (x[i] == 1)
printf("%d ", s[i]);
printf("\n");
} else if (p + s[k] + s[k + 1] <= d) {
sumofsub(p + s[k], k + 1, r - s[k]);
}
if ((p + r - s[k] >= d) && (p + s[k + 1] <= d)) {
x[k] = 0;
sumofsub(p, k + 1, r - s[k]);
}
}
int main() {
int i, n, sum = 0;
printf("\nEnter the n value:");
scanf("%d", &n);
printf("\nEnter the set in increasing order:");
for (i = 1; i <= n; i++)
scanf("%d", &s[i]);
printf("\nEnter the max subset value:");
scanf("%d", &d);
for (i = 1; i <= n; i++)
sum = sum + s[i];
if (sum < d || s[1] > d)
printf("\nNo subset possible");
else
sumofsub(0, 1, sum);
return 0;
}
Sorting Algorithms
9. Selection Sort
Selection sort repeatedly finds the minimum element from the unsorted part of the array and swaps it with the element at the beginning of the unsorted part.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void selectionSort(int arr[], int n) {
int i, j, min_idx;
for (i = 0; i < n - 1; i++) {
min_idx = i;
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
void generateRandomNumbers(int arr[], int n) {
for (int i = 0; i < n; i++) {
arr[i] = rand() % 10000;
}
}
int main() {
int n;
printf("Enter number of elements: ");
scanf("%d", &n);
if (n <= 5000) {
printf("Please enter a value greater than 5000\n");
return 1;
}
int *arr = (int *)malloc(n * sizeof(int));
if (arr == NULL) {
printf("Memory allocation failed\n");
return 1;
}
generateRandomNumbers(arr, n);
clock_t start = clock();
selectionSort(arr, n);
clock_t end = clock();
double time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("Time taken to sort %d elements: %f seconds\n", n, time_taken);
free(arr);
return 0;
}
10. Quick Sort
Quick sort is a divide-and-conquer algorithm that selects a pivot element and partitions the array around the pivot, such that elements smaller than the pivot are placed before it, and elements greater than the pivot are placed after it.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
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);
}
}
void generateRandomNumbers(int arr[], int n) {
for (int i = 0; i < n; i++) {
arr[i] = rand() % 100000;
}
}
int main() {
int n;
printf("Enter number of elements: ");
if (scanf("%d", &n) != 1) {
printf("Invalid input\n");
return 1;
}
if (n <= 5000) {
printf("Please enter a value greater than 5000\n");
return 1;
}
int *arr = (int *)malloc(n * sizeof(int));
if (arr == NULL) {
printf("Memory allocation failed\n");
return 1;
}
srand(time(0));
generateRandomNumbers(arr, n);
clock_t start = clock();
quickSort(arr, 0, n - 1);
clock_t end = clock();
double time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("Time taken to sort %d elements: %f seconds\n", n, time_taken);
free(arr);
return 0;
}
11. Merge Sort
Merge sort is another divide-and-conquer algorithm that recursively divides the array into two halves, sorts each half, and then merges the sorted halves back together.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void merge(int arr[], int left, int mid, int right) {
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;
int *L = (int *)malloc(n1 * sizeof(int));
int *R = (int *)malloc(n2 * sizeof(int));
for (i = 0; i < n1; i++)
L[i] = arr[left + i];
for (j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
i = 0;
j = 0;
k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
free(L);
free(R);
}
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 generateRandomArray(int arr[], int n) {
for (int i = 0; i < n; i++)
arr[i] = rand() % 100000;
}
int main() {
int n;
printf("Enter the number of elements: ");
scanf("%d", &n);
if (n <= 5000) {
printf("Please enter a value greater than 5000\n");
return 1;
}
int *arr = (int *)malloc(n * sizeof(int));
if (arr == NULL) {
printf("Memory allocation failed\n");
return 1;
}
generateRandomArray(arr, n);
clock_t start = clock();
for (int i = 0; i < 1000; i++) {
mergeSort(arr, 0, n - 1);
}
clock_t end = clock();
double time_taken = ((double)(end - start)) / CLOCKS_PER_SEC / 1000.0;
printf("Time taken to sort %d elements: %f seconds\n", n, time_taken);
free(arr);
return 0;
}
Conclusion
This document provided a comparative analysis of various graph and sorting algorithms, including their implementations in C. Each algorithm has its strengths and weaknesses, making them suitable for different scenarios. Understanding their time and space complexities is crucial for selecting the most efficient algorithm for a given problem.