最小生成树算法C语言代码实例

什么是最小生成树？

最小生成树（MST）是指在一张图中，找到一颗包含所有节点的连通子树，且这颗树的边的权值之和最小。其中，连通子树是指子树中任意两点都可以互相到达的树。

Kruskal算法实现最小生成树

Kruskal算法的过程

Kruskal算法是一种贪心算法，它的基本思想是先将图中所有边按权值从小到大排序，然后从小到大地选择边，加入到一个新的集合中，如果加入这个边能够形成一个新的环路，则舍弃这个边，否则就保留这个边，直到加入的边数等于节点数减1为止。此时所构成的边即为最小生成树。

Kruskal算法的代码实现

下面是Kruskal算法的C语言代码实现，其中边的结构体定义如下：

struct Edge {
    int u, v; // 边的两个端点
    int w; // 边的权值
};

核心函数代码：

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

int find(int parent[], int i) {
    if (parent[i] == -1)
        return i;
    return find(parent, parent[i]);
}

void Union(int parent[], int x, int y) {
    int xset = find(parent, x);
    int yset = find(parent, y);
    parent[xset] = yset;
}

void Kruskal(struct Edge edges[], int V, int E) {
    int parent[V];
    memset(parent, -1, sizeof(parent));
    int i = 0, j = 0, k = 0;
    struct Edge result[V];

    // 对所有边按权值从小到大排序
    qsort(edges, E, sizeof(edges[0]), cmp);

    while (j < V - 1 && k < E) {
        int u = edges[k].u;
        int v = edges[k].v;
        int w = edges[k].w;

        int x = find(parent, u);
        int y = find(parent, v);

        if (x != y) {
            result[i++] = edges[k];
            Union(parent, x, y);
            j++;
        }
        k++;
    }

    printf("Edges in MST:\n");
    for (i = 0; i < j; i++) {
        printf("%d - %d : %d\n", result[i].u, result[i].v, result[i].w);
    }
}

Prim算法实现最小生成树

Prim算法的过程

Prim算法也是一种贪心算法，它的基本思想是从某个顶点开始，不断地扩张当前生成树，每次选择当前生成树与其它未加入到生成树中的节点所对应的边中的最短边加入到生成树中，直到所有节点都加入到生成树中为止。此时所构成的边即为最小生成树。

Prim算法的代码实现

下面是Prim算法的C语言代码实现，其中边的结构体定义与之前一致：

struct Edge {
    int u, v; // 边的两个端点
    int w; // 边的权值
};

核心函数代码：

void Prim(int graph[V][V], int V) {
    int parent[V]; // 存放最小生成树的边
    int key[V]; // 存放顶点到最小生成树的最小边权值
    bool mstSet[V]; // 存放那些顶点已经包含在最小生成树中

    for (int i = 0; i < V; i++) {
        key[i] = INT_MAX;
        mstSet[i] = false;
    }

    key[0] = 0;
    parent[0] = -1;

    for (int count = 0; count < V - 1; count++) {
        int u = minKey(key, mstSet, V);
        mstSet[u] = true;

        for (int v = 0; v < V; v++) {
            if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }

    printf("Edges in MST:\n");
    for (int i = 1; i < V; i++) {
        printf("%d - %d : %d\n", parent[i], i, graph[i][parent[i]]);
    }
}

示例说明

假设一个图如下所示：

  5  ----- 4
 / \       | \
2   \      |  3
 \   \     | /
  6 - 1 --- 0
      9

按照Kruskal算法，首先将所有边按权值从小到大排序：

(2,6): 3
(0,1): 4
(7,8): 7
(3,4): 8
(6,1): 8
(1,4): 9
(3,5): 10
(1,2): 11

从最小的边开始加入到生成树中，一直到生成树中有5条边为止，这样形成的最小生成树为：

Edges in MST:
2 - 6 : 3
0 - 1 : 4
1 - 4 : 9
6 - 1 : 8

按照Prim算法，首先选择一个顶点，比如顶点0作为根节点，将所有顶点到根节点的最短距离存储在key数组中：

key[] = {0, INF, INF, INF, INF, INF, INF, INF, INF}

然后选择key数组中最短距离的顶点2，将它加入到生成树中，并更新key数组：

key[] = {0, INF, 3, INF, INF, INF, INF, INF, INF}

接下来，选择key数组中最短距离的顶点6，将它加入到生成树中，并更新key数组：

key[] = {0, 6, 3, INF, INF, 10, INF, INF, INF}

重复上述操作，直到生成树中包含所有的顶点，产生的最小生成树为：

Edges in MST:
0 - 1 : 4
1 - 2 : 11
2 - 6 : 3
1 - 4 : 9

总结

以上就是Kruskal算法和Prim算法实现最小生成树的完整攻略。其中，Kruskal算法的时间复杂度为O(ElogE)，空间复杂度为O(E)，Prim算法的时间复杂度为O(V^2)或O(ElogV)，空间复杂度为O(V+E)。在实际使用时，根据图中节点的数量和边的数量来选择恰当的算法。