• 日期: 2028-09-15
  • 标签: 常规

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

#define MAX_VERTEX_NUM 100 // 最大顶点数 #define INF 32767 // 表示无穷大的值

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

typedef struct { int vex[MAX_VERTEX_NUM]; // 存储顶点 int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边的权值 int vexNum; // 顶点数 int edgeNum; // 边数 } Graph; // 图的结构体

void initGraph(Graph* graph) { int i, j; for (i = 0; i < MAX_VERTEX_NUM; i++) { for (j = 0; j < MAX_VERTEX_NUM; j++) { graph->edge[i][j] = INF; } } graph->vexNum = 0; graph->edgeNum = 0; }

int find(int* parent, int f) { while (parent[f] > 0) { f = parent[f]; } return f; }

void kruskal(Graph graph, Edge* mst) { int i, j, k, n, m; int parent[MAX_VERTEX_NUM] = { 0 }; // 存储每个顶点的父节点 Edge* edgeList = (Edge*)malloc(sizeof(Edge) * graph.edgeNum); // 存储所有边的列表 k = 0; // 边的数量 for (i = 0; i < graph.vexNum; i++) { for (j = i + 1; j < graph.vexNum; j++) { if (graph.edge[i][j] != INF) { // 存储所有的边 edgeList[k].vex1 = i; edgeList[k].vex2 = j; edgeList[k].weight = graph.edge[i][j]; k++; } } } for (i = 0; i < k; i++) { // 对所有边按权值从小到大排序 for (j = i + 1; j < k; j++) { if (edgeList[i].weight > edgeList[j].weight) { Edge temp = edgeList[i]; edgeList[i] = edgeList[j]; edgeList[j] = temp; } } } k = 0; // 选中的边的数量 for (i = 0; i < graph.edgeNum; i++) { int parentVex1 = find(parent, edgeList[i].vex1); int parentVex2 = find(parent, edgeList[i].vex2); if (parentVex1 != parentVex2) { // 如果两个顶点的父节点不同，说明它们不在同一个集合中 parent[parentVex1] = parentVex2; // 将它们合并到同一个集合中 mst[k++] = edgeList[i]; // 将该边加入最小生成树 if (k == graph.vexNum - 1) { // 最小生成树的边数等于顶点数减1时结束 break; } } } free(edgeList); }

int main() { Graph graph; Edge mst[MAX_VERTEX_NUM - 1]; int i, j; initGraph(&graph); printf("请输入顶点数和边数："); scanf("%d%d", &graph.vexNum, &graph.edgeNum); printf("请输入顶点："); for (i = 0; i < graph.vexNum; i++) { scanf("%d", &graph.vex[i]); } printf("请输入边及其权值：\n"); for (i = 0; i < graph.edgeNum; i++) { int vex1, vex2, weight; scanf("%d%d%d", &vex1, &vex2, &weight); graph.edge[vex1][vex2] = weight; graph.edge[vex2][vex1] = weight; // 无向图的边是双向的 } kruskal(graph, mst); printf("最小生成树的边及其权值为：\n"); for (i = 0; i < graph.vexNum - 1; i++) { printf("(%d, %d) %d\n", graph.vex[mst[i].vex1], graph.vex[mst[i].vex2], mst[i].weight); } return 0; }

// 以下是代码的讲解内容：

Kruskal 算法是求解带权连通图的最小生成树的一种算法。它的基本思想是：将图中的所有边按照权值从小到大排序，然后从小到大依次加入边，如果加入一条边会形成环，则不加入这条边。直到加入 n-1 条边为止，其中 n 是图中的顶点数，这 n-1 条边就构成了最小生成树。

代码中使用的两个结构体：

  1. Edge 结构体

Edge 结构体表示边，包括边的起点 vex1，边的终点 vex2，边的权值 weight。它的定义如下：

typedef struct {
    int vex1; // 边的起点
    int vex2; // 边的终点
    int weight; // 边的权值
} Edge;
  1. Graph 结构体

Graph 结构体表示图，包括存储顶点的数组 vex，存储边权值的二维数组 edge，以及顶点数 vexNum 和边数 edgeNum。它的定义如下：

typedef struct {
    int vex[MAX_VERTEX_NUM]; // 存储顶点
    int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边的权值
    int vexNum; // 顶点数
    int edgeNum; // 边数
} Graph;

其中 MAX_VERTEX_NUM 定义了最大顶点数，INF 定义了无穷大的值，可以根据需要进行调整。

Kruskal 算法的具体实现：

  1. 初始化图

在初始化图时，将所有边的权值初始化为 INF，顶点数和边数初始化为 0。代码如下：

void initGraph(Graph* graph) {
    int i, j;
    for (i = 0; i < MAX_VERTEX_NUM; i++) {
        for (j = 0; j < MAX_VERTEX_NUM; j++) {
            graph->edge[i][j] = INF;
        }
    }
    graph->vexNum = 0;
    graph->edgeNum = 0;
}
  1. 查找父节点

在 Kruskal 算法中，需要查找每个顶点的父节点。这里使用了一个 find 函数来实现，它的参数是一个 parent 数组和一个顶点的编号，返回该顶点的父节点编号。它的实现如下：

int find(int* parent, int f) {
    while (parent[f] > 0) {
        f = parent[f];
    }
    return f;
}

这个函数的实现思路是：如果一个顶点的父节点编号大于 0，说明它不是根节点，继续向上查找，直到找到根节点。根节点的父节点编号为负数，例如 -1。

  1. Kruskal 算法的实现

在 Kruskal 算法中，需要进行以下几个步骤：

  • 将所有边存储到 edgeList 数组中，并按权值从小到大排序。
  • 依次从 edgeList 数组中取出边，判断它们的起点和终点是否在同一个集合中，如果不在同一个集合中，将它们合并到同一个集合中，并将该边加入最小生成树中。
  • 当最小生成树的边数等于顶点数减 1 时，结束循环。

具体实现如下：

void kruskal(Graph graph, Edge* mst) {
    int i, j, k, n, m;
    int parent[MAX_VERTEX_NUM] = { 0 }; // 存储每个顶点的父节点
    Edge* edgeList = (Edge*)malloc(sizeof(Edge) * graph.edgeNum); // 存储所有边的列表
    k = 0; // 边的数量
    for (i = 0; i < graph.vexNum; i++) {
        for (j = i + 1; j < graph.vexNum; j++) {
            if (graph.edge[i][j] != INF) { // 存储所有的边
                edgeList[k].vex1 = i;
                edgeList[k].vex2 = j;
                edgeList[k].weight = graph.edge[i][j];
                k++;
            }
        }
    }
    for (i = 0; i < k; i++) { // 对所有边按权值从小到大排序
        for (j = i + 1; j < k; j++) {
            if (edgeList[i].weight > edgeList[j].weight) {
                Edge temp = edgeList[i];
                edgeList[i] = edgeList[j];
                edgeList[j] = temp;
            }
        }
    }
    k = 0; // 选中的边的数量
    for (i = 0; i < graph.edgeNum; i++) {
        int parentVex1 = find(parent, edgeList[i].vex1);
        int parentVex2 = find(parent, edgeList[i].vex2);
        if (parentVex1 != parentVex2) { // 如果两个顶点的父节点不同，说明它们不在同一个集合中
            parent[parentVex1] = parentVex2; // 将它们合并到同一个集合中
            mst[k++] = edgeList[i]; // 将该边加入最小生成树
            if (k == graph.vexNum - 1) { // 最小生成树的边数等于顶点数减1时结束
                break;
            }
        }
    }
    free(edgeList);
}
  1. 完整代码

下面是 Kruskal 算法的完整代码，包括初始化图、查找父节点和 Kruskal 算法的实现。

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

#define MAX_VERTEX_NUM 100 // 最大顶点数
#define INF 32767 // 表示无穷大的值

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

typedef struct {
    int vex[MAX_VERTEX_NUM]; // 存储顶点
    int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边的权值
    int vexNum; // 顶点数
    int edgeNum; // 边数
} Graph; // 图的结构体

void initGraph(Graph* graph) {
    int i, j;
    for (i = 0; i < MAX_VERTEX_NUM; i++) {
        for (j = 0; j < MAX_VERTEX_NUM; j++) {
            graph->edge[i][j] = INF;
        }
    }
    graph->vexNum = 0;
    graph->edgeNum = 0;
}

int find(int* parent, int f) {
    while (parent[f] > 0) {
        f = parent[f];
    }
    return f;
}

void kruskal(Graph graph, Edge* mst) {
    int i, j, k, n, m;
    int parent[MAX_VERTEX_NUM] = { 0 }; // 存储每个顶点的父节点
    Edge* edgeList = (Edge*)malloc(sizeof(Edge) * graph.edgeNum); // 存储所有边的列表
    k = 0; // 边的数量
    for (i = 0; i < graph.vexNum; i++) {
        for (j = i + 1; j < graph.vexNum; j++) {
            if (graph.edge[i][j] != INF) { // 存储所有的边
                edgeList[k].vex1 = i;
                edgeList[k].vex2 = j;
                edgeList[k].weight = graph.edge[i][j];
                k++;
            }
        }
    }
    for (i = 0; i < k; i++) { // 对所有边按权值从小到大排序
        for (j = i + 1; j < k; j++) {
            if (edgeList[i].weight > edgeList[j].weight) {
                Edge temp = edgeList[i];
                edgeList[i] = edgeList[j];
                edgeList[j] = temp;
            }
        }
    }
    k = 0; // 选中的边的数量
    for (i = 0; i < graph.edgeNum; i++) {
        int parentVex1 = find(parent, edgeList[i].vex1);
        int parentVex2 = find(parent, edgeList[i].vex2);
        if (parentVex1 != parentVex2) { // 如果两个顶点的父节点不同，说明它们不在同一个集合中
            parent[parentVex1] = parentVex2; // 将它们合并到同一个集合中
            mst[k++] = edgeList[i]; // 将该边加入最小生成树
            if (k == graph.vexNum - 1) { // 最小生成树的边数等于顶点数减1时结束
                break;
            }
        }
    }
    free(edgeList);
}

int main() {
    Graph graph;
    Edge mst[MAX_VERTEX_NUM - 1];
    int i, j;
    initGraph(&graph);
    printf("请输入顶点数和边数：");
    scanf("%d%d", &graph.vexNum, &graph.edgeNum);
    printf("请输入顶点：");
    for (i = 0; i < graph.vexNum; i++) {
        scanf("%d", &graph.vex[i]);
    }
    printf("请输入边及其权值：\n");
    for (i = 0; i < graph.edgeNum; i++) {
        int vex1, vex2, weight;
        scanf("%d%d%d", &vex1, &vex2, &weight);
        graph.edge[vex1][vex2] = weight;
        graph.edge[vex2][vex1] = weight; // 无向图的边是双向的
    }
    kruskal(graph, mst);
    printf("最小生成树的边及其权值为：\n");
    for (i = 0; i < graph.vexNum - 1; i++) {
        printf("(%d, %d) %d\n", graph.vex[mst[i].vex1], graph.vex[mst[i].vex2], mst[i].weight);
    }
    return 0;
}
Kruskal 算法 C 语言实现详解 - 求解最小生成树

原文地址: https://www.cveoy.top/t/topic/oroN 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录