克鲁斯卡尔算法c++代码编写

以下是克鲁斯卡尔算法的C语言代码实现：

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

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

typedef char VertexType; // 顶点类型
typedef int EdgeType; // 权值类型

typedef struct {
    VertexType vertexes[MAX_VERTEX_NUM]; // 顶点集合
    EdgeType edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 边集合
    int vertex_num; // 顶点数
    int edge_num; // 边数
} Graph;

typedef struct {
    int begin; // 起点
    int end; // 终点
    EdgeType weight; // 权值
} Edge;

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

void kruskal(Graph *g) {
    Edge edges[MAX_EDGE_NUM];
    int parent[MAX_VERTEX_NUM] = {0};

    // 初始化边集合
    int k = 0;
    for (int i = 0; i < g->vertex_num; i++) {
        for (int j = i + 1; j < g->vertex_num; j++) {
            if (g->edges[i][j] != 0) {
                edges[k].begin = i;
                edges[k].end = j;
                edges[k].weight = g->edges[i][j];
                k++;
            }
        }
    }

    // 按权值升序排序
    for (int i = 0; i < g->edge_num - 1; i++) {
        for (int j = i + 1; j < g->edge_num; j++) {
            if (edges[i].weight > edges[j].weight) {
                Edge tmp = edges[i];
                edges[i] = edges[j];
                edges[j] = tmp;
            }
        }
    }

    // 初始化parent数组
    for (int i = 0; i < g->vertex_num; i++) {
        parent[i] = 0;
    }

    // 遍历边集合
    printf("Kruskal Algorithm:\n");
    for (int i = 0; i < g->edge_num; i++) {
        int begin = edges[i].begin;
        int end = edges[i].end;
        int weight = edges[i].weight;

        int root1 = find(parent, begin);
        int root2 = find(parent, end);

        if (root1 != root2) {
            parent[root1] = root2;
            printf("(%c, %c) %d\n", g->vertexes[begin], g->vertexes[end], weight);
        }
    }
}

int main() {
    Graph g = {
        {'A', 'B', 'C', 'D', 'E', 'F', 'G'},
        {
            {0,  12, 0,  0,  0,  16, 14},
            {12, 0,  10, 0,  0,  7,  0},
            {0,  10, 0,  3,  5,  6,  0},
            {0,  0,  3,  0,  4,  0,  0},
            {0,  0,  5,  4,  0,  2,  8},
            {16, 7,  6,  0,  2,  0,  9},
            {14, 0,  0,  0,  8,  9,  0},
        },
        7,
        12
    };

    kruskal(&g);

    return 0;
}

这里我们采用邻接矩阵的方式存储图，并实现了一个find函数来查找某个节点的根节点。kruskal函数中首先初始化了边集合，然后按照权值升序排序。接着初始化parent数组，然后遍历边集合，对于每一条边，我们分别找到它两个节点的根节点，如果根节点不同，说明这两个节点不在同一个连通分量中，我们将它们合并，并输出这条边。最终输出的就是最小生成树的边集合。