克鲁斯卡尔(Kruskal )算法——求最小生成树贪心算法

克鲁斯卡尔算法是一种用于求解最小生成树问题的贪心算法。最小生成树是一个连通图的生成树，其边的权重之和最小。

一、原理

克鲁斯卡尔算法的核心思想是按照边的权重从小到大逐渐选择连通图的边，直到所有顶点都被连接为止。在每一步中，选择当前权重最小的边，若该边的两个顶点尚未连接，则将其添加到最小生成树的边集合中，并将这两个顶点归为同一个连通分量。通过不断地选择权重最小的边，保证了最小生成树的边权重之和最小。

二、步骤

下面是克鲁斯卡尔算法的具体步骤：

1. 创建一个空的最小生成树的边集合。
2. 将图中的所有边按权重从小到大进行排序。
3. 遍历排序后的边集合，依次选择权重最小的边。
4. 若该边的两个顶点尚未在最小生成树的边集合中相连（即添加该边不会形成环），则将该边添加到最小生成树的边集合中，并将这两个顶点归为同一个连通分量。
5. 重复步骤3和步骤4，直到最小生成树的边数等于顶点数减1或者遍历完所有边。

假设遍历到一条由顶点 A 和 B 构成的边，而顶点 A 和顶点 B 标记不同，此时不仅需要将顶点 A 的标记更新为顶点 B 的标记，还需要更改所有和顶点 A 标记相同的顶点的标记，全部改为顶点 B 的标记。

图 1

连通网例如，使用克鲁斯卡尔算法找图 1 的最小生成树的过程为：

首先，在初始状态下，对各顶点赋予不同的标记（用颜色区别），如下图所示：

（1）

对所有边按照权值的大小进行排序，按照从小到大的顺序进行判断，首先是（1，3），由于顶点 1 和顶点 3 标记不同，所以可以构成生成树的一部分，遍历所有顶点，将与顶点 3 标记相同的全部更改为顶点 1 的标记，如（2）所示：

（2）

其次是（4，6）边，两顶点标记不同，所以可以构成生成树的一部分，更新所有顶点的标记为：

（3）

其次是（2，5）边，两顶点标记不同，可以构成生成树的一部分，更新所有顶点的标记为：

（4）

然后最小的是（3，6）边，两者标记不同，可以连接，遍历所有顶点，将与顶点 6 标记相同的所有顶点的标记更改为顶点 1 的标记：

（5）

继续选择权值最小的边，此时会发现，权值为 5 的边有 3 个，其中（1，4）和（3，4）各自两顶点的标记一样，如果连接会产生回路，所以舍去，而（2，3）标记不一样，可以选择，将所有与顶点 2 标记相同的顶点的标记全部改为同顶点 3 相同的标记：

（6）

当选取的边的数量相比与顶点的数量小 1 时，说明最小生成树已经生成。所以最终采用克鲁斯卡尔算法得到的最小生成树为（6）所示。

三、应用场景

克鲁斯卡尔算法在许多实际问题中都有广泛的应用，尤其是在网络设计和图像分割等领域。以下是一些常见的应用场景：

1. 网络布线：在进行网络设计时，需要确定最优的布线方案，以便使得网络的总长度最小。克鲁斯卡尔算法可以帮助我们选择连接各节点的最短路径，从而实现网络的最优布线。
2. 铁路规划：在铁路交通规划中，需要确定一条连接各个城市的最短线路，以便在建设过程中节约资源和成本。克鲁斯卡尔算法可以帮助我们选择连接各城市的最短线路，从而实现铁路规划的最优化。
3. 图像分割：在图像处理中，图像分割是一项重要任务，其目的是将图像划分为不同的区域，以便进行后续的处理。克鲁斯卡尔算法可以帮助我们选择图像中各个区域的最短边界，从而实现图像的有效分割。

四、代码示例

以下是实现的克鲁斯卡尔算法的示例代码：

#include <stdio.h>
#include <stdlib.h>

// 边的结构体
struct Edge {
    int src, dest, weight;
};

// 图的结构体
struct Graph {
    int V, E;
    struct Edge* edge;
};

// 创建一个图
struct Graph* createGraph(int V, int E) {
    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
    graph->V = V;
    graph->E = E;
    graph->edge = (struct Edge*) malloc(E * sizeof(struct Edge));
    return graph;
}

// 并查集的操作
int find(int parent[], int i) {
    if (parent[i] == -1)
        return i;
    return find(parent, parent[i]);
}

void unionSet(int parent[], int x, int y) {
    parent[x] = y;
}

// 按权重对边进行排序
void sortEdges(struct Graph* graph) {
    int i, j;
    for(i = 0; i < graph->E - 1; i++) {
        for(j = 0; j < graph->E - i - 1; j++) {
            if(graph->edge[j].weight > graph->edge[j + 1].weight) {
                struct Edge temp = graph->edge[j];
                graph->edge[j] = graph->edge[j + 1];
                graph->edge[j + 1] = temp;
            }
        }
    }
}

// 执行克鲁斯卡尔算法
void kruskalMST(struct Graph* graph) {
    int V = graph->V;
    struct Edge result[V];
    int e = 0;
    int i = 0;

    sortEdges(graph);

    int parent[V];
    for(i = 0; i < V; i++) {
        parent[i] = -1;
    }

    i = 0;
    while (e < V - 1) {
        struct Edge nextEdge = graph->edge[i++];
        int x = find(parent, nextEdge.src);
        int y = find(parent, nextEdge.dest);
        
        if(x != y) {
            result[e++] = nextEdge;
            unionSet(parent, x, y);
        }
    }

    printf("边   权重\n");
    for (i = 0; i < e; i++)
        printf("%d - %d   %d\n", result[i].src, result[i].dest, result[i].weight);
}

// 测试
int main() {
    int V = 4;  // 图的顶点数
    int E = 5;  // 图的边数
    struct Graph* graph = createGraph(V, E);

    // 添加边
    graph->edge[0].src = 0;
    graph->edge[0].dest = 1;
    graph->edge[0].weight = 10;

    graph->edge[1].src = 0;
    graph->edge[1].dest = 2;
    graph->edge[1].weight = 6;

    graph->edge[2].src = 0;
    graph->edge[2].dest = 3;
    graph->edge[2].weight = 5;

    graph->edge[3].src = 1;
    graph->edge[3].dest = 3;
    graph->edge[3].weight = 15;

    graph->edge[4].src = 2;
    graph->edge[4].dest = 3;
    graph->edge[4].weight = 4;

    kruskalMST(graph);

    return 0;
}

以上是使用C语言实现克鲁斯卡尔算法的示例代码。你可以根据自己的需求修改图的顶点数、边数以及边的权重，并运行代码查看最小生成树的结果。

五、时间复杂度和空间复杂度的分析

时间复杂度：

• 对边按权重进行排序的时间复杂度为 O(ElogE)，其中 E 是边的数量。
• 在并查集中查找和合并的时间复杂度近似为 O(logV)，其中 V 是顶点的数量。
• 所以，整个克鲁斯卡尔算法的时间复杂度为 O(ElogE + ElogV)。
• 在稀疏图中，E 接近于 V^2，因此可以简化为 O(ElogV)。

空间复杂度：

• 创建并查集的额外空间复杂度为 O(V)，其中 V 是顶点的数量。
• 存储边的结构体数组需要 O(E) 的空间。
• 因此，整个克鲁斯卡尔算法的空间复杂度为 O(V + E)。

需要注意的是，克鲁斯卡尔算法通常适用于稀疏图，即边的数量相对于顶点数量较少的情况。在密集图中，即边的数量接近顶点数量的平方时，使用其他算法（如普里姆算法）可能更有效率。

六、总结

本文介绍了克鲁斯卡尔算法的原理、步骤以及应用场景。克鲁斯卡尔算法是一种贪心算法，通过不断选择权重最小的边来构建最小生成树。它在网络设计、铁路规划、图像分割等领域有广泛的应用。

文章部分引用：data.biancheng.net