C++ Coding Test Course, Finding Minimum Spanning Tree

In this course, we will learn about the Minimum Spanning Tree (MST). A minimum spanning tree is a tree that includes all vertices in a weighted graph while ensuring that the total weight is minimized. Such problems can be applied in various fields and play an important role in network design, road construction, and communication network establishment.

Problem Description

Given a weighted undirected graph as follows, find the minimum spanning tree.

Input:
The first line contains the number of vertices V and the number of edges E. (1 ≤ V ≤ 1000, 1 ≤ E ≤ 10000)
The next E lines each contain the edge information u, v, w. This means that the weight w connects vertex u and vertex v.

Output:
Print the total weight of the minimum spanning tree.

Example Input

3 3
1 2 1
2 3 2
1 3 3

Example Output

3

Solution Method

To solve this problem, we can use Prim’s algorithm or Kruskal’s algorithm. Here, we will use Kruskal’s algorithm for the solution.

Kruskal’s Algorithm Explanation

Kruskal’s algorithm is an edge-based algorithm that proceeds in the following steps:

1. Sort all edges in ascending order of weight.
2. Initialize the vertex set. (Using Union-Find data structure)
3. Select edges one by one, and if the two vertices are not yet connected, choose the edge. Repeat this process to create a minimum spanning tree that connects all vertices.

Code Implementation

Now, let’s implement Kruskal’s algorithm in C++.

#include <iostream>
#include <vector>
#include <algorithm>

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 x) {
    if (parent[x] != x) {
        parent[x] = find(parent, parent[x]);
    }
    return parent[x];
}

void unionSet(int parent[], int rank[], int x, int y) {
    int rootX = find(parent, x);
    int rootY = find(parent, y);

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

int kruskal(int V, vector& edges) {
    sort(edges.begin(), edges.end(), compare);
    int parent[V + 1];
    int rank[V + 1];
    for (int i = 0; i <= V; i++) {
        parent[i] = i;
        rank[i] = 0;
    }

    int totalWeight = 0;
    for (Edge edge : edges) {
        if (find(parent, edge.u) != find(parent, edge.v)) {
            totalWeight += edge.weight;
            unionSet(parent, rank, edge.u, edge.v);
        }
    }
    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;
    }
    cout << kruskal(V, edges) << endl;
    return 0;
}

Code Explanation

First, we define the Edge structure and sort based on weights using a comparison function.

find function uses path compression to efficiently find the parent node. unionSet function merges the sets of two vertices while using rank to prevent the tree from becoming too large.

The main function receives input and calculates the total weight of the minimum spanning tree using Kruskal’s algorithm and then outputs it.

Complexity Analysis

The time complexity of Kruskal’s algorithm is O(E log E). This is the time required for edge sorting. When optimizing Union-Find operations, it operates as a very efficient algorithm.

Conclusion

The minimum spanning tree is used in many real-world problems, so systematically understanding it is important. Through this example, we have learned how to apply Kruskal’s algorithm to find MST and have acquired foundational theories applicable to various modified problems. Additionally, we recommend practicing Prim’s algorithm as well.

The next lecture will cover other algorithms related to the minimum spanning tree or various problem-solving, so stay tuned.