C语言实现最小生成树算法 - Kruskal算法

C语言实现最小生成树算法 - Kruskal算法

问题描述

给定一个带权无向连通图，要求找出一棵生成树，使得生成树上所有边的权值之和最小。

求解算法

破圈法（Kruskal算法）。该算法基于贪心策略，每次选择当前最小的边，如果加入该边不会形成环，则将其加入生成树，否则将其删除。具体实现中，可以使用并查集来判断两个顶点是否在同一个集合中，从而判断是否会形成环。最终，生成树上所有边的权值之和即为最小值。

代码实现

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

#define MAX_VERTEX_NUM 100 //最大顶点数
#define MAX_EDGE_NUM 100 //最大边数

//边结构体
typedef struct {
    int tail; //边的起点
    int head; //边的终点
    int weight; //边的权值
} Edge;

//图结构体
typedef struct {
    int vertexNum; //顶点数
    int edgeNum; //边数
    Edge edges[MAX_EDGE_NUM]; //边数组
} Graph;

//并查集结构体
typedef struct {
    int parent[MAX_VERTEX_NUM]; //父节点数组
    int rank[MAX_VERTEX_NUM]; //秩数组
} UnionFindSet;

//初始化并查集
void MakeSet(UnionFindSet *set, int n) {
    for (int i = 0; i < n; i++) {
        set->parent[i] = i;
        set->rank[i] = 0;
    }
}

//查找节点所在集合的代表元
int Find(UnionFindSet *set, int x) {
    if (set->parent[x] != x) {
        set->parent[x] = Find(set, set->parent[x]);
    }
    return set->parent[x];
}

//合并两个集合
void Union(UnionFindSet *set, int x, int y) {
    int xRoot = Find(set, x);
    int yRoot = Find(set, y);
    if (xRoot == yRoot) {
        return;
    }
    if (set->rank[xRoot] < set->rank[yRoot]) {
        set->parent[xRoot] = yRoot;
    } else if (set->rank[xRoot] > set->rank[yRoot]) {
        set->parent[yRoot] = xRoot;
    } else {
        set->parent[yRoot] = xRoot;
        set->rank[xRoot]++;
    }
}

//边比较函数，用于排序
int cmp(const void *a, const void *b) {
    Edge *e1 = (Edge *)a;
    Edge *e2 = (Edge *)b;
    return e1->weight - e2->weight;
}

//破圈法求最小生成树
void Kruskal(Graph *graph) {
    //按权值从小到大排序
    qsort(graph->edges, graph->edgeNum, sizeof(Edge), cmp);
    //初始化并查集
    UnionFindSet set;
    MakeSet(&set, graph->vertexNum);
    //记录删除的边
    Edge removedEdges[MAX_EDGE_NUM];
    int removedEdgeNum = 0;
    //遍历所有边
    for (int i = 0; i < graph->edgeNum; i++) {
        Edge e = graph->edges[i];
        //如果边的两个端点不在同一个集合中，说明不会形成环，可以加入最小生成树中
        if (Find(&set, e.tail) != Find(&set, e.head)) {
            Union(&set, e.tail, e.head);
            printf('边 (%d, %d) 权值为 %d 加入最小生成树\n', e.tail, e.head, e.weight);
        } else {
            //否则，删除边
            removedEdges[removedEdgeNum++] = e;
        }
    }
    //输出删除的边
    printf('删除的边：\n');
    for (int i = 0; i < removedEdgeNum; i++) {
        Edge e = removedEdges[i];
        printf('(%d, %d) 权值为 %d\n', e.tail, e.head, e.weight);
    }
}

int main() {
    int n, m; //顶点数和边数
    Graph graph;
    printf('请输入顶点数和边数：');
    scanf('%d %d', &n, &m);
    graph.vertexNum = n;
    graph.edgeNum = m;
    printf('请输入每条边的起点、终点和权值：\n');
    for (int i = 0; i < m; i++) {
        Edge e;
        scanf('%d %d %d', &e.tail, &e.head, &e.weight);
        graph.edges[i] = e;
    }
    Kruskal(&graph);
    return 0;
}

代码解析

1. 结构体定义：定义了边结构体Edge、图结构体Graph和并查集结构体UnionFindSet。
2. 并查集操作：定义了MakeSet、Find和Union三个函数，分别用于初始化并查集、查找节点所在集合的代表元和合并两个集合。
3. 边比较函数：定义了cmp函数，用于比较两个边的权值大小，以便对边进行排序。
4. Kruskal算法实现：在Kruskal函数中，首先将所有边按权值从小到大排序，然后使用并查集判断每条边是否会形成环，如果不会形成环，则将其加入最小生成树，否则将其删除。
5. 主函数：在主函数中，输入顶点数、边数和每条边的信息，然后调用Kruskal函数求最小生成树。

总结

Kruskal算法是求解最小生成树的经典算法，该算法易于理解和实现，时间复杂度为O(ElogE)，其中E为边数。本文提供了一个C语言实现的示例，供读者参考学习。