Minimum Spanning Tree

shriyanshi24jindal

Mar 30th, 2026

132

Never

Not a member of GistPad yet? Sign Up, it unlocks many cool features!

Java 12.60 KB | None | 0 0

copy raw download clone embed print report

class Pair {
int vertex;
int weight;
Pair(int weight, int vertex)
{
this.vertex = vertex;
this.weight = weight;
}
}
class Solution {
/**
* Start from any node and keep adding the minimum weight edge that connects a visited node to an unvisited node.
* Step 1: Build Adjacency List
* Step 2: Use a Min Heap (Priority Queue)
* -- This ensures we always pick the minimum weight edge
* -- Each entry in PQ = (weight, node)
* Step 3: Start from Node 0, Start with node 0 and Weight = 0 (no cost to start)
* Step 4: Maintain Visited Array and sum as 0
* Step 5: Main Loop (Core of Prim’s)
* -- Extract minimum edge
* -- Always picks the smallest weight edge available
* -- Skip if already visited, Avoids revisiting nodes (cycle prevention)
* -- Include this edge in MST
* -- Add its weight to total cost
* -- Explore neighbors and Push all adjacent edges into PQ, Only if neighbor is not visited
* Step 6: Return sum of all edges
*/
public int spanningTree(int V, int[][] edges) {
// Step-1 Create an adjacency list
ArrayList<ArrayList<Pair>> adj = new ArrayList<>();
for(int i=0; i<V; i++)
{
adj.add(new ArrayList<Pair>());
}
for(int[] edge : edges)
{
int u = edge[0];
int v = edge[1];
int w = edge[2];
adj.get(u).add(new Pair(w, v));
adj.get(v).add(new Pair(w, u)); // undirected
}
// Step-2 Create a visited array
boolean[] visited = new boolean[V];
// Step-3 Define a min-heap <weight, node>
PriorityQueue<Pair> pq = new PriorityQueue<>( (x,y) -> Integer.compare(x.weight, y.weight));
pq.offer(new Pair(0, 0));
int sum = 0;
while(!pq.isEmpty())
{
Pair pair = pq.poll();
int weight = pair.weight;
int currentNode = pair.vertex;
if(visited[currentNode])
continue;
visited[currentNode] = true;
sum += weight;
// traverse the neighbour nodes
for(Pair neighbour : adj.get(currentNode))
{
if(visited[neighbour.vertex] == false)
{
pq.offer(new Pair(neighbour.weight, neighbour.vertex));
}
}
}
return sum;
}
}

RAW Paste Data Copied

class Pair {
    int vertex;
    int weight;

Pair(int weight, int vertex) 
    {
        this.vertex = vertex;
        this.weight = weight;
    }
}

class Solution {
    /**
     * Start from any node and keep adding the minimum weight edge that connects a visited node to an unvisited node.
     * Step 1: Build Adjacency List
     * Step 2: Use a Min Heap (Priority Queue) 
     *      -- This ensures we always pick the minimum weight edge
     *      -- Each entry in PQ = (weight, node)
     * Step 3: Start from Node 0, Start with node 0 and Weight = 0 (no cost to start)
     * Step 4: Maintain Visited Array and sum as 0
     * Step 5: Main Loop (Core of Prim’s)
     *      -- Extract minimum edge
     *      -- Always picks the smallest weight edge available
     *      -- Skip if already visited, Avoids revisiting nodes (cycle prevention)
     *      -- Include this edge in MST
     *      -- Add its weight to total cost
     *      -- Explore neighbors and Push all adjacent edges into PQ, Only if neighbor is not visited
     * Step 6: Return sum of all edges
     */
    public int spanningTree(int V, int[][] edges) {
        // Step-1 Create an adjacency list
        ArrayList<ArrayList<Pair>> adj = new ArrayList<>();
        for(int i=0; i<V; i++)
        {
            adj.add(new ArrayList<Pair>());
        }
        
        for(int[] edge : edges)
        {
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];
            
            adj.get(u).add(new Pair(w, v));
            adj.get(v).add(new Pair(w, u)); // undirected
        }

// Step-2 Create a visited array
        boolean[] visited = new boolean[V];
    
        // Step-3 Define a min-heap <weight, node> 
        PriorityQueue<Pair> pq = new PriorityQueue<>( (x,y) -> Integer.compare(x.weight, y.weight));
        pq.offer(new Pair(0, 0));
        
        int sum = 0;
        while(!pq.isEmpty())
        {
            Pair pair = pq.poll();
            int weight = pair.weight;
            int currentNode = pair.vertex;
            
            if(visited[currentNode])
                continue;
            
            visited[currentNode] = true;
            sum += weight;
            
            // traverse the neighbour nodes
            for(Pair neighbour : adj.get(currentNode))
            {
                if(visited[neighbour.vertex] == false)
                {
                    pq.offer(new Pair(neighbour.weight, neighbour.vertex));
                }
            }
        }
        return sum;
    }
}