Hello! In this blog post, we will discuss one of the frequently asked questions in coding tests using C++, Minimum Spanning Tree<\/strong>. We will use Prim’s algorithm and Kruskal’s algorithm, and we will organize the theory by solving a concrete problem.<\/p>\n Given the following graph, find the minimum spanning tree. Finally, output the sum of the weights of the tree.<\/p>\n The structure of the input is as follows:<\/p>\n 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.<\/p>\n Prim’s algorithm consists of the following steps:<\/p>\n Now, let’s implement Prim’s algorithm in C++. Through this implementation, we will look at the process of solving a real problem.<\/p>\n The explanation of the above code is as follows:<\/p>\n When executing the input data, the following result is obtained:<\/p>\n Output result:<\/p>\n 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.<\/p>\n Kruskal's algorithm consists of the following steps:<\/p>\n Now, let's implement Kruskal's algorithm in C++.<\/p>\n The explanation of the code above is as follows:<\/p>\n When executing the input data, the following result is obtained:<\/p>\n Output result:<\/p>\n 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.<\/p>\n 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.<\/p>\n 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!<\/p>\n <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"Problem Description<\/h2>\n
\nInput:\n5 7\n1 2 3\n1 3 4\n2 3 2\n2 4 6\n3 4 1\n3 5 5\n4 5 2\n\nOutput:\n6\n<\/pre>\n
\n
V<\/code> and number of edges E<\/code><\/li>\nE<\/code> lines: information about each edge (Vertex1, Vertex2, Weight)<\/li>\n<\/ul>\nProblem Solving Method<\/h2>\n
1. Overview of Prim’s Algorithm<\/h3>\n
\n
2. Implementing Prim’s Algorithm in C++<\/h3>\n
\n#include 3. Code Explanation<\/h4>\n
\n
inMST<\/code> array.<\/li>\n4. Execution Example<\/h4>\n
\n5 7\n1 2 3\n1 3 4\n2 3 2\n2 4 6\n3 4 1\n3 5 5\n4 5 2\n<\/code><\/pre>\n\n6\n<\/code><\/pre>\nFinding Minimum Spanning Tree Using Kruskal's Algorithm<\/h2>\n
1. Overview of Kruskal's Algorithm<\/h3>\n
\n
2. Implementing Kruskal's Algorithm in C++<\/h3>\n
\n#include 3. Code Explanation<\/h4>\n
\n
Edge<\/code> to store edges.<\/li>\n4. Execution Example<\/h4>\n
\n5 7\n1 2 3\n1 3 4\n2 3 2\n2 4 6\n3 4 1\n3 5 5\n4 5 2\n<\/code><\/pre>\n\n6\n<\/code><\/pre>\nConclusion<\/h2>\n