C语言中给定图的邻接矩阵数据结构，设计算法，用Prim和KrusKal算法构造图的最小生成树

Prim算法构造最小生成树的步骤如下：

1. 初始化一个空的最小生成树集合，将任意一个顶点加入其中。

2. 对于所有不在最小生成树集合中的点，计算它与最小生成树集合中点的边的权重，选择其中权重最小的边所连接的点加入最小生成树集合中。

3. 重复步骤2直到最小生成树集合包含所有点。

C语言中给定图的邻接矩阵数据结构，Prim算法的代码如下：

#define INF 0x3f3f3f3f // 定义正无穷

int prim(int n, int graph[][n])
{
    int i, j, k;
    int lowcost[n]; // 存储当前点到最小生成树集合的最短距离
    int closest[n]; // 存储当前点到最小生成树集合中距离最近的点
    int sum = 0; // 最小生成树的权值和

    for (i = 1; i < n; i++) {
        lowcost[i] = graph[0][i]; // 初始化当前点到最小生成树集合的距离
        closest[i] = 0; // 初始化当前点到最小生成树集合中距离最近的点为0
    }

    for (i = 1; i < n; i++) {
        int min = INF;
        for (j = 1; j < n; j++) {
            if (lowcost[j] > 0 && lowcost[j] < min) {
                min = lowcost[j];
                k = j;
            }
        }
        sum += min;
        lowcost[k] = 0;
        for (j = 1; j < n; j++) {
            if (lowcost[j] > 0 && graph[k][j] < lowcost[j]) {
                lowcost[j] = graph[k][j];
                closest[j] = k;
            }
        }
    }

    return sum;
}

Kruskal算法构造最小生成树的步骤如下：

1. 初始化一个空的最小生成树集合，将所有边按照权重从小到大排序。

2. 依次选择权重最小的边，如果边所连接的两个点不在同一个连通块中，则将这条边加入最小生成树集合中。

3. 重复步骤2直到最小生成树集合包含所有点。

C语言中给定图的邻接矩阵数据结构，Kruskal算法的代码如下：

#define MAX_EDGE (n * (n - 1) / 2) // 最大边数

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

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

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

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

int kruskal(int n, int graph[][n])
{
    Edge edges[MAX_EDGE]; // 存储所有边
    int parent[n]; // 存储每个点所在的连通块
    int sum = 0; // 最小生成树的权值和
    int e = 0; // 已加入最小生成树集合的边数

    for (int i = 0; i < n; i++) {
        parent[i] = -1;
        for (int j = i + 1; j < n; j++) {
            if (graph[i][j] != 0) {
                edges[e].u = i;
                edges[e].v = j;
                edges[e].w = graph[i][j];
                e++;
            }
        }
    }

    qsort(edges, e, sizeof(Edge), cmp);

    int i = 0;
    while (e < n - 1 && i < n * (n - 1) / 2) {
        int u = edges[i].u;
        int v = edges[i].v;
        int w = edges[i].w;
        i++;
        int x = find(parent, u);
        int y = find(parent, v);
        if (x != y) {
            sum += w;
            union_set(parent, x, y);
            e++;
        }
    }

    return sum;
}