c语言最小生成树

C语言实现最小生成树算法主要有两种：Prim算法和Kruskal算法。

1. Prim算法实现最小生成树

Prim算法是一种贪心算法，其主要思想是从一个起点开始，每次选择一个与当前生成树距离最小的点，加入到生成树中，直到所有点都被加入到生成树中。

具体实现步骤如下：

1）定义一个数组dist，用于存储每个顶点到当前生成树的距离，初始化为无穷大。

2）将起点加入到生成树中，更新与起点相邻的顶点到生成树的距离。

3）选择一个距离最小的顶点加入到生成树中，更新与该顶点相邻的顶点到生成树的距离。

4）重复步骤3，直到所有顶点都被加入到生成树中。

代码实现如下：

#define MAXVEX 100
#define INF 0x3f3f3f3f

typedef struct {
    int vexs[MAXVEX];    // 顶点集合
    int arcs[MAXVEX][MAXVEX];    // 邻接矩阵
    int vexnum, arcnum;    // 顶点数和边数
} Graph;

void prim(Graph* G, int v0) {
    int dist[MAXVEX], visited[MAXVEX], i, j, k, min;

    // 初始化dist数组和visited数组
    for (i = 0; i < G->vexnum; i++) {
        dist[i] = G->arcs[v0][i];
        visited[i] = 0;
    }

    visited[v0] = 1;    // 将v0加入到生成树中

    // 进行n-1次选择
    for (i = 1; i < G->vexnum; i++) {
        min = INF;

        // 选择与当前生成树距离最小的顶点
        for (j = 0; j < G->vexnum; j++) {
            if (!visited[j] && dist[j] < min) {
                min = dist[j];
                k = j;
            }
        }

        visited[k] = 1;    // 将k加入到生成树中

        // 更新dist数组
        for (j = 0; j < G->vexnum; j++) {
            if (!visited[j] && G->arcs[k][j] < dist[j]) {
                dist[j] = G->arcs[k][j];
            }
        }
    }
}

2. Kruskal算法实现最小生成树

Kruskal算法也是一种贪心算法，其主要思想是将所有边按照权值从小到大排序，然后依次选择每条边，如果该边的两个端点不在同一个连通分量中，则将它们合并到同一个连通分量中，并将该边加入到生成树中。

具体实现步骤如下：

1）将所有边按照权值从小到大排序。

2）依次选择每条边，如果该边的两个端点不在同一个连通分量中，则将它们合并到同一个连通分量中，并将该边加入到生成树中。

3）重复步骤2，直到所有顶点都被加入到生成树中。

代码实现如下：

#define MAXVEX 100
#define INF 0x3f3f3f3f

typedef struct {
    int u, v, w;    // 边的起点、终点和权值
} Edge;

typedef struct {
    int vexs[MAXVEX];    // 顶点集合
    Edge edges[MAXVEX * MAXVEX];    // 边集合
    int vexnum, edgenum;    // 顶点数和边数
} Graph;

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

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

    return f;
}

void kruskal(Graph* G) {
    int parent[MAXVEX], i, j, k, m, n;
    Edge e;

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

    // 将所有边按照权值从小到大排序
    qsort(G->edges, G->edgenum, sizeof(Edge), cmp);

    // 依次选择每条边
    for (i = 0; i < G->edgenum; i++) {
        e = G->edges[i];
        m = find(parent, e.u);
        n = find(parent, e.v);

        // 如果该边的两个端点不在同一个连通分量中，则将它们合并到同一个连通分量中，并将该边加入到生成树中
        if (m != n) {
            parent[m] = n;
            printf("(%d, %d) %d\n", e.u, e.v, e.w);
        }
    }
}