Prim's Algorithm

Definition

Definition

Prim's Algorithm is a greedy algorithm used to find the minimum spanning tree of a connected, undirected graph. It operates by selecting the smallest edge connected to the current minimum spanning tree and adding it to the tree, repeating this process until all vertices are included

Explanation

Beginning with an arbitrary vertex, the algorithm grows the minimum spanning tree one vertex at a time. At each step, it selects the smallest edge that connects a vertex in the tree to a vertex outside of it, ensuring that the tree remains connected. This process continues until all vertices are included in the tree, resulting in a minimum spanning tree that spans all vertices with the smallest possible total edge weight

Guidance

• Choose an arbitrary starting vertex to begin the minimum spanning tree
• Mark this vertex as visited or add it to the minimum spanning tree
  • find the smallest edge connected to any vertex in the minimum spanning tree that leads to an unvisited vertex
  • add this edge to the minimum spanning tree
  • mark the newly reached vertex as visited
  • repeat steps until all vertices are included in the minimum spanning tree

Tips

• keep track of visited vertices to avoid cycles and ensure connectivity
• utilize a priority queue or heap data structure to efficiently find the smallest edge at each step
• ensure that the graph is connected; if not, handle disconnected components separately or consider using a different algorithm

Practice

Practice

Prim(Graph, start_vertex):
    initialize an empty set called MST (minimum spanning tree)
    initialize a priority queue called pq
    initialize a boolean array called visited to track visited vertices
    add start_vertex to pq with priority 0
    while pq is not empty:
        vertex = pq.extract_min()
        if vertex is not visited:
            add vertex to MST
            mark vertex as visited
            for each neighbor of vertex:
                if neighbor is not visited:
                    add edge(vertex, neighbor) to pq with priority equal to edge weight
    return MST

Solution

package main

import (
    "container/heap"
)

type Edge struct {
    node   int
    weight int
}

type Graph struct {
    numNodes int
    adjList  map[int][]Edge
}

func NewGraph(numNodes int) *Graph {
    return &Graph{
        numNodes: numNodes,
        adjList:  make(map[int][]Edge),
    }
}

func (g *Graph) AddEdge(u, v, weight int) {
    g.adjList[u] = append(g.adjList[u], Edge{node: v, weight: weight})
    g.adjList[v] = append(g.adjList[v], Edge{node: u, weight: weight})
}

func PrimMST(g *Graph) int {
    visited := make(map[int]bool)
    pq := make(PriorityQueue, 0)
    startNode := 0

    heap.Push(&pq, &Item{node: startNode, weight: 0})

    minCost := 0

    for pq.Len() > 0 {
        item := heap.Pop(&pq).(*Item)
        u := item.node

        if visited[u] {
            continue
        }

        visited[u] = true
        minCost += item.weight

        for _, edge := range g.adjList[u] {
            v := edge.node
            weight := edge.weight
            if !visited[v] {
                heap.Push(&pq, &Item{node: v, weight: weight})
            }
        }
    }
    return minCost
}

type Item struct {
    node   int
    weight int
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].weight < pq[j].weight
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
    item := x.(*Item)
    *pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    *pq = old[0 : n-1]
    return item
}

import java.util.*;

class Edge {

  int node;
  int weight;

  public Edge(int node, int weight) {
    this.node = node;
    this.weight = weight;
  }
}

class Graph {

  int numNodes;
  Map<Integer, List<Edge>> adjList;

  public Graph(int numNodes) {
    this.numNodes = numNodes;
    this.adjList = new HashMap<>();
    for (int i = 0; i < numNodes; i++) {
      adjList.put(i, new ArrayList<>());
    }
  }

  public void addEdge(int u, int v, int weight) {
    adjList.get(u).add(new Edge(v, weight));
    adjList.get(v).add(new Edge(u, weight));
  }
}

public class PrimAlgorithm {

  public static int primMST(Graph graph) {
    boolean[] visited = new boolean[graph.numNodes];
    PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
    int startNode = 0;

    pq.offer(new Edge(startNode, 0));

    int minCost = 0;

    while (!pq.isEmpty()) {
      Edge edge = pq.poll();
      int u = edge.node;

      if (visited[u]) {
        continue;
      }

      visited[u] = true;
      minCost += edge.weight;

      for (Edge adjacent : graph.adjList.get(u)) {
        int v = adjacent.node;
        int weight = adjacent.weight;

        if (!visited[v]) {
          pq.offer(new Edge(v, weight));
        }
      }
    }
    return minCost;
  }
}

class PriorityQueue {
  constructor() {
    this.queue = [];
  }

  enqueue(element) {
    this.queue.push(element);
    this.queue.sort((a, b) => a[1] - b[1]);
  }

  dequeue() {
    return this.queue.shift();
  }

  isEmpty() {
    return this.queue.length === 0;
  }
}

class Graph {
  constructor(numNodes) {
    this.numNodes = numNodes;
    this.adjList = new Map();
    for (let i = 0; i < numNodes; i++) {
      this.adjList.set(i, []);
    }
  }

  addEdge(u, v, weight) {
    this.adjList.get(u).push({ node: v, weight });
    this.adjList.get(v).push({ node: u, weight });
  }
}

function primMST(graph) {
  const visited = new Array(graph.numNodes).fill(false);
  const pq = new PriorityQueue();
  const startNode = 0;

  pq.enqueue([startNode, 0]);

  let minCost = 0;

  while (!pq.isEmpty()) {
    const [u, weight] = pq.dequeue();

    if (visited[u]) {
      continue;
    }

    visited[u] = true;
    minCost += weight;

    for (const { node, weight } of graph.adjList.get(u)) {
      if (!visited[node]) {
        pq.enqueue([node, weight]);
      }
    }
  }
  return minCost;
}

import java.util.*

class Edge(val node: Int, val weight: Int)

class Graph(val numNodes: Int) {
    val adjList = mutableMapOf<Int, MutableList<Edge>>()

    init {
        for (i in 0 until numNodes) {
            adjList[i] = mutableListOf()
        }
    }

    fun addEdge(u: Int, v: Int, weight: Int) {
        adjList[u]?.add(Edge(v, weight))
        adjList[v]?.add(Edge(u, weight))
    }
}

fun primMST(graph: Graph): Int {
    val visited = BooleanArray(graph.numNodes)
    val pq = PriorityQueue<Pair<Int, Int>>(compareBy { it.second })
    val startNode = 0

    pq.offer(Pair(startNode, 0))

    var minCost = 0

    while (pq.isNotEmpty()) {
        val (u, weight) = pq.poll()

        if (visited[u]) {
            continue
        }

        visited[u] = true
        minCost += weight

        graph.adjList[u]?.forEach { (v, weight) ->
            if (!visited[v]) {
                pq.offer(Pair(v, weight))
            }
        }
    }
    return minCost
}

import heapq

class Graph:
    def __init__(self, numNodes):
        self.numNodes = numNodes
        self.adjList = [[] for _ in range(numNodes)]

    def addEdge(self, u, v, weight):
        self.adjList[u].append((v, weight))
        self.adjList[v].append((u, weight))

def primMST(graph):
    visited = [False] * graph.numNodes
    pq = [(0, 0)]
    minCost = 0

    while pq:
        weight, u = heapq.heappop(pq)

        if visited[u]:
            continue

        visited[u] = True
        minCost += weight

        for v, w in graph.adjList[u]:
            if not visited[v]:
                heapq.heappush(pq, (w, v))

    return minCost

use std::collections::BinaryHeap;
use std::cmp::Ordering;

#[derive(Clone, Copy, Eq, PartialEq)]
struct Edge {
    node: usize,
    weight: usize,
}

impl Ord for Edge {
    fn cmp(&self, other: &Self) -> Ordering {
        other.weight.cmp(&self.weight)
    }
}

impl PartialOrd for Edge {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

struct Graph {
    num_nodes: usize,
    adj_list: Vec<Vec<Edge>>,
}

impl Graph {
    fn new(num_nodes: usize) -> Self {
        Graph {
            num_nodes,
            adj_list: vec![Vec::new(); num_nodes],
        }
    }

    fn add_edge(&mut self, u: usize, v: usize, weight: usize) {
        self.adj_list[u].push(Edge { node: v, weight });
        self.adj_list[v].push(Edge { node: u, weight });
    }
}

fn prim_mst(graph: &Graph) -> usize {
    let mut visited = vec![false; graph.num_nodes];
    let mut pq = BinaryHeap::new();
    let start_node = 0;

    pq.push(Edge { node: start_node, weight: 0 });
    
    let mut min_cost = 0;

    while let Some(Edge { node: u, weight }) = pq.pop() {
        if visited[u] {
            continue;
        }

        visited[u] = true;
        min_cost += weight;

        for &Edge { node: v, weight } in &graph.adj_list[u] {
            if !visited[v] {
                pq.push(Edge { node: v, weight });
            }
        }
    }
    min_cost
}

class Edge {
  constructor(
    public node: number,
    public weight: number,
  ) {}
}

class Graph {
  numNodes: number;
  adjList: Map<number, Edge[]>;

  constructor(numNodes: number) {
    this.numNodes = numNodes;
    this.adjList = new Map<number, Edge[]>();
    for (let i = 0; i < numNodes; i++) {
      this.adjList.set(i, []);
    }
  }

  addEdge(u: number, v: number, weight: number) {
    this.adjList.get(u)?.push(new Edge(v, weight));
    this.adjList.get(v)?.push(new Edge(u, weight));
  }
}

function primMST(graph: Graph): number {
  const visited: boolean[] = new Array(graph.numNodes).fill(false);
  const pq: [number, number][] = [];
  const startNode = 0;

  pq.push([0, startNode]);

  let minCost = 0;

  while (pq.length > 0) {
    const [weight, u] = pq.shift()!;

    if (visited[u]) {
      continue;
    }

    visited[u] = true;

    minCost += weight;

    for (const edge of graph.adjList.get(u)!) {
      const { node: v, weight } = edge;
      if (!visited[v]) {
        pq.push([weight, v]);
      }
    }
    pq.sort((a, b) => a[0] - b[0]);
  }
  return minCost;
}