Find the MST Weight

111.4k
0

Given a connected, undirected, weighted graph with V vertices numbered from 0 to V - 1 and E edges, find the sum of edge weights in a minimum spanning tree.

Every edge is represented as [source, destination, weight]. A minimum spanning tree connects every vertex, contains no cycle, uses exactly V - 1 edges, and has the smallest possible total edge weight.

Example 1

Input: V = 4, edges = [[0,1,1],[1,2,2],[2,3,3],[0,3,4]]

Output: 6

Explanation: Edges (0,1), (1,2), and (2,3) connect all vertices with total weight 1 + 2 + 3 = 6.

Example 2

Input: V = 3, edges = [[0,1,5],[1,2,10],[2,0,15]]

Output: 15

Explanation: Edges (0,1) and (1,2) connect all vertices with total weight 5 + 10 = 15.

Approach 1

Prim's algorithm grows one connected tree from an arbitrary starting vertex. A min-heap stores candidate edges crossing from selected vertices to unselected vertices, so the lightest available connection is processed first.

A visited array prevents duplicate heap entries from adding the same vertex more than once. The cut property guarantees safety for every accepted minimum crossing edge. Prerequisite concepts include adjacency lists, priority queues, greedy selection, and the cut property.

Algorithm

  • Build an undirected adjacency list so every vertex can access all of its connected edges.

  • Initialize a min-heap with vertex 0 and weight 0 because Prim's algorithm can begin from any vertex.

  • Remove the minimum-weight entry because the lightest available connection is the best candidate for extending the MST.

  • Skip the entry when its vertex is already visited because that vertex has already been included in the MST.

  • Mark the vertex as visited, add its edge weight to the MST weight, and increase the included-vertex count.

  • Push every edge connecting the selected vertex to an unvisited neighbor because these edges become candidates for the next selection.

  • Continue selecting the minimum-weight valid edge until all V vertices are included.

  • Return the accumulated MST weight.

Dry Run

mst-prims-corrected

mst-prims-corrected

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to compute MST weight using a binary min-heap.
int spanningTree(int vertices, vector<vector<int>>& edges) {
// Build an undirected adjacency list.
vector<vector<pair<int, int>>> adjacency(vertices);
for (const auto& edge : edges) {
adjacency[edge[0]].push_back({edge[1], edge[2]});
adjacency[edge[1]].push_back({edge[0], edge[2]});
}
// Store pairs as {connection weight, destination vertex}.
priority_queue<pair<int, int>,
vector<pair<int, int>>,
greater<pair<int, int>>> minHeap;
vector<bool> inMst(vertices, false);
minHeap.push({0, 0});
int totalWeight = 0;
int includedVertices = 0;
// Grow one tree until every vertex becomes part of the MST.
while (!minHeap.empty() && includedVertices < vertices) {
auto [weight, node] = minHeap.top();
minHeap.pop();
// Ignore stale entries for vertices already selected.
if (inMst[node]) continue;
// Accept the cheapest edge crossing the current cut.
inMst[node] = true;
totalWeight += weight;
includedVertices++;
// Add candidate edges leading outside the growing tree.
for (const auto& [neighbor, edgeWeight] : adjacency[node]) {
if (!inMst[neighbor]) {
minHeap.push({edgeWeight, neighbor});
}
}
}
// Return the total MST weight.
return totalWeight;
}
};
// Driver function with a hard-coded graph.
int main() {
int vertices = 4;
vector<vector<int>> edges = {
{0, 1, 1}, {1, 2, 2}, {2, 3, 3}, {0, 3, 4}
};
Solution solution;
cout << solution.spanningTree(vertices, edges) << "\n";
return 0;
}

Complexity Analysis

Here, V is the number of vertices and E is the number of edges.

Time Complexity: O(E×log V), because every edge can enter the binary min-heap and each heap operation costs logarithmic time.

Space Complexity: O(V+E), where the adjacency list, heap entries, and visited array store graph data.

Approach 2

Kruskal's algorithm builds a forest by processing all edges in nondecreasing weight order. Disjoint Set Union tracks the component containing every vertex, allowing constant-like cycle checks before edge selection.

Path compression shortens parent chains, while union by size keeps component trees shallow. The cut property guarantees safety for the lightest edge joining two separate components. Prerequisite concepts include edge sorting, Disjoint Set Union, path compression, union by size, and the cut property.

Algorithm

  • Sort all edges in nondecreasing order of weight so the lightest edges are considered first.

  • Initialize every vertex as an independent DSU component because no vertices are connected initially.

  • Find the representatives of both endpoints for each sorted edge to determine whether they already belong to the same component.

  • Skip the edge when both representatives are equal because adding it would create a cycle.

  • Merge the two different components using union by size so the DSU trees remain shallow.

  • Add the selected edge's weight to the MST weight and increase the selected-edge count.

  • Stop after selecting V - 1 edges because a spanning tree with V vertices requires exactly V - 1 edges.

  • Return the accumulated MST weight.

Dry Run

mst-kruskal-corrected

mst-kruskal-corrected

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Function to find a component representative with path compression.
int findParent(int node, vector<int>& parent) {
if (parent[node] == node) return node;
parent[node] = findParent(parent[node], parent);
return parent[node];
}
// Function to merge two components using union by size.
bool unite(int first, int second,
vector<int>& parent, vector<int>& size) {
int rootFirst = findParent(first, parent);
int rootSecond = findParent(second, parent);
if (rootFirst == rootSecond) return false;
if (size[rootFirst] < size[rootSecond]) {
swap(rootFirst, rootSecond);
}
parent[rootSecond] = rootFirst;
size[rootFirst] += size[rootSecond];
return true;
}
public:
// Function to compute MST weight using Disjoint Set Union.
int spanningTree(int vertices, vector<vector<int>>& edges) {
// Process edges from smallest weight to largest weight.
sort(edges.begin(), edges.end(),
[](const auto& left, const auto& right) {
return left[2] < right[2];
});
// Initialize one independent component for every vertex.
vector<int> parent(vertices);
vector<int> size(vertices, 1);
iota(parent.begin(), parent.end(), 0);
int totalWeight = 0;
int selectedEdges = 0;
// Select only edges joining different components.
for (const auto& edge : edges) {
if (!unite(edge[0], edge[1], parent, size)) continue;
totalWeight += edge[2];
selectedEdges++;
if (selectedEdges == vertices - 1) break;
}
// Return the total MST weight.
return totalWeight;
}
};
// Driver function with a hard-coded graph.
int main() {
int vertices = 4;
vector<vector<int>> edges = {
{0, 1, 1}, {1, 2, 2}, {2, 3, 3}, {0, 3, 4}
};
Solution solution;
cout << solution.spanningTree(vertices, edges) << "\n";
return 0;
}

Complexity Analysis

Here, V is the number of vertices and E is the number of edges.

Time Complexity: O(E×log E + E×ALPHA(V)), where ALPHA(V) is the inverse Ackermann function and is practically constant. Edge sorting dominates the overall complexity.

Space Complexity: O(V+E), where sorted edges and DSU parent and size arrays store graph and component data.

Interview follow-up Questions

No. Removing one edge from a cycle preserves connectivity, so a minimum spanning structure remains acyclic.

Graph

Read Similar Blogs

Graph

Find the City with the Smallest Number of Neighbors at a Threshold Distance

Given N cities numbered from 0 to N-1 , an array of bidirectional weighted roads [first, second, weight] , and a positive distanceThreshold , count the other cities reachable from every city with s...

105.7k
Graph

Dijkstra’s Algorithm

Given an undirected weighted graph with V vertices numbered from 0 to V - 1 , an edge list, and a source vertex, find the shortest distance from source to every vertex. Every edge appears as [u, v,...

93k
Graph

Print Shortest Path

Given a weighted undirected graph with n vertices numbered from 1 to n and m edges, find a shortest path from vertex 1 to vertex n . Each edge appears as [u, v, weight] and every weig...

96.1k
Comments0