Prim 算法

1import heapq2
3
4def prim(graph, start):5    visited = {start}6    heap = [(w, start, v) for v, w in graph[start]]7    heapq.heapify(heap)8    mst, total = [], 09    while heap and len(visited) < len(graph):10        w, u, v = heapq.heappop(heap)11        if v in visited:12            continue13        visited.add(v)14        mst.append((u, v, w))15        total += w16        # Offer the new node's edges to the frontier17        for neighbor, weight in graph[v]:18            if neighbor not in visited:19                heapq.heappush(heap, (weight, v, neighbor))20    return mst, total21
22
23graph = {24    "A": [("B", 4), ("C", 1)],25    "B": [("A", 4), ("C", 3), ("D", 2)],26    "C": [("A", 1), ("B", 3), ("D", 5)],27    "D": [("B", 2), ("C", 5), ("E", 7)],28    "E": [("D", 7)],29}30
31mst, total = prim(graph, "A")32for u, v, w in mst:33    print(f"{u} - {v} (weight {w})")34print("Total MST weight:", total)

1const graph = {2    A: { B: 4, C: 2 },3    B: { A: 4, C: 1, D: 5 },4    C: { A: 2, B: 1, D: 8, E: 10 },5    D: { B: 5, C: 8, E: 2 },6    E: { C: 10, D: 2 },7};8
9function prim(start) {10    const inTree = new Set([start]);11    const mst = [];12    let total = 0;13    while (inTree.size < Object.keys(graph).length) {14        // JS has no built-in heap: scan all crossing edges for the cheapest15        let best = null;16        for (const u of inTree) {17            for (const [v, w] of Object.entries(graph[u])) {18                if (!inTree.has(v) && (best === null || w < best[2])) {19                    best = [u, v, w];20                }21            }22        }23        const [u, v, w] = best;24        inTree.add(v);25        mst.push(`${u}-${v} (${w})`);26        total += w;27    }28    return { mst, total };29}30
31const { mst, total } = prim("A");32console.log("MST edges:", mst.join(", "));33console.log("Total weight:", total);

1import java.util.ArrayList;2import java.util.List;3import java.util.PriorityQueue;4
5public class Main {6    public static void main(String[] args) {7        int n = 6;8        List<List<int[]>> adj = new ArrayList<>();9        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());10        int[][] edges = {11            {0, 1, 4}, {0, 2, 3}, {1, 2, 1}, {1, 3, 2},12            {2, 3, 4}, {3, 4, 2}, {4, 5, 6}, {2, 5, 7}13        };14        for (int[] e : edges) {15            adj.get(e[0]).add(new int[]{e[1], e[2]});16            adj.get(e[1]).add(new int[]{e[0], e[2]});17        }18
19        boolean[] inMst = new boolean[n];20        // Always grow the tree along the cheapest crossing edge21        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);22        pq.add(new int[]{0, 0}); // {node, edge weight}23        int total = 0, taken = 0;24        while (!pq.isEmpty() && taken < n) {25            int[] cur = pq.poll();26            if (inMst[cur[0]]) continue;27            inMst[cur[0]] = true;28            total += cur[1];29            taken++;30            for (int[] edge : adj.get(cur[0])) {31                if (!inMst[edge[0]]) pq.add(edge);32            }33        }34        System.out.println("MST nodes reached: " + taken);35        System.out.println("MST total weight: " + total);36    }37}

1#include <iostream>2#include <queue>3#include <vector>4
5int main() {6    // Undirected weighted graph: adj[u] = {(neighbor, weight), ...}7    std::vector<std::vector<std::pair<int, int>>> adj = {8        {{1, 2}, {3, 6}},                  // 09        {{0, 2}, {2, 3}, {3, 8}, {4, 5}},  // 110        {{1, 3}, {4, 7}},                  // 211        {{0, 6}, {1, 8}},                  // 312        {{1, 5}, {2, 7}},                  // 413    };14    int n = static_cast<int>(adj.size());15    std::vector<bool> inMST(n, false);16    using State = std::pair<int, int>;  // (edge weight, node)17    std::priority_queue<State, std::vector<State>, std::greater<State>> pq;18    pq.push({0, 0});19    int total = 0, picked = 0;20    // Always grow the tree along the cheapest crossing edge21    while (!pq.empty() && picked < n) {22        auto [w, u] = pq.top();23        pq.pop();24        if (inMST[u]) continue;25        inMST[u] = true;26        total += w;27        ++picked;28        std::cout << "Add node " << u << " (edge weight " << w << ")\n";29        for (auto [v, weight] : adj[u]) {30            if (!inMST[v]) pq.push({weight, v});31        }32    }33    std::cout << "MST total weight: " << total << "\n";34    return 0;35}

1#include <stdbool.h>2#include <stdio.h>3
4#define N 55#define INF 10000000006
7int main(void) {8    // Undirected weighted graph: w[u][v] = 0 means no edge9    int w[N][N] = {10        {0, 2, 0, 6, 0},11        {2, 0, 3, 8, 5},12        {0, 3, 0, 0, 7},13        {6, 8, 0, 0, 0},14        {0, 5, 7, 0, 0},15    };16    int key[N], parent[N];17    bool inMST[N] = {false};18    for (int v = 0; v < N; v++) {19        key[v] = INF;20        parent[v] = -1;21    }22    key[0] = 0;23    int total = 0;24    // O(V^2) scan for the cheapest crossing edge (no heap needed here)25    for (int iter = 0; iter < N; iter++) {26        int u = -1;27        for (int v = 0; v < N; v++) {28            if (!inMST[v] && (u == -1 || key[v] < key[u])) u = v;29        }30        inMST[u] = true;31        total += key[u];32        if (parent[u] != -1) {33            printf("Add edge %d - %d (weight %d)\n", parent[u], u, key[u]);34        }35        for (int v = 0; v < N; v++) {36            if (w[u][v] > 0 && !inMST[v] && w[u][v] < key[v]) {37                key[v] = w[u][v];38                parent[v] = u;39            }40        }41    }42    printf("MST total weight: %d\n", total);43    return 0;44}