C++ Coding Test Course, Minimum Spanning Tree

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 V and number of edges E
The next E lines: 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 inMST array.
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:

Output result:

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 Edge to 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:

Output result:

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!

Problem Description

Problem Solving Method

1. Overview of Prim’s Algorithm

2. Implementing Prim’s Algorithm in C++

3. Code Explanation

4. Execution Example

Finding Minimum Spanning Tree Using Kruskal's Algorithm

1. Overview of Kruskal's Algorithm

2. Implementing Kruskal's Algorithm in C++

3. Code Explanation

4. Execution Example

Conclusion

관련