JavaScript Coding Test Course, Finding Minimum Spanning Tree

Today, we will learn about a method to find the “Minimum Spanning Tree (MST)” which is a common problem in algorithm tests. In particular, we will explain how to solve this problem step by step using JavaScript. Through this tutorial, you will understand all the concepts and develop the ability to confidently solve this problem in actual coding tests.

1. What is a Minimum Spanning Tree?

A Minimum Spanning Tree is a subgraph that includes all vertices of a connected graph and has the minimum sum of edge weights. In other words, it refers to a tree that connects all vertices with the least cost. MST is used in various fields such as network design, transportation systems, and clustering.

2. Problem Description

When given the vertices and edges information of a graph, please write a function that finds the Minimum Spanning Tree and returns its total weight.

Input Format

The number of vertices n (1 ≤ n ≤ 1000)
The number of edges m (1 ≤ m ≤ 10000)
Each edge is given in the form of (a, b, c), where a and b are the vertices and c is the weight of the edge.

Output Format

Print the total weight of the Minimum Spanning Tree.

Example

3. Algorithm Selection

There are several methods to find the Minimum Spanning Tree. Among these, Kruskal’s Algorithm and Prim’s Algorithm are widely used. We will use Kruskal’s Algorithm here.

Kruskal’s Algorithm

Kruskal’s Algorithm sorts the edges based on their weights and selects the edge with the lowest weight first, ensuring that no cycles are formed so that it can create the Minimum Spanning Tree. This method first sorts the given list of edges and then adds the lightest edges one by one.

4. Algorithm Implementation

Now, let’s write the JavaScript code to solve the problem using Kruskal’s Algorithm. The overall steps are as follows:

After receiving edge information, sort them based on weights.
Use the Union-Find data structure to include edges without forming cycles.
After processing all edges, calculate and return the total weight of the Minimum Spanning Tree.

Code Implementation

    
    function find(parent, i) {
        if (parent[i] === -1) {
            return i;
        }
        return find(parent, parent[i]);
    }

    function union(parent, x, y) {
        const xset = find(parent, x);
        const yset = find(parent, y);
        parent[xset] = yset;
    }

    function kruskal(n, edges) {
        edges.sort((a, b) => a[2] - b[2]); // Sort by edge weight
        let parent = Array(n + 1).fill(-1);
        let minWeight = 0;
        const mst = [];

        for (let i = 0; i < edges.length; i++) {
            const [u, v, weight] = edges[i];

            if (find(parent, u) !== find(parent, v)) {
                union(parent, u, v);
                minWeight += weight;
                mst.push([u, v, weight]);
            }
        }

        return { minWeight, mst };
    }

    // Example input data
    const n = 4;
    const edges = [
        [1, 2, 1],
        [1, 3, 4],
        [2, 3, 2],
        [1, 4, 3],
        [3, 4, 5]
    ];

    const result = kruskal(n, edges);
    console.log("Total weight of the Minimum Spanning Tree:", result.minWeight);

5. Code Explanation

The above code is a function that uses Kruskal's Algorithm to find the Minimum Spanning Tree of the given graph. It is divided into the following key parts:

5.1. Union-Find Function

The Union-Find data structure is used to track the connected components of the graph. Each node has its own parent. The find function finds the representative of the set that the node belongs to, and the union function merges two sets.

5.2. Edge Sorting

Sort the list of edges by weight to select the minimum weight edge first. The sort method in JavaScript can be used to sort easily.

5.3. Minimum Spanning Tree Construction

For each edge, check the parents of the two nodes and select the edge only if it does not create a cycle. The selected edges are stored in the mst array, and the sum of the weights is incremented in the minWeight variable.

6. Performance Analysis

The time complexity of Kruskal's Algorithm is O(E log E). Here, E is the number of edges. Under the constraints of the given problem, this algorithm is efficient. You can expect additional performance improvements with the path compression technique of Union-Find.

7. Conclusion

In this tutorial, we learned about Kruskal's Algorithm to find the Minimum Spanning Tree using JavaScript and explained in detail how to solve the problem. Graph problems are frequently posed in algorithm competitions and various coding tests, so mastering this content will be very helpful. Next, we will solve various problems using other algorithms or data structures.

8. Practice Problem

Try to solve the following problem. After solving it, review your code to check for any parts that can be optimized.

Write an algorithm to extract the edges of the Minimum Spanning Tree from the given graph and output this list of edge weights.