本文共 1952 字，大约阅读时间需要 6 分钟。

最小生成树的普里姆算法和克鲁斯卡尔算法

最小生成树是多重图中连接所有顶点的边的子集，且该子集中任意两顶点之间都有一条 edges ，并且边的权重之和最小。找到最小生成树的算法有两种主要方法：普里姆算法和克鲁斯卡尔算法。本文将详细介绍这两种算法的实现方法。

普里姆算法的基本思路是通过“枚举”法一步步加入最小边，直到形成包含所有顶点的树。具体步骤如下：

以下是普里姆算法在代码中的实现示例：

#include 
   
    
#include 
    
     
#include "graph.h"
void Prim(MGraph g, int v) {
    int lowcost[MAXV]; // 是否包含顶点i
    int min;
    int closest[MAXV], i, j, k;
    for (i = 0; i < MAXV; i++) {
        lowcost[i] = INFINITY;
    }
    closest[v] = 0;
    lowcost[v] = 0;
    for (i = 0; i < MAXV; i++) {
        min = INFINITY;
        j = v;
        for (k = 0; k < MAXV; k++) {
            if (lowcost[k] < lowcost[j]) {
                min = lowcost[k];
                j = k;
            }
        }
        for (k = 0; k < MAXV; k++) {
            if (lowcost[k] == min) {
                closest[k] = j;
                lowcost[k] += weight[ j ][ k ];
            }
        }
    }
}
    
   

克鲁斯卡尔算法则通过“裁剪”现有的边来构建生成树。其基本步骤如下：

具体代码实现如下：

#include 
   
    
#include 
    
     
#include "graph.h"
void Kruskal(MGraph g, int n) {
    Edge edges[MAXEDGES];
    int i, j, k, min_edge_weight;
    Edgesort(edges, n, min_edge_weight);
    
    int Uindx[MAXV], Vindx[MAXV];
    Uindx[n] = Vindx[n] = -1;
    
    for (j = 1; j < n; j++) {
        for (i = 0; i < edges[j].v; i++) {
            if (Uindx[edges[i].u] == -1 && Vindx[edges[i].v] == -1) {
                Uindx[edges[i].u] = Uindx[edges[i].v] = ++current_union;
            } else if (Uindx[edges[i].u] > Uindx[edges[i].v]) {
                Uindx[edges[i].u] = Vindx[edges[i].v];
            } else {
                Vindx[edges[i].v] = Uindx[edges[i].u];
            }
        }
    }
}
    
   

注：Edgesort 和相关辅助函数负责对边按权重排序和管理并查集。

整个算法的实现核心在于如何高效地维护边的访问状态和连通部分。若图规模较大，可进一步优化数据结构以提升性能。