# 11. Minimum spanning tree - points

[mst-minimum-spanning-tree](https://algorithm.prettylog.com/overview/3.-how-to-construct-algorithm-paradigm/mst-minimum-spanning-tree "mention")

1584\. Min Cost to Connect All PointsMedium3.7K85Companies

You are given an array `points` representing integer coordinates of some points on a 2D-plane, where `points[i] = [xi, yi]`.

The cost of connecting two points `[xi, yi]` and `[xj, yj]` is the **manhattan distance** between them: `|xi - xj| + |yi - yj|`, where `|val|` denotes the absolute value of `val`.

Return *the minimum cost to make all points connected.* All points are connected if there is **exactly one** simple path between any two points.

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/08/26/d.png)

<pre><code><strong>Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
</strong><strong>Output: 20
</strong><strong>Explanation: 
</strong>
We can connect the points as shown above to get the minimum cost of 20.
Notice that there is a unique path between every pair of points.
</code></pre>

**Example 2:**

<pre><code><strong>Input: points = [[3,12],[-2,5],[-4,1]]
</strong><strong>Output: 18
</strong></code></pre>

**Constraints:**

* `1 <= points.length <= 1000`
* `-106 <= xi, yi <= 106`
* All pairs `(xi, yi)` are distinct.

{% embed url="<https://leetcode.com/problems/min-cost-to-connect-all-points/>" %}

## Prim

***

> Time:\
> Prim: ((V + E)logN), E insert logV ⇒ ElogV, V remove logV ⇒ VlogV\
> adjs Creation: O(N^2)\
> Total: <mark style="color:blue;">O(N^2)</mark>

> Space: O(N^2) every points can be connected to each other

```jsx
/**
 * @param {number[][]} points
 * @return {number}
 */

function Node(vertex, precedessor, dist) {
    this.vertex = vertex;
    this.precedessor = precedessor;
    this.dist = dist;
}

var minCostConnectPoints = function (points) {
    // first need to find weights between each point pair
    const dist = {};

		// V^2
    for (let i = 0; i < points.length; i++) {
        dist[i] = [];
        for (let j = 0; j < points.length; j++) {
            const distance = getDistance(points[i], points[j]);
            dist[i][j] = dist[i][j] ?? [];
            dist[i][j] = distance;
        }
    }

    const minHeap = new Heap([], (a, b) => a.dist <= b.dist);
    
    const visited = new Set();
    minHeap.insert(new Node(0, 0, 0));

    let sum = 0;
		// V
    while (minHeap.size > 0) {
				// logV
        const node = minHeap.remove();

        // required filter
        if (visited.has(node.vertex)) {
            continue;
        }

        sum += node.dist;
        visited.add(node.vertex);

        const adj = dist[node.vertex];
				// E
        for (let there = 0; there < adj.length; there++) {
            // can do another filter optional
            // if (visited.has(there)) {
            //     continue;
            // }
            const d = dist[node.vertex][there];
						// logV
            minHeap.insert(new Node(there, node.vertex, d));
        }
    }   

    return sum;
};

function getDistance(p1, p2) {
    return Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]);
}

function swap(arr, a, b) {
    [arr[a], arr[b]] = [arr[b], arr[a]];
}
```