C语言实现 分别用Prim算法和Kruskal算法编程实现一下连通无向图的最小生成树。

好的，我可以为您介绍一下Prim算法和Kruskal算法，并提供C语言的实现代码。

首先，Prim算法是一种贪心算法，它从一个源节点开始，逐步扩大生成树的规模，直到包含图中所有节点。在每一步中，Prim算法选择当前生成树外与生成树内节点距离最短的边，将其加入生成树中。这个过程一直重复，直到生成树包含了所有节点。

其次，Kruskal算法也是一种贪心算法，它将所有边按照权值从小到大排序，然后依次将边加入生成树中，如果加入这条边不会形成环，就将其加入生成树中。这个过程一直重复，直到生成树包含了所有节点。

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

Prim算法实现代码：

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

#define INF 999999

int n; // 节点数
int graph[100][100]; // 图的邻接矩阵
int dist[100]; // 到生成树的最短距离
bool visited[100]; // 是否已访问
int parent[100]; // 最小生成树的父节点

int prim()
{
    // 初始化
    for (int i = 1; i <= n; i++) {
        dist[i] = INF;
        visited[i] = false;
    }
    dist[1] = 0;
    parent[1] = -1;

    // 重复 n-1 次
    for (int i = 1; i < n; i++) {
        // 找到到生成树距离最小的节点 u
        int u = -1;
        for (int j = 1; j <= n; j++) {
            if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
                u = j;
            }
        }
        visited[u] = true;

        // 更新到生成树的距离和父节点
        for (int v = 1; v <= n; v++) {
            if (!visited[v] && graph[u][v] < dist[v]) {
                dist[v] = graph[u][v];
                parent[v] = u;
            }
        }
    }

    // 计算最小生成树的权值和
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        if (parent[i] != -1) {
            sum += graph[i][parent[i]];
        }
    }
    return sum;
}

int main()
{
    // 输入图的邻接矩阵和节点数
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &graph[i][j]);
        }
    }

    int minWeight = prim();
    printf("最小生成树的权值和为 %d\n", minWeight);

    return 0;
}

Kruskal算法实现代码：

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

#define MAX 100

int n; // 节点数
int parent[MAX]; // 并查集数组
int graph[MAX][MAX]; // 图的邻接矩阵

// 并查集查找
int find(int x)
{
    if (parent[x] == x) {
        return x;
    }
    return parent[x] = find(parent[x]);
}

// 并查集合并
void merge(int x, int y)
{
    int px = find(x);
    int py = find(y);
    if (px != py) {
        parent[px] = py;
    }
}

// Kruskal算法
int kruskal()
{
    // 初始化并查集
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }

    // 将所有边按照权值从小到大排序
    int edges[MAX*MAX][3];
    int count = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i+1; j <= n; j++) {
            if (graph[i][j] != 0) {
                edges[count][0] = i;
                edges[count][1] = j;
                edges[count][2] = graph[i][j];
                count++;
            }
        }
    }
    for (int i = 0; i < count-1; i++) {
        for (int j = i+1; j < count; j++) {
            if (edges[i][2] > edges[j][2]) {
                int temp[3];
                temp[0] = edges[i][0];
                temp[1] = edges[i][1];
                temp[2] = edges[i][2];
                edges[i][0] = edges[j][0];
                edges[i][1] = edges[j][1];
                edges[i][2] = edges[j][2];
                edges[j][0] = temp[0];
                edges[j][1] = temp[1];
                edges[j][2] = temp[2];
            }
        }
    }

    // 依次加入边，直到生成树包含所有节点
    int sum = 0;
    for (int i = 0; i < count; i++) {
        int u = edges[i][0];
        int v = edges[i][1];
        if (find(u) != find(v)) {
            merge(u, v);
            sum += edges[i][2];
        }
    }
    return sum;
}

int main()
{
    // 输入图的邻接矩阵和节点数
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &graph[i][j]);
        }
    }

    int minWeight = kruskal();
    printf("最小生成树的权值和为 %d\n", minWeight);

    return 0;
}

以上是Prim算法和Kruskal算法的C语言实现代码，希望能够帮到您。