Prim - Minimum spanning tree

Ref: https://www.youtube.com/watch?v=4ZlRH0eK-qQ Spanning tree → Minimum Spanning Tree (Read below for more) Min Heap just like Dijkstra but different purpose Dijkstra vs Prim

---

Min cost to connect all points

• Create edges O(n^2)
• apply Prim log(n) - start from any node, use BFS+visited+MinHeap
• Stop when visited set is equal to node count - we got our spanning tree

time: O(n^2 * log(n))

class Solution {
    /**
     * @param {number[][]} points
     * @return {number}
     */
    minCostConnectPoints(points) {
        const N = points.length;
        const adj = new Map();
        for (let i = 0; i < N; i++) {
            adj.set(i, []);
        }
 
        for (let i = 0; i < N; i++) {
            const [x1, y1] = points[i];
            for (let j = i + 1; j < N; j++) {
                const [x2, y2] = points[j];
                const dist = Math.abs(x1 - x2) + Math.abs(y1 - y2);
                adj.get(i).push([dist, j]);
                adj.get(j).push([dist, i]);
            }
        }
 
        let res = 0;
        const visit = new Set();
        const minHeap = new MinPriorityQueue((entry) => entry[0]);
        minHeap.push([0, 0]);
 
        while (visit.size < N) {
            const [cost, i] = minHeap.pop();
            if (visit.has(i)) continue;
            res += cost;
            visit.add(i);
            for (const [neiCost, nei] of adj.get(i)) {
                if (!visit.has(nei)) {
                    minHeap.push([neiCost, nei]);
                }
            }
        }
        return res;
    }
}

---

Spanning Tree

A spanning tree of a graph is a subset of edges that:

• Connects all vertices
• Has no cycles
• Uses exactly V - 1 edges (for V vertices)

Example:

A --- B
|   / |
|  /  |
| /   |
C --- D

One possible spanning tree:

A --- B
|
|
C --- D

All 4 nodes connected, no cycles, 3 edges (= V-1).

---

Minimum Spanning Tree (MST)

If the graph has weighted edges, an MST is:

A spanning tree whose total edge weight is minimum.

Example:

A --1-- B
|       |
4       2
|       |
C --3-- D

Possible spanning tree:

A --1-- B
B --2-- D
D --3-- C
 
Total = 6

If that’s the smallest possible total weight, it’s the MST.

---

Interview Notes

Spanning Tree:
- Connects all nodes
- No cycles
- Exactly V - 1 edges
 
Minimum Spanning Tree:
- A spanning tree with minimum total edge weight
 
Popular Algorithms:
- Kruskal's (Union Find)
- Prim's (Min Heap)

A common interview question:

“When do I use MST?”

Use MST when you need to connect all nodes as cheaply as possible, e.g. laying fiber cables between cities, connecting servers, road networks, etc.