Prim算法、Kruskal算法构造最小生成树（C语言）

问题

给定一个边权重的连通图，以点1为起点，构建一个能将图中所有定点连接起来，且边权重和最小的图。

解析

prim算法

prim算法的核心是从起始点开始，每次选择到已有点路径距离最短的点连接，但不能成环。实现示意图如下：(图中右下角1应当为6) 这样一个图我们选取点1为起始点： step 1： step2： step3: step4: step5:

kruskal算法

与prim算法的目的相同，但kruskal算法选择边，即每次选择图中权重最小的边，值得注意的是，所选的边在图中不能构成环。解析图示如下所示：

step1： step2: step3: step4: step5:

设计

prim

设计两个辅助数组（lowCost[ ]，source[ ]）

lowCost:用于存储当前已经生成的点图到其他点的距离，可以连通则为具体数值，无法连通则为无穷（此处假设所有权重都小于设置的最大值） source：用于记录当前lowCost值是由哪个点决定的，更新lowCost数组，source数组的值也要更新。 核心代码：

void Prim(Graph graph){
          
   
    int lowCast[graph->nv];
    int source[graph->nv];
    lowCast[0] = 0;
    source[0] = 1;
    int k = 0;

    for (int i = 1; i <graph->nv ; i++) {
          
   
        lowCast[i] = graph->G[0][i];
        source[i] = 1;
    }

    for (int i = 1; i < graph->nv; ++i) {
          
   
        int min = 20200821;
        int j = 0;
        while (j<graph->nv){
          
   
            if (lowCast[j]!=0&&lowCast[j]<min){
          
   
                min = lowCast[j];
                k = j;
            }
            j++;
        }
        fprintf(fp2,"%d-->%d
",source[k],k+1);
        lowCast[k] = 0;
        //更新lowCast表
        for (int o = 0; o < graph->nv; ++o) {
          
   
            if (lowCast[o]!=0&&graph->G[k][o]<lowCast[o]){
          
   
                lowCast[o] = graph->G[k][o];
                source[o] = k+1;
            }
        }
    }
}

kruskal算法

当图较为稀疏时，kruskal是较为高效的算法，配合使用并查集将提高其效率。并查集通过递归寻找父节点，通过父节点是否相同来察看是否是同一个父节点来察看是否是会形成环。 核心代码：

int find(int x)
{
          
   
    if (f[x]!=x)
        f[x]=find(f[x]);
    return f[x];
}
bool merge(int t1,int t2)
{
          
   
    int r1=find(t1);
    int r2=find(t2);
    if (r1!=r2)
    {
          
   
        f[r1]=r2;
        return true;
    }
    return false;
}
bool cmp(ENode a,ENode b)
{
          
   
    return a.weight<b.weight;
}

void Kruskal(FILE *fp,FILE *fp2){
          
   
    int i,j;
    fscanf(fp,"%d%d",&n,&m);
    for (i=1;i<=m;i++)
        fscanf(fp,"%d%d%d",&a[i].v1,&a[i].v2,&a[i].weight);
    sort(a+1,a+m+1,cmp);
    for (i=1;i<=n;i++)
        f[i]=i;
    for (i=1;i<=m;i++)
    {
          
   
        if (merge(a[i].v1,a[i].v2))
        {
          
   
            sum++;
            fprintf(fp2,"%d-->%d: %d
",a[i].v1,a[i].v2,a[i].weight);
        }
        if (sum==n-1)
            break;
    }
    for (i=1;i<=n;i++)
        if (f[i]==i)
            k++;
}

测试样例input.txt

6 10
1 2 6
1 3 1
1 4 5
2 1 6
2 3 5
2 5 3
3 1 1
3 2 5
3 4 5
3 5 6
3 6 4
4 1 5
4 3 5
4 6 2
5 2 3
5 3 6
5 6 6
6 3 4
6 4 2
6 5 6
6 10
1 3 1
1 2 6
1 4 5
2 3 5
4 3 5
2 5 3
4 6 2
3 5 6
3 6 4
5 6 6

输出样例output.txt

Prim: 
1-->3
3-->6
6-->4
3-->2
2-->5
Kruskal: 
1-->3: 1
4-->6: 2
2-->5: 3
3-->6: 4
2-->3: 5

分析

时间复杂度：

prim：O(n3+n) kruska:O(n)