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.<\/p>\n
Given a weighted undirected graph as follows, find the minimum spanning tree.<\/p>\n
Input:\nThe first line contains the number of vertices V<\/em> and the number of edges E<\/em>. (1 \u2264 V<\/em> \u2264 1000, 1 \u2264 E<\/em> \u2264 10000)\nThe next E<\/em> lines each contain the edge information u, v, w<\/em>. This means that the weight w<\/em> connects vertex u<\/em> and vertex v<\/em>.\n\nOutput:\nPrint the total weight of the minimum spanning tree.<\/code><\/pre>\nExample Input<\/h2>\n3 3\n1 2 1\n2 3 2\n1 3 3\n<\/code><\/pre>\nExample Output<\/h2>\n3\n<\/code><\/pre>\nSolution Method<\/h2>\n
To solve this problem, we can use Prim’s algorithm or Kruskal’s algorithm. Here, we will use Kruskal’s algorithm for the solution.<\/p>\n
Kruskal’s Algorithm Explanation<\/h3>\n
Kruskal’s algorithm is an edge-based algorithm that proceeds in the following steps:<\/p>\n
\n- Sort all edges in ascending order of weight.<\/li>\n
- Initialize the vertex set. (Using Union-Find data structure)<\/li>\n
- 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.<\/li>\n<\/ol>\n
Code Implementation<\/h3>\n
Now, let’s implement Kruskal’s algorithm in C++.<\/p>\n
#include <iostream>\n#include <vector>\n#include <algorithm>\n\nusing namespace std;\n\nstruct Edge {\n int u, v, weight;\n};\n\nbool compare(Edge a, Edge b) {\n return a.weight < b.weight;\n}\n\nint find(int parent[], int x) {\n if (parent[x] != x) {\n parent[x] = find(parent, parent[x]);\n }\n return parent[x];\n}\n\nvoid unionSet(int parent[], int rank[], int x, int y) {\n int rootX = find(parent, x);\n int rootY = find(parent, y);\n\n if (rootX != rootY) {\n if (rank[rootX] < rank[rootY]) {\n parent[rootX] = rootY;\n } else if (rank[rootX] > rank[rootY]) {\n parent[rootY] = rootX;\n } else {\n parent[rootY] = rootX;\n rank[rootX]++;\n }\n }\n}\n\nint kruskal(int V, vector& edges) {\n sort(edges.begin(), edges.end(), compare);\n int parent[V + 1];\n int rank[V + 1];\n for (int i = 0; i <= V; i++) {\n parent[i] = i;\n rank[i] = 0;\n }\n\n int totalWeight = 0;\n for (Edge edge : edges) {\n if (find(parent, edge.u) != find(parent, edge.v)) {\n totalWeight += edge.weight;\n unionSet(parent, rank, edge.u, edge.v);\n }\n }\n return totalWeight;\n}\n\nint main() {\n int V, E;\n cin >> V >> E;\n vector edges(E);\n for (int i = 0; i < E; i++) {\n cin >> edges[i].u >> edges[i].v >> edges[i].weight;\n }\n cout << kruskal(V, edges) << endl;\n return 0;\n}\n<\/edge><\/edge><\/code><\/pre>\nCode Explanation<\/h2>\n
First, we define the Edge structure and sort based on weights using a comparison function.<\/p>\n
find<\/b> function uses path compression to efficiently find the parent node. unionSet<\/b> function merges the sets of two vertices while using rank to prevent the tree from becoming too large.<\/p>\n
The main function receives input and calculates the total weight of the minimum spanning tree using Kruskal’s algorithm and then outputs it.<\/p>\n
Complexity Analysis<\/h2>\n
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.<\/p>\n
Conclusion<\/h2>\n
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.<\/p>\n
The next lecture will cover other algorithms related to the minimum spanning tree or various problem-solving, so stay tuned.<\/p>\n","protected":false},"excerpt":{"rendered":"