ASSIGNMENT ALGO
Ayesha 22BSCS016
BSCS-5
Jalil
Solution
Kruskal's Algorithm
The inputs taken by the kruskal’s algorithm are the graph G {V, E}, where V is the set of vertices and E is the set of
edges, and the source vertex S and the minimum spanning tree of graph G is obtained as an output.
Algorithm
Sort all the edges in the graph in an ascending order and store it in an array edge[].
Construct the forest of the graph on a plane with all the vertices in it.
Select the least cost edge from the edge[] array and add it into the forest of the graph. Mark the vertices
visited by adding them into the visited[] array.
Repeat the steps 2 and 3 until all the vertices are visited without having any cycles forming in the graph
When all the vertices are visited, the minimum spanning tree is formed.
Calculate the minimum cost of the output spanning tree formed.
Steps of the Algorithm:*
1. *Sort edges* by weight in ascending order.
2. Use the *Union-Find (Disjoint Set Union)* data structure to check for cycles:
- Each vertex starts as its own parent (forming separate sets).
- For each edge, check if its vertices belong to the same set:
- If not, include it in the MST (merge the sets).
- Otherwise, skip the edge (as it would form a cycle).
3. Repeat until the MST contains ( n - 1 ) edges, where ( n ) is the number of vertices.
Time Complexity :The time complexity of Kruskal's algorithm is O(E log E) or O(E log V), where E is the
number of edges and V is the number of vertices.
Space Complexity : The space complexity of Kruskal's algorithm is O(E + V), where E is the number of
edges and V is the number of vertices.
Code:
#include <iostream>
using namespace std;
// DSU data structure
// path compression + rank by union
class DSU {
int* parent;
int* rank;
public:
DSU(int n)
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = -1;
rank[i] = 1;
// Find function
int find(int i)
if (parent[i] == -1)
return i;
return parent[i] = find(parent[i]);
// Union function
void unite(int x, int y)
int s1 = find(x);
int s2 = find(y);
if (s1 != s2) {
if (rank[s1] < rank[s2]) {
parent[s1] = s2;
else if (rank[s1] > rank[s2]) {
parent[s2] = s1;
else {
parent[s2] = s1;
rank[s1] += 1;
};
class Graph {
vector<vector<int> > edgelist;
int V;
public:
Graph(int V) { this->V = V; }
// Function to add edge in a graph
void addEdge(int x, int y, int w)
edgelist.push_back({ w, x, y });
void kruskals_mst()
// Sort all edges
sort(edgelist.begin(), edgelist.end());
// Initialize the DSU
DSU s(V);
int ans = 0;
int count = 0; // To keep track of the number of edges in MST
cout << "Following are the edges in the "
"constructed MST"
<< endl;
for (auto edge : edgelist) {
int w = edge[0];
int x = edge[1];
int y = edge[2];
// Take this edge in MST if it does
// not forms a cycle
if (s.find(x) != s.find(y)) {
s.unite(x, y);
ans += w;
cout << x << " -- " << y << " == " << w
<< endl;
count++; // Increase the count of edges added to MST
}
if (count == V - 1) {
break;
cout << "Minimum Cost Spanning Tree: " << ans;
};
// Driver code
int main()
Graph g(4);
g.addEdge(0, 1, 10);
g.addEdge(1, 3, 15);
g.addEdge(2, 3, 4);
g.addEdge(2, 0, 6);
g.addEdge(0, 3, 5);
// Function call
g.kruskals_mst();
return 0;
}
Explanation of Output:
- The algorithm picks the edges with the smallest weights first, ensuring no cycles are formed- The final
MST consists of:
- ( ('E', 'D', 1) )
- ( ('C', 'E', 2) )
- ( ('A', 'C', 3) )
- ( ('A', 'B', 4) )
- The total weight of the MST is \( 1 + 2 + 3 + 4 = 10 \)
This solution meets all requirements: computing the MST and displaying the edges with their total weight.
