INDIRA GANDHI DELHI TECHNICAL UNIVERSITY FOR WOMEN

(Establishes by Government of Delhi vide Act 9 of 2012)

(Formerly Indira Gandhi institute of Technology)

LAB FILE
Design Analysis and Algorithm

B.TECH AI-ML
(2023-2027)

Submitted To: Submitted By:

Ms. Nidhi Arora Sugandh
06701192023
 INDEX

S.No. Lab Name Teacher’s Sign

 LAB 1

Objective : Write a program to implement Bubble Sort , Insertion Sort , Quick Sort ,
Merge Sort and Heap Sort

Bubble Sort

Algorithm :

Step 1 : Start by taking an array of size n as input . Initialize an outer loop that iterates from the first element to the second-last
element.
Step 2 : For each pass, create an inner loop that iterates from the first element to the unsorted portion of the array.
Step 3 : In the inner loop, compare each element with its adjacent element.
Step 4 : If the current element is greater than the next element, swap them.
Step 5 : Repeat this process until the largest unsorted element moves to its correct position at the end of the array.
Step 6 :Continue the passes until the entire array is sorted.

Code :
#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n) {

bool swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
swapped = true;
}
}
if (!swapped)
break;
}
}

int main() {
int n;
cout << "Enter the size of the array: ";
cin >> n;
int arr[n];
cout << "Enter the elements: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
bubbleSort(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
Insertion Sort

Algorithm :

Step 1 : Start with an array of size n.Consider the first element as sorted.
Step 2 : Pick the next element and compare it with the elements in the sorted portion.
Step 3 :Shift the larger elements one position to the right.
Step 4 : Insert the current element at its correct position.
Step 5 : Repeat the process until all elements are sorted.

Code :

#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {

for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;

while (j >= 0 && arr[j] > key) {

arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}

int main() {
int n;
cout << "Enter size of array: ";
cin >> n;

int arr[n];
cout << "Enter elements: ";
for (int i = 0; i < n; i++) cin >> arr[i];

insertionSort(arr, n);

cout << "Sorted array: ";

for (int i = 0; i < n; i++) cout << arr[i] << " ";

return 0;
}

Quick Sort
Algorithm :

Step 1 : Select a pivot element from the array

Step 2 : Rearrange the elements so that all smaller elements appear before the pivot and all larger elements after it.
Step 3 : Recursively apply the same process to the sub-arrays on both sides of the pivot.
Step 4 : Continue until the entire array is sorted.

Code :
#include <iostream>
using namespace std;

int partition(int arr[], int low, int high) {

int pivot = arr[high];
int i = low - 1;

for (int j = low; j < high; 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);
}
}

int main() {
int n;
cout << "Enter size of array: ";
cin >> n;
int arr[n];
cout << "Enter elements: ";
for (int i = 0; i < n; i++) cin >> arr[i];
quickSort(arr, 0, n - 1);
cout << "Quick Sorted array: ";
for (int i = 0; i < n; i++) cout << arr[i] << " ";
return 0;
}

Merge Sort

Algorithm :

Step 1 : Divide the array into two halves recursively until each part contains only one element.
Step 2 : Merge the two sorted halves by comparing elements and placing them in the correct order.
Step 3 : Repeat this process until the entire array is merged and sorted.

Code :
#include <iostream>
using namespace std;

void merge(int arr[], int l, int m, int r) {

int n1 = m - l + 1;
int n2 = r - m;

int L[n1], R[n2];

for (int i = 0; i < n1; i++) L[i] = arr[l + i];

for (int i = 0; i < n2; i++) R[i] = arr[m + 1 + i];

int i = 0, j = 0, k = l;

while (i < n1 && j < n2) {

if (L[i] <= R[j]) arr[k++] = L[i++];
else arr[k++] = 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 n;
cout << "Enter size of array: ";
cin >> n;
int arr[n];
cout << "Enter elements: ";
for (int i = 0; i < n; i++) cin >> arr[i];
mergeSort(arr, 0, n - 1);
cout << "Merge Sorted array: ";
for (int i = 0; i < n; i++) cout << arr[i] << " ";
return 0;
}

Heap Sort

Algorithm :
Step 1 : Build a max heap from the given array.
Step 2 :Extract the largest element (root) and place it at the end of the array.
Step 3 : Reduce the heap size and repeat the heapify process.
Step 4 : Continue extracting and placing the largest element until the heap size reduces to one.

Code :
#include <iostream>
using namespace std;

void heapify(int arr[], int n, int i) {

int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;

if (left < n && arr[left] > arr[largest])

largest = left;

if (right < n && arr[right] > arr[largest])

largest = right;

if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}

void heapSort(int arr[], int n) {

for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);

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

swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}

int main() {
int n;
cout << "Enter size of array: ";
cin >> n;
int arr[n];
cout << "Enter elements: ";
for (int i = 0; i < n; i++) cin >> arr[i];
heapSort(arr, n);
cout << "Heap Sorted array: ";
for (int i = 0; i < n; i++) cout << arr[i] << " ";
return 0;
}
 LAB 2

Objective : Write a program to implement Binary Search , Linear Search , BFS ,DFS and
N X N matrix multiplication -Strassens.

Binary Search

Algorithm :

Step 1 : Start with the middle element of the array.

Step 2 : If the element is equal to the target, return the index.
Step 3 : If the element is smaller than the target, ignore the left half.
Step 4 : If the element is larger than the target, ignore the right half.
Step 5 : Repeat the process until the target is found or the array is exhausted.

Code :

#include <iostream>
using namespace std;

int binarySearch(int arr[], int size, int target) {

int left = 0, right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return mid;

if (arr[mid] < target)

left = mid + 1;

else
right = mid - 1;
}

return -1;
}

int main() {
int arr[] = {2, 4, 7, 10, 15, 20, 25};
int size = sizeof(arr) / sizeof(arr[0]);
int target = 10;

int result = binarySearch(arr, size, target);

if (result != -1)
cout << "Element found at index " << result << endl;
else
cout << "Element not found!" << endl;

return 0;
}
Linear Search

Algorithm :

Step 1 : Start from the first element of the list.

Step 2 : Compare each element with the target.
Step 3 : If the target is found, return the index.
Step 4 : If the target is not found after checking all elements, return -1.

Code :

#include <iostream>
using namespace std;
int linearSearch(int arr[], int size, int target) {
for (int i = 0; i < size; i++) {
if (arr[i] == target)
return i;
}
return -1;
}

int main() {
int arr[] = {2, 4, 7, 10, 15, 20, 25};
int size = sizeof(arr) / sizeof(arr[0]);
int target = 20;

int result = linearSearch(arr, size, target);

if (result != -1)
cout << "Element found at index " << result << endl;
else
cout << "Element not found!" << endl;

return 0;
}

BFS: Breadth First Search

Algorithm :

Step 1 : Start at the source node and enqueue it.

Step 2 : While the queue is not empty repeat step 3 and 4
Step 3 : Dequeue the front node.
Step 4 : Visit the node and enqueue all its unvisited neighbors.
Step 5 :Repeat this process until all nodes are visited.

Code :

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
class Graph {
public:
int vertices;
vector<vector<int>> adjList;

Graph(int V) {
vertices = V;
adjList.resize(V);
}

void addEdge(int u, int v) {

adjList[u].push_back(v);
adjList[v].push_back(u); // For undirected graph
}

void BFS(int start) {

vector<bool> visited(vertices, false);
queue<int> q;

visited[start] = true;
q.push(start);

while (!q.empty()) {
int node = q.front();
cout << node << " ";
q.pop();

for (int neighbor : adjList[node]) {

if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
cout << endl;
}
};

int main() {
Graph g(6); // Create a graph with 6 vertices
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 5);

cout << "BFS starting from vertex 0: ";

g.BFS(0);

return 0;
}
DFS: Depth First Search

Algorithm :

Step 1 : Create a visited array to keep track of visited nodes.

Step 2 : Choose a starting node and mark it as visited.
Step 3 : Use a stack or recursion to visit the adjacent nodes.
Step 4 : For each adjacent node: repeat step 5.
Step 5 : If it is not visited, mark it as visited and perform DFS on it.
Step 6 : All reachable nodes from the starting node are visited.

Code :
#include <iostream>
#include <vector>
using namespace std;

void dfs(int node, vector<int> adj[], vector<bool> &visited) {

cout << node << " ";
visited[node] = true;

for (int neighbor : adj[node]) {

if (!visited[neighbor]) {
dfs(neighbor, adj, visited);
}
}
}

int main() {
int vertices, edges;
cout << "Enter number of vertices and edges: ";
cin >> vertices >> edges;

vector<int> adj[vertices + 1];

vector<bool> visited(vertices + 1, false);

cout << "Enter edges (u v):" << endl;

for (int i = 0; i < edges; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}

cout << "DFS traversal: ";

for (int i = 1; i <= vertices; ++i) {
if (!visited[i]) {
dfs(i, adj, visited);
}
}

return 0;
}
N X N Matrix Multiplication Strassens

Algorithm :

Step 1 : Divide matrices A and B in 4 sub-matrices of size N/2 x N/2 as shown in the below diagram.
Step 2 : Calculate following values recursively. ae + bg, af + bh, ce + dg and cf + dh

Code :
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> addMatrix(const vector<vector<int>> &A, const vector<vector<int>> &B, int n) {

vector<vector<int>> result(n, vector<int>(n));
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
result[i][j] = A[i][j] + B[i][j];
return result;
}

vector<vector<int>> subtractMatrix(const vector<vector<int>> &A, const vector<vector<int>> &B, int n) {

vector<vector<int>> result(n, vector<int>(n));
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
result[i][j] = A[i][j] - B[i][j];
return result;
}

vector<vector<int>> strassen(const vector<vector<int>> &A, const vector<vector<int>> &B, int n) {

if (n == 1) {
return {{A[0][0] * B[0][0]}};
}

int newSize = n / 2;
vector<vector<int>> A11(newSize, vector<int>(newSize));
vector<vector<int>> A12(newSize, vector<int>(newSize));
vector<vector<int>> A21(newSize, vector<int>(newSize));
vector<vector<int>> A22(newSize, vector<int>(newSize));

vector<vector<int>> B11(newSize, vector<int>(newSize));

 vector<vector<int>> B12(newSize, vector<int>(newSize));
vector<vector<int>> B21(newSize, vector<int>(newSize));
vector<vector<int>> B22(newSize, vector<int>(newSize));

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

for (int j = 0; j < newSize; ++j) {
A11[i][j] = A[i][j];
A12[i][j] = A[i][j + newSize];
A21[i][j] = A[i + newSize][j];
A22[i][j] = A[i + newSize][j + newSize];

B11[i][j] = B[i][j];
B12[i][j] = B[i][j + newSize];
B21[i][j] = B[i + newSize][j];
B22[i][j] = B[i + newSize][j + newSize];
}
}

vector<vector<int>> M1 = strassen(addMatrix(A11, A22, newSize), addMatrix(B11, B22, newSize), newSize);

vector<vector<int>> M2 = strassen(addMatrix(A21, A22, newSize), B11, newSize);
vector<vector<int>> M3 = strassen(A11, subtractMatrix(B12, B22, newSize), newSize);
vector<vector<int>> M4 = strassen(A22, subtractMatrix(B21, B11, newSize), newSize);
vector<vector<int>> M5 = strassen(addMatrix(A11, A12, newSize), B22, newSize);
vector<vector<int>> M6 = strassen(subtractMatrix(A21, A11, newSize), addMatrix(B11, B12, newSize), newSize);
vector<vector<int>> M7 = strassen(subtractMatrix(A12, A22, newSize), addMatrix(B21, B22, newSize), newSize);

vector<vector<int>> C(n, vector<int>(n));

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

for (int j = 0; j < newSize; ++j) {
C[i][j] = M1[i][j] + M4[i][j] - M5[i][j] + M7[i][j];
C[i][j + newSize] = M3[i][j] + M5[i][j];
C[i + newSize][j] = M2[i][j] + M4[i][j];
C[i + newSize][j + newSize] = M1[i][j] - M2[i][j] + M3[i][j] + M6[i][j];
}
}

return C;
}

int main() {
int n;
cout << "Enter the size of the matrix (n x n): ";
cin >> n;

vector<vector<int>> A(n, vector<int>(n));

vector<vector<int>> B(n, vector<int>(n));

cout << "Enter elements of matrix A:" << endl;

for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
cin >> A[i][j];

cout << "Enter elements of matrix B:" << endl;

for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
cin >> B[i][j];

vector<vector<int>> C = strassen(A, B, n);

cout << "Resultant Matrix (A x B):" << endl;

for (const auto &row : C) {
for (int val : row)
 cout << val << " ";
cout << endl;
}

return 0;
}
 LAB 3

Objective : Write a program to implement Knapsack , Job Sequencing , Activity Selection

and Huffman .

Knapsack

Algorithm :

Step 1 : Create a DP table of size (n+1) x (W+1).

Step 2 : Fill the table based on step 3 and 4.
Step 3 : If item weight > current capacity, exclude the item.
Step 4 : Otherwise, take the max of including or excluding the item.
Step 5 : Return the last cell value as the answer.

Code :
#include <iostream>
using namespace std;

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 n, W;
cout << "Enter number of items: ";
cin >> n;
cout << "Enter capacity of knapsack: ";
cin >> W;

int wt[n], val[n];

cout << "Enter weight and value of items:\n";
for (int i = 0; i < n; i++)
cin >> wt[i] >> val[i];

cout << "Maximum profit: " << knapsack(W, wt, val, n) << endl;
return 0;
}
Job Sequencing

Algorithm :

Step 1 : Take a list of n jobs, each with a deadline and profit.

Step 2 : Sort the jobs in decreasing order of profit.
Step 3 : Create an array to store the job schedule.
Step 4 : For each job, find a free slot (from its deadline to earlier slots).
Step 5 : Place the job in the latest available slot.
Step 6 : Add the job's profit to the total profit.

Code :
#include <iostream>
#include <algorithm>
using namespace std;

struct Job {
char id;
int deadline, profit;
};

bool compare(Job a, Job b) {

return a.profit > b.profit;
}

void jobSequencing(Job jobs[], int n) {

sort(jobs, jobs + n, compare);

int maxDeadline = 0;
for (int i = 0; i < n; i++)
maxDeadline = max(maxDeadline, jobs[i].deadline);

char result[maxDeadline];
bool slot[maxDeadline] = {false};

int maxProfit = 0;

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

for (int j = min(maxDeadline, jobs[i].deadline) - 1; j >= 0; j--) {
if (!slot[j]) {
result[j] = jobs[i].id;
maxProfit += jobs[i].profit;
slot[j] = true;
break;
}
}
}

cout << "Job sequence: ";

for (int i = 0; i < maxDeadline; i++) {
if (slot[i])
cout << result[i] << " ";
}
 cout << "\nMaximum Profit: " << maxProfit << endl;
}

int main() {
int n;
cout << "Enter number of jobs: ";
cin >> n;

Job jobs[n];
cout << "Enter job ID, deadline, and profit:\n";
for (int i = 0; i < n; i++)
cin >> jobs[i].id >> jobs[i].deadline >> jobs[i].profit;

jobSequencing(jobs, n);
return 0;
}

Activity Selection

Algorithm :

Step 1 : Take a list of n activities, each with a start and end time.
Step 2 : Sort the activities based on their finishing time.
Step 3 : Select the first activity.
Step 4 : For the remaining activities,Select the activity only if its start time is greater than or equal to the end time of the last
selected activity.
Step 5 : Continue step 4 until no more activities can be selected.

Code :
#include <iostream>
#include <algorithm>
using namespace std;

struct Activity {
int start, finish;
};

bool compare(Activity a, Activity b) {

return a.finish < b.finish;
}

void activitySelection(Activity activities[], int n) {

sort(activities, activities + n, compare);

int count = 1;
int lastFinishTime = activities[0].finish;
 cout << "Selected activities: " << "(" << activities[0].start << ", " << activities[0].finish << ") ";

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

if (activities[i].start >= lastFinishTime) {
cout << "(" << activities[i].start << ", " << activities[i].finish << ") ";
lastFinishTime = activities[i].finish;
count++;
}
}

cout << "\nMaximum number of activities: " << count << endl;
}

int main() {
int n;
cout << "Enter number of activities: ";
cin >> n;

Activity activities[n];
cout << "Enter start and finish time of activities:\n";
for (int i = 0; i < n; i++)
cin >> activities[i].start >> activities[i].finish;

activitySelection(activities, n);
return 0;
}

Huffman

Algorithm :

Step 1 : Take a list of characters and their frequencies.

Step 2 : Create a min-heap and insert all the characters with their frequencies.
Step 3 : Extract two nodes with the smallest frequency.
Step 4 : Create a new internal node with the combined frequency of the two nodes
Step 5 : Insert the new node back into the min-heap.
Step 6 : Repeat step 4 and 5 until only one node remains (root of the Huffman Tree).
Step 7 : Assign binary codes to each character by traversing the tree.

Code :
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct Node {
char ch;
int freq;
Node *left, *right;
 Node(char ch, int freq) : ch(ch), freq(freq), left(nullptr), right(nullptr) {}
};

struct Compare {
bool operator()(Node* l, Node* r) {
return l->freq > r->freq;
}
};

void printHuffmanCodes(Node* root, string str) {

if (!root) return;

if (root->ch != '$') cout << root->ch << ": " << str << endl;

printHuffmanCodes(root->left, str + "0");

printHuffmanCodes(root->right, str + "1");
}

void huffmanCoding(char ch[], int freq[], int n) {

priority_queue<Node*, vector<Node*>, Compare> minHeap;

for (int i = 0; i < n; i++) minHeap.push(new Node(ch[i], freq[i]));

while (minHeap.size() > 1) {

Node* left = minHeap.top(); minHeap.pop();
Node* right = minHeap.top(); minHeap.pop();

Node* merged = new Node('$', left->freq + right->freq);

merged->left = left;
merged->right = right;

minHeap.push(merged);
}

printHuffmanCodes(minHeap.top(), "");
}

int main() {
int n;
cout << "Enter number of characters: ";
cin >> n;

char ch[n];
int freq[n];

cout << "Enter characters and frequencies:\n";

for (int i = 0; i < n; i++)
cin >> ch[i] >> freq[i];

huffmanCoding(ch, freq, n);

return 0;
}
 LAB 4

Objective : Write a program to implement Prisms , Krushkal and Dijkstra.

Prims

Algorithm :

Step 1 : Start with an arbitrary vertex as the starting node.

Step 2 : Initialize a minimum spanning tree (MST) with this vertex.
Step 3 : Select the edge with the smallest weight that connects a vertex in the MST to a vertex outside the MST.
Step 4 : Add this edge and the new vertex to the MST.
Step 5 : Repeat steps 3 and 4 until all vertices are included in the MST.

Code :

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

#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] && key[v] < min)
min = key[v], min_index = v;
return min_index;
}

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

cout << "Edge\tWeight\n";
for (int i = 1; i < V; i++)
cout << parent[i] << " - " << i << "\t" << graph[i][parent[i]] << endl;
}

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] && 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;
}

Krushkal

Algorithm :

Step 1 : Sort all the edges in ascending order of their weights.

Step 2 : Initialize an empty MST and set the number of edges in MST to 0.
Step 3 : Pick the smallest edge.
Step 4 : Check if adding this edge forms a cycle. If not, add it to the MST.
Step 5 : Repeat steps 3 and 4 until the MST contains V−1 edges (where V is the number of vertices).

Code :
#include <iostream>
#include <algorithm>
using namespace std;

struct Edge {
int src, dest, weight;
};

struct Graph {
int V, E;
Edge* edge;
};

Graph* createGraph(int V, int E) {

Graph* graph = new Graph;
graph->V = V;
graph->E = E;
graph->edge = new Edge[E];
return graph;
}

struct subset {
int parent;
int rank;
};

int find(subset subsets[], int i) {

if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);
return subsets[i].parent;
}

void Union(subset subsets[], int x, int y) {

int rootX = find(subsets, x);
int rootY = find(subsets, y);

if (subsets[rootX].rank < subsets[rootY].rank)

subsets[rootX].parent = rootY;
else if (subsets[rootX].rank > subsets[rootY].rank)
subsets[rootY].parent = rootX;
else {
subsets[rootY].parent = rootX;
subsets[rootX].rank++;
}
}

bool compare(Edge e1, Edge e2) {

return e1.weight < e2.weight;
}

void KruskalMST(Graph* graph) {

int V = graph->V;
Edge result[V];
int e = 0, i = 0;

sort(graph->edge, graph->edge + graph->E, compare);

subset* subsets = new subset[(V * sizeof(subset))];

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

subsets[v].parent = v;
subsets[v].rank = 0;
}

while (e < V - 1 && i < graph->E) {

Edge nextEdge = graph->edge[i++];

int x = find(subsets, nextEdge.src);

int y = find(subsets, nextEdge.dest);

if (x != y) {
result[e++] = nextEdge;
Union(subsets, x, y);
}
}

cout << "Edge\tWeight\n";

for (i = 0; i < e; i++)
cout << result[i].src << " - " << result[i].dest << "\t" << result[i].weight << endl;
}

int main() {
int V = 4, E = 5;
Graph* graph = createGraph(V, E);

graph->edge[0] = {0, 1, 10};

graph->edge[1] = {0, 2, 6};
 graph->edge[2] = {0, 3, 5};
graph->edge[3] = {1, 3, 15};
graph->edge[4] = {2, 3, 4};

KruskalMST(graph);

return 0;
}

Dijkstra

Algorithm :

Step 1 : Initialize distances from the source to all vertices as infinity, except the source itself (0).
Step 2 : Create a visited set to keep track of processed vertices.
Step 3 : Select the vertex with the minimum distance and mark it as visited.
Step 4 : For each neighboring vertex, update its distance if a shorter path is found.
Step 5 : Repeat steps 3 and 4 until all vertices are processed.

Code :
#include <iostream>
#include <climits>
using namespace std;

#define V 6

int minDistance(int dist[], bool visited[]) {

int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (!visited[v] && dist[v] < min)
min = dist[v], min_index = v;
return min_index;
}

void printSolution(int dist[]) {

cout << "Vertex\tDistance from Source\n";
for (int i = 0; i < V; i++)
cout << i << "\t" << dist[i] << endl;
}

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

int dist[V];
bool visited[V];

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

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

dist[src] = 0;

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

int u = minDistance(dist, visited);
visited[u] = true;
 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];
}

printSolution(dist);
}

int main() {
int graph[V][V] = {
{0, 10, 0, 0, 15, 0},
{10, 0, 20, 0, 0, 30},
{0, 20, 0, 25, 0, 0},
{0, 0, 25, 0, 35, 0},
{15, 0, 0, 35, 0, 40},
{0, 30, 0, 0, 40, 0}
};

dijkstra(graph, 0);

return 0;
}