37.2° Blog

1.基本概念

1.1 生成树

连通图的生成树是包含图中全部顶点的一个极小连通子图；

对于一个带权连通无向图G=(V, E)，生成树不同，每颗树的权也不同；

1.2 最小生成树

设R为G的所有生成树的集合，若T为R中边的权值之和最小的生成树，则T称为G的最小生成树（MST）

1.3 最小生成树特性

• 最小生成树可能有多个，但边的权值之和是唯一且最小的
• 最小生成树的变数 = 顶点树 - 1
• 若连通图本身就是一棵树，则其最小生成树就是它本身
• 只有连通图才有生成树，非连通图只有生成森林

2.Prim算法

2.1 算法思想

• 从某一个顶点开始构建生成树；
• 每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止

2.2 特点

• 时间复杂度：O(|V|^2)
• 适合用于边稠密图

2.3 伪代码

void Prim(G, T)
{
    T = NULL;    // 初始化空树
    U = {w};    // 添加任一顶点w
    while((V - U) != NULL)  // 若树中不含全部顶点
    {
        设(u, v)是使 u属于U 与 v属于(V-U) ，且权值最小的边
        T = T 并 {(u, v)};  // 边归入树
        U = U 并 {v};    // 顶点归入树
    }
}

3.Kruskal算法

3.1 算法思想

• 从某一个顶点开始构建生成树；
• 每次选择一条权值最小的边，使这条边的两头连通（原本已经连通的就不选），
• 直到所有结点都连通；

2.2 特点

• 时间复杂度：O(|E|log|E|)
• 适合用于边稀疏图

2.3 伪代码

void Kruskal(V, T)
{
    T = V;      // 初始化树T，仅含顶点
    numS = n;    // 连通分量数
    while(numS > 1)  // 若连通分量数大于1
    {
        从E中取出权值最小的边(u, v)
        if(v和u属于T中不同的连通分量)
        {
            T = T 并 {(v, u)};  // 将此边加入生成树中
            numS--;        // 连通分量数减1
        }
    }
}