普里姆(Prim)算法

定义：假设N = {P,{E}}是连通网，TE是N上最小生成树中边的集合。算法从U={u0}(u0∈V),TE={}开始。重复执行下述操作：在所有u∈U,v∈V-U的边(u,v)∈E中找一条代价最小的边(u0,v0)并入TE，同时v0并入U，直到U=V为止。此时TE中必有n-1条边，则T=(V,{TE})为N的最小生成树。

一句话概括：从一个顶点v0出发，找当前已纳入最小生成树的整体向外扩散的最小权值，直到所有顶点均被纳入最小生成树为止。

mark

代码：

void MiniSpanTree_Prim (MGraph G)
{
    int adjvex[MAXVEX];//保存相关顶点下标
    //adjvex[0]=1意思为边(v0,v1)在最小生成树中
    int lowcost[MAXVEX];//保存相关顶点间边的权值
    //lowcost[i]的值为0即下标为i的顶点加入最小生成树
    
    lowcost[0] = 0;//v0加入生成树
    adjvex[0] = 0;//初始化第一个顶点下标为0
    for (int i = 1;i < G.numVertexes;i++)
    {
        lowcost[i] = G.arc[0][i];//将与v0顶点相连的边的权值存入
        adjvex[i] = 0;//初始化都为v0的下标
    }
    
    //以上全为初始化操作
    
    for (i = 1;i < G.numVertexes;i++)
    {
        int min = INFINITY;//初始化最小权值为∞，用65535代替
        int j = 1;int k = 0;
        
        while (j < G.numVertexes)
        {
            if (lowcost[j] != 0 && lowcost[j] < min)
            {
            //顶点j不在最小生成树中且整体到顶点j的所有边中最小权值小于min
                min = lowcost[j];//让当前权值成为最小值
                k = j;//将当前最小值下标存入k
            }
            j++;
        }
        
        //该循环用于寻找当前整体向外扩散的最小值
        
        printf("(%d,%d)",adjvex[k],k);//打印当前顶点边中权值最小边
        lowcost[k] = 0;//将当前顶点纳入最小生成树
        for (int j = 1;j < G.numVertexes;j++)
        {
            if (lowcost[j] != 0 && G.arc[k][j] < lowcost[j])
            {
            //若下标为k的顶点各边的权值小于该顶点被加入最小生成树前整体到这些顶点的最小权值
                lowcost[j] = G.arc[k][j];
                adjvex[j] = k;//将下标为k的顶点存入adjvex
            }
        }
        //该循环用于将新增顶点向外扩散的权值与原整体向外扩散的权值比较后取最小权值更新lowcost数组
    }
}

由循环嵌套可知时间复杂度为O(n²)。

克鲁斯卡尔(Kruskal)算法

定义：假设N = {P,{E}}是连通网，则令最小生成树的初始状态为只有n个顶点而无边的非连通图T={V,{}},图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依次类推，直到所有顶点都在同一连通分量上为止。

这里采用边集数组：

typedef struct
{
    int begin;
    int end;
    int weight;
}Edge;

mark

代码：

void MiniSpanTree_Kruskal (MGraph G)
{
    int n,m;
    Edge edges[MAXVEX];//定义边集数组
    int parent[MAXVEX];//定义一数组来判断边与边是否形成环路
    //此处省略将邻接矩阵转化为边集数组且按权由小到大排序的代码
    for (int i = 0;i < G.numVertexes;i++)
        parent[i] = 0;//初始化数组为0
    for (int i = 0;i < G.numEdges;i++)//循环每一条边
    {
        n = Find(parent,edges[i],begin);
        m = Find(parent,edges[i],end);
        if (n != m)//若n!=m说明此边没有与现有生成树形成环路
        {
            parent[n] = m;
            //将此边的结尾顶点放入下标为起点的parent中，表示该顶点已经在生成树集合中
            //例如parent[5]=8表示v5和v8都在生成树集合中且在同一个连通分量中
            printf("(%d,%d) %d",edges[i].begin,edges[i].end,edges[i].weight);
        }
    }
}

int Find (int *parent,int f)
{
    while (parent[f] > 0)//将"两个数组在一个连通分量中"这一结论用数组中的空闲位置来表达
        f = parent[f];
    return f;
}

理解：例如当i = 6时parent数组为:{1,5,8,7,7,8,0,0,6},从parent[0] = 1开始可构建两条指针链： mark

可以认为每个连通分量只提供一个指向parent数组中值为0的项的API接口，若某条边能够形成环路，则其begin和end端经过Find函数后得到的n和m必定相等，此即为判断一条边是否满足要求的判断依据。

此算法的Find函数由边数e决定，时间复杂度为O(loge),而外面有一个for循环e次，故Kruskal算法的时间复杂度为O(eloge)。(先记下，以后再想原因)

Kruskal算法主要针对边来展开，边数少时效率非常高，对于稀疏图有很大优势；Prim算法对于稠密图，即边数非常多的情况会更有优势。