C语言实现最小生成树构造算法

C语言实现最小生成树构造算法攻略

最小生成树（Minimum Spanning Tree，MST）是一种求加权无向连通图的生成树的算法，其可以将连通图的n个顶点连接起来，形成一个权值最小的树。本文将介绍使用C语言实现最小生成树构造算法的攻略。

算法简介

其中，Kruskal算法和Prim算法是最常用的两个求解最小生成树的算法。

• Kruskal算法

Kruskal算法首先需要把图中所有的边从小到大排序，依次取出每一条边，检查该边的两个顶点是否在同一个连通分量内，若不在，则将这条边放入生成树中，并将这两个顶点之间连通。

• Prim算法

Prim算法则需要选取一个任意的顶点作为根节点，每次向生成树中添加一条从树中已有节点到不在树上的节点的最短边，直到所有节点都在生成树中。

Kruskal算法实现

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

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

#define MAX 1000

typedef struct {
    int u, v, w;
}Edge;

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

int Kruskal(Edge *edges, int n, int m, Edge *tree)
{
    int i, j, k;
    int set[MAX];

    for (i = 0; i < n; ++i)
        set[i] = i;

    qsort(edges, m, sizeof(edges[0]), cmp);  // 对边按权值进行排序

    for (i = j = 0; i < m && j < n - 1; ++i) {
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        while (u != set[u]) u = set[u];
        while (v != set[v]) v = set[v];
        if (u != v) {
            set[u] = v;
            tree[j++] = edges[i];
        }
    }

    return (j == n - 1);  // 如果生成树边数为n-1则返回1，否则返回0
}

int main()
{
    int n, m;
    Edge edges[MAX], tree[MAX];
    scanf("%d %d", &n, &m);

    for (int i = 0; i < m; ++i)
        scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].w);

    if (!Kruskal(edges, n, m, tree)) {
        printf("No MST!\n");  // 如果生成树不存在则输出No MST！
    }
    else {
        int w = 0;
        for (int i = 0; i < n - 1; ++i)
            w += tree[i].w;
        printf("MST weight=%d\n", w);
        for (int i = 0; i < n - 1; ++i)
            printf("(%d,%d) ", tree[i].u, tree[i].v);
    }

    return 0;
}

Prim算法实现

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

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

#define MAX 1000

int adj[MAX][MAX];

int Prim(int n, int **edges)
{
    int i, j, k;
    int dist[MAX], parent[MAX];
    bool visited[MAX];

    for (i = 0; i < n; ++i) {
        dist[i] = INT_MAX;
        visited[i] = false;
    }
    dist[0] = 0;
    parent[0] = -1;

    for (i = 0; i < n - 1; ++i) {
        int u = -1;
        for (j = 0; j < n; ++j) {
            if (!visited[j] && (u == -1 || dist[u] > dist[j]))
                u = j;
        }
        visited[u] = true;
        for (v = 0; v < n; ++v) {
            if (adj[u][v] && !visited[v] && dist[v] > adj[u][v]) {
                dist[v] = adj[u][v];
                parent[v] = u;
            }
        }
    }

    for (i = 1, k = 0; i < n; ++i) {
        if (parent[i] != -1) {
            edges[k][0] = parent[i];
            edges[k++][1] = i;
        }
    }

    return k;
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);

    for (int i = 0; i < m; ++i) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        adj[u][v] = w;
        adj[v][u] = w;
    }

    int **tree = (int**)malloc((n - 1) * sizeof(int*));
    for (int i = 0; i < n - 1; ++i) {
        tree[i] = (int*)malloc(2 * sizeof(int));
    }

    int k = Prim(n, tree);  // k为生成树的边数

    int w = 0;
    for (int i = 0; i < k; ++i)
        w += adj[tree[i][0]][tree[i][1]];
    printf("MST weight=%d\n", w);
    for (int i = 0; i < k; ++i)
        printf("(%d,%d) ", tree[i][0], tree[i][1]);

    return 0;
}

结束语

以上就是C语言实现最小生成树构造算法的详细攻略，希望对大家有所帮助。