What is a Minimum Spanning Tree (MST)?

A Minimum Spanning Tree (MST) of a connected, undirected graph is a subgraph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

What are the main algorithms to find the MST?

The two most common algorithms for finding a Minimum Spanning Tree are Prim's algorithm and Kruskal's algorithm. Both are greedy algorithms that always find the optimal solution.

Graph Algorithms

Minimum Spanning Tree Problems

Master MST algorithms like Prim's and Kruskal's. This guide provides expert solutions, practice problems, and AI-powered hints to help you ace your coding interviews.

Prim's Algorithm for MST

Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. It works by building the tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.

                            function prims(graph) {
                              // graph should be an adjacency list representation
                            const minHeap = new PriorityQueue({ compare: (a, b) => a[0] - b[0] });
                            const visited = new Set();
                            let totalWeight = 0;
                            
                              // Start from vertex 0
                            minHeap.enqueue([0, 0]); // [weight, vertex]
                            
                            while (!minHeap.isEmpty()) {
                            const [weight, u] = minHeap.dequeue();
                            
                            if (visited.has(u)) continue;
                            
                            visited.add(u);
                            totalWeight += weight;
                            
                            for (const [v, edgeWeight] of graph[u]) {
                            if (!visited.has(v)) {
                            minHeap.enqueue([edgeWeight, v]);
                            }
                            }
                            }
                            
                            return totalWeight;
                            }
                        

AI Coach Hint: Prim's algorithm is very similar to Dijkstra's algorithm for shortest paths. The main difference is that Dijkstra's considers the total path cost from the source, while Prim's only considers the weight of the single edge being added. A priority queue (min-heap) is crucial for an efficient implementation.