用c语言编译实现构建最小生成树的两种算法

最小生成树是一种常用的图论算法，主要用于解决带权连通图的最小连通子图问题。构建最小生成树有两种经典的算法：Kruskal算法和Prim算法。

1. Kruskal算法

Kruskal算法是一种贪心算法，主要思想是先将图中的边按照权值从小到大排序，然后依次加入到最小生成树中，直到所有节点都被连接为止。在加入每条边时，判断这条边是否会形成环，如果不会，则将其加入最小生成树中。

下面是用C语言实现Kruskal算法的代码：

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

#define MaxVertexNum 100 // 最大顶点数
#define MaxEdgeNum 100   // 最大边数

typedef struct {
    int u, v; // 顶点编号
    int w;    // 边权重
} Edge;

typedef struct {
    int n, m;          // 顶点数和边数
    Edge edges[MaxEdgeNum]; // 边集合
} Graph;

Graph* createGraph(int n, int m)
{
    Graph* G = (Graph*)malloc(sizeof(Graph));
    G->n = n;
    G->m = m;
    return G;
}

int cmp(const void* a, const void* b)
{
    return ((Edge*)a)->w - ((Edge*)b)->w;
}

int getParent(int* parent, int i)
{
    if (parent[i] == i) return i;
    else return getParent(parent, parent[i]);
}

void kruskal(Graph* G)
{
    int parent[MaxVertexNum];
    for (int i = 0; i < G->n; i++) parent[i] = i;
    qsort(G->edges, G->m, sizeof(Edge), cmp);
    int count = 0, i = 0;
    while (count < G->n - 1 && i < G->m) {
        int u = G->edges[i].u;
        int v = G->edges[i].v;
        int w = G->edges[i].w;
        i++;
        int pu = getParent(parent, u);
        int pv = getParent(parent, v);
        if (pu != pv) {
            printf("(%d, %d) %d\n", u, v, w);
            parent[pu] = pv;
            count++;
        }
    }
}

int main()
{
    int n = 6, m = 10;
    Graph* G = createGraph(n, m);
    G->edges[0] = (Edge){0, 1, 6};
    G->edges[1] = (Edge){0, 2, 1};
    G->edges[2] = (Edge){0, 3, 5};
    G->edges[3] = (Edge){1, 2, 5};
    G->edges[4] = (Edge){1, 4, 3};
    G->edges[5] = (Edge){2, 3, 5};
    G->edges[6] = (Edge){2, 4, 6};
    G->edges[7] = (Edge){2, 5, 4};
    G->edges[8] = (Edge){3, 5, 2};
    G->edges[9] = (Edge){4, 5, 6};
    kruskal(G);
    return 0;
}

2. Prim算法

Prim算法也是一种贪心算法，但与Kruskal算法不同，Prim算法从一个顶点开始，每次选择与当前生成树相邻的最短边，并将其加入到生成树中，直到所有节点都被连接为止。

下面是用C语言实现Prim算法的代码：

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

#define MaxVertexNum 100 // 最大顶点数
#define INF INT_MAX     // 无穷大

typedef struct {
    int n;            // 顶点数
    int e[MaxVertexNum][MaxVertexNum]; // 邻接矩阵
} Graph;

Graph* createGraph(int n)
{
    Graph* G = (Graph*)malloc(sizeof(Graph));
    G->n = n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            G->e[i][j] = INF;
        }
    }
    return G;
}

void prim(Graph* G)
{
    int lowcost[MaxVertexNum]; // 存储当前节点到生成树的最短边
    int closest[MaxVertexNum]; // 存储当前节点到生成树的最短边的终点
    int S[MaxVertexNum]; // 存储当前已经加入生成树的节点
    for (int i = 0; i < G->n; i++) {
        lowcost[i] = G->e[0][i];
        closest[i] = 0;
        S[i] = 0;
    }
    S[0] = 1;
    for (int i = 1; i < G->n; i++) {
        int min = INF, k = 0;
        for (int j = 0; j < G->n; j++) {
            if (!S[j] && lowcost[j] < min) {
                min = lowcost[j];
                k = j;
            }
        }
        printf("(%d, %d) %d\n", closest[k], k, min);
        S[k] = 1;
        for (int j = 0; j < G->n; j++) {
            if (!S[j] && G->e[k][j] < lowcost[j]) {
                lowcost[j] = G->e[k][j];
                closest[j] = k;
            }
        }
    }
}

int main()
{
    int n = 6;
    Graph* G = createGraph(n);
    G->e[0][1] = G->e[1][0] = 6;
    G->e[0][2] = G->e[2][0] = 1;
    G->e[0][3] = G->e[3][0] = 5;
    G->e[1][2] = G->e[2][1] = 5;
    G->e[1][4] = G->e[4][1] = 3;
    G->e[2][3] = G->e[3][2] = 5;
    G->e[2][4] = G->e[4][2] = 6;
    G->e[2][5] = G->e[5][2] = 4;
    G->e[3][5] = G->e[5][3] = 2;
    G->e[4][5] = G->e[5][4] = 6;
    prim(G);
    return 0;
}