最小生成树

定义

在无向图中求一棵满足如下条件的树

• $n$个顶点，$n-1$条边
• 无环
• 连通所有点
• 边权和最小

性质

连通性

生成树上，任意两点之间有且仅有一条简单路径。

• 少一条边：不连通
• 多一条边：出现环，路径不唯一

最小代价性

在所有极小连通结构中，选一个总代价最小的。

最大路径最小性

在所有极小连通结构中，选一个最长路径最短的。

实现算法

Prim算法（加点法）

Kruskal算法（加边法）

Boruvka算法

附录

Edge定义

struct Edge {
    int u, v, w;
    // 重载 < 用于排序
    bool operator < (const Edge& e) const {
        return w < e.w;
    }
};

Node定义

struct Node {
    int v, w;
    // 重载 > 用于优先队列（因为用greater）
    bool operator > (const Node& n) const {
        return w > n.w;
    }
    // 构造函数
    Node(int v, int w) : v(v), w(w) {}
};