假设要在n个城市之间建立通信联络网，则联通n个城市需要n-1条线路。这时需要考虑如何建设才能最省钱呢？用连通网来表示n个城市及n个城市间可能设置的通信线路，其中网的顶点表示城市，边表示城市间的线路，边的权值表示建造这条线路的花费。对于n个顶点的连通网可以建立许多不同的生成树，每棵生成树都可以是一个通信网，选择一棵总耗费最小的生成树，就是最小代价生成树（最小生成树minimum cost spanning tree）。一棵生成树的代价就是树上各边的代价之和。
下面介绍构造最小生成树的算法。
一、普里姆（Prim）算法
1、算法思想

image.png

上图为原始的连通网，从中选取合适的路径构造最小生成树。
初始时：属于最小生成树的顶点集合U = { }
不属于最小生成树的集合V = {v1、v2、v3、v4、v5、v6}
设置两个数据结构：
lowcost[i]：表示以i为终点的边的最小权值，lowcost[i] = 0表示以i为终点的边的最小权值为0，也就说i点加入了最小生成树。
mst[i]：表示对应lowcost[i]那条边的起点，（mst[i]，i）表示的就是最小生成树的一条边，当mst[i] = 0表示起点i加入了最小生成树。

第一步：选择顶点v1作为起始点
这时：属于最小生成树的顶点集合U = {v1}
不属于最小生成树的集合V = {v2、v3、v4、v5、v6}
以顶点v1作为起点的边有（1，2），（1，3），（1，4），也就是终端点为2，4，5，
把权值赋到lowcost中，lowcost[2]=6，lowcost[3]=1，lowcost[4]=5，lowcost[5]=，lowcost[6]=，（*代表无限大，即无通路）
mst赋默认值：mst[2]=1，mst[3]=1，mst[4]=1，mst[5]=1，mst[6]=1

image.png

image.png

image.png

image.png

2、算法

int prim(int graph[][MAX], int n)  {  
    int lowcost[MAX];  
    int mst[MAX];  
    int i, j, min, minid, sum = 0;  
    for (i = 2; i <= n; i++)  {  //lowcost赋值为起点为v1的边的权值
        lowcost[i] = graph[1][i];  
        mst[i] = 1;  
    }  
    mst[1] = 0;  //顶点v1加入集合
    for (i = 2; i <= n; i++)  {  
        min = MAXCOST;  
        minid = 0;  
        for (j = 2; j <= n; j++)   {  
          //找到未被访问的，且权值最小的顶点
            if (lowcost[j] < min && lowcost[j] != 0)  {  
                min = lowcost[j];  
                minid = j;  
            }  
        }  
        sum += min;  
        lowcost[minid] = 0;  //加入集合
        for (j = 2; j <= n; j++)   {  
          //更新lowcost，mst
            if (graph[minid][j] < lowcost[j])  {  
                lowcost[j] = graph[minid][j];  
                mst[j] = minid;  
            }  
        }  
    }  
    return sum;  
}  

算法复杂度为O（n2），与网中的边数无关，适用于求边稠密的网的最小生成树。

二、克鲁斯卡尔（Kruskal）算法
1、算法思想
（1）一个有n个顶点的连通网络N = (V, {E})，最初先构造一个只有n个顶点，没有边的非连通图T = {V, {ф}}，图中每个顶点自成一格连通分量。
（2）在Ｅ中选择一条具有最小权植的边，若该边的两个顶点落在T中不同的连通分量上，则将此边加入到Ｔ中；否则将此边舍去，重新选择一条权植最小的边。
（3）以此类推，直到T中所有顶点在同一连通分量上为止。

image.png

上图为原始的连通网，从中选取合适的路径构造最小生成树。
第一步：只有6个顶点而没有边的非连通图，每个顶点都是一个连通分量，一共有6个（红色圆圈）

image.png

第二步：选择一条权值最小的边（v1，v3），这条边连接了两个连通分量，因此连通分量变成了5个

image.png

image.png

image.png

第五步：在剩下的边中，再选择一条权值最小的边（v3， v6），这条边连接了两个连通分量，也没有构成回路，所以是符合要求的，这时连通分量变成了2个

image.png

image.png