C语言实现破圈法求解带权连通图的最小生成树

#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;
}