Hello! In this blog post, we will discuss one of the frequently asked questions in coding tests using C++, Minimum Spanning Tree. We will use Prim’s algorithm and Kruskal’s algorithm, and we will organize the theory by solving a concrete problem.
Problem Description
Given the following graph, find the minimum spanning tree. Finally, output the sum of the weights of the tree.
Input: 5 7 1 2 3 1 3 4 2 3 2 2 4 6 3 4 1 3 5 5 4 5 2 Output: 6
The structure of the input is as follows:
- First line: number of vertices
Vand number of edgesE - The next
Elines: information about each edge (Vertex1, Vertex2, Weight)
Problem Solving Method
To solve the above problem, we can use Prim’s algorithm and Kruskal’s algorithm. Here, we will solve the problem using Prim’s algorithm. Prim’s algorithm starts from an arbitrary vertex and gradually expands the graph by selecting the edge with the smallest weight.
1. Overview of Prim’s Algorithm
Prim’s algorithm consists of the following steps:
- Select the starting vertex and choose the edge with the minimum weight among the edges connected to it.
- Include the vertex connected by the selected edge.
- Repeat the above steps until all vertices are included.
2. Implementing Prim’s Algorithm in C++
Now, let’s implement Prim’s algorithm in C++. Through this implementation, we will look at the process of solving a real problem.
#include
#include
#include
#include
#include
using namespace std;
const int MAX_V = 100; // Maximum number of vertices
const int INF = 1e9; // Representation of infinity
vector> graph[MAX_V]; // Adjacency list
int key[MAX_V]; // Minimum weight array
bool inMST[MAX_V]; // Inclusion in MST
int prim(int start, int V) {
priority_queue, vector>, greater>> pq;
fill(key, key + V, INF);
fill(inMST, inMST + V, false);
key[start] = 0; // The key value of the starting vertex is 0
pq.push({0, start}); // (Weight, Vertex)
int totalWeight = 0; // Total weight of the minimum spanning tree
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
if (inMST[u]) continue; // If already included in MST
totalWeight += key[u]; // Add the key value of the current vertex to the total weight
inMST[u] = true; // Add to MST
for (auto& edge : graph[u]) {
int v = edge.first;
int weight = edge.second;
// If the current edge is not included in MST and weight is smaller
if (!inMST[v] && weight < key[v]) {
key[v] = weight; // Update minimum weight
pq.push({key[v], v}); // Add to queue
}
}
}
return totalWeight;
}
int main() {
int V, E;
cin >> V >> E;
for (int i = 0; i < E; i++) {
int u, v, weight;
cin >> u >> v >> weight;
// Stored in 0-indexed
graph[u - 1].push_back({v - 1, weight});
graph[v - 1].push_back({u - 1, weight});
}
cout << prim(0, V) << endl; // Starting vertex 0
return 0;
}
3. Code Explanation
The explanation of the above code is as follows:
- The graph is represented using an adjacency list. Each vertex has a list of connected vertices and their weights.
- A priority queue is used to efficiently select the edge with the minimum weight among the edges connected from the current vertex.
- The vertices included in MST are managed by the
inMSTarray. - Finally, it returns the total weight of the MST including all vertices.
4. Execution Example
When executing the input data, the following result is obtained:
5 7
1 2 3
1 3 4
2 3 2
2 4 6
3 4 1
3 5 5
4 5 2
Output result:
6
Finding Minimum Spanning Tree Using Kruskal's Algorithm
Following Prim's algorithm, we will look at how to solve the same problem using Kruskal's algorithm. Kruskal's algorithm operates based on edges, sorting all edges by weight and adding them from the smallest.
1. Overview of Kruskal's Algorithm
Kruskal's algorithm consists of the following steps:
- Sort the edges by weight.
- Select the smallest edge and add it to the MST if it does not create a cycle.
- Repeat until all edges are processed.
2. Implementing Kruskal's Algorithm in C++
Now, let's implement Kruskal's algorithm in C++.
#include
#include
#include
using namespace std;
struct Edge {
int u, v, weight;
};
bool compare(Edge a, Edge b) {
return a.weight < b.weight;
}
int find(int parent[], int u) {
if (parent[u] != u) {
parent[u] = find(parent, parent[u]); // Path compression
}
return parent[u];
}
void unionSet(int parent[], int rank[], int u, int v) {
int root_u = find(parent, u);
int root_v = find(parent, v);
if (root_u != root_v) {
if (rank[root_u] > rank[root_v]) {
parent[root_v] = root_u;
} else if (rank[root_u] < rank[root_v]) {
parent[root_u] = root_v;
} else {
parent[root_v] = root_u;
rank[root_u]++;
}
}
}
int kruskal(int V, vector& edges) {
sort(edges.begin(), edges.end(), compare);
int parent[V], rank[V];
for (int i = 0; i < V; i++) {
parent[i] = i;
rank[i] = 0;
}
int totalWeight = 0; // Total weight of the MST
for (Edge edge : edges) {
int u = edge.u, v = edge.v;
// Add to MST if no cycle is formed
if (find(parent, u) != find(parent, v)) {
unionSet(parent, rank, u, v);
totalWeight += edge.weight; // Add weight
}
}
return totalWeight;
}
int main() {
int V, E;
cin >> V >> E;
vector edges(E);
for (int i = 0; i < E; i++) {
cin >> edges[i].u >> edges[i].v >> edges[i].weight;
edges[i].u--; // 0-indexed
edges[i].v--; // 0-indexed
}
cout << kruskal(V, edges) << endl; // Output the total weight of the MST
return 0;
}
3. Code Explanation
The explanation of the code above is as follows:
- Define a structure
Edgeto store edges. - Sort the edges by weight.
- Utilize the Union-Find data structure to check for cycles and add the edge to the MST if no cycles occur.
4. Execution Example
When executing the input data, the following result is obtained:
5 7
1 2 3
1 3 4
2 3 2
2 4 6
3 4 1
3 5 5
4 5 2
Output result:
6
Conclusion
In this session, we learned how to solve the Minimum Spanning Tree problem using Prim's algorithm and Kruskal's algorithm. Understanding the characteristics of each algorithm and their actual implementation methods is important, and one should familiarize themselves with these algorithms to solve various problems.
The Minimum Spanning Tree problem is one of the basic concepts in graph theory and frequently appears in algorithm problems. Utilize the implementations above to practice solving various graph problems efficiently.
I hope that viewers found this tutorial helpful, and if you have any further questions, please leave a comment. In the next post, we will cover another algorithm problem. Thank you!