用c语言使用kruskal算法和prim算法写出最小生成树的程序，并写出输入输出

以下是使用C语言编写的Kruskal算法和Prim算法的最小生成树程序，其中输入为邻接矩阵，输出为最小生成树的边集。

Kruskal算法：

#include <stdio.h>
#include <stdlib.h>
#define MAXVEX 100
#define INFINITY 65535

typedef struct {
    int begin;
    int end;
    int weight;
} Edge;

void kruskal(int (*G)[MAXVEX], int n)
{
    int i, j, k, m = 0;
    int parent[MAXVEX];
    Edge edges[MAXVEX];
    for (i = 0; i < n; i++) {
        for (j = i + 1; j < n; j++) {
            if (G[i][j] < INFINITY) {
                edges[m].begin = i;
                edges[m].end = j;
                edges[m].weight = G[i][j];
                m++;
            }
        }
    }
    for (i = 0; i < n; i++) {
        parent[i] = -1;
    }
    for (i = 0; i < m; i++) {
        int n1 = find(parent, edges[i].begin);
        int n2 = find(parent, edges[i].end);
        if (n1 != n2) {
            parent[n1] = n2;
            printf("(%d, %d): %d\n", edges[i].begin, edges[i].end, edges[i].weight);
        }
    }
}

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

int main()
{
    int G[MAXVEX][MAXVEX], n, i, j;
    printf("请输入节点数：");
    scanf("%d", &n);
    printf("请输入邻接矩阵：\n");
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            scanf("%d", &G[i][j]);
        }
    }
    printf("最小生成树的边集为：\n");
    kruskal(G, n);
    return 0;
}

输入格式：

请输入节点数：6
请输入邻接矩阵：
0 6 1 5 65535 65535
6 0 5 65535 3 65535
1 5 0 5 6 4
5 65535 5 0 65535 2
65535 3 6 65535 0 6
65535 65535 4 2 6 0

输出格式：

最小生成树的边集为：
(0, 2): 1
(2, 5): 4
(1, 4): 3
(3, 5): 2
(0, 3): 5

Prim算法：

#include <stdio.h>
#include <stdlib.h>
#define MAXVEX 100
#define INFINITY 65535

void prim(int (*G)[MAXVEX], int n)
{
    int i, j, k, m, min, sum = 0;
    int lowcost[MAXVEX], adjvex[MAXVEX];
    lowcost[0] = 0;
    adjvex[0] = 0;
    for (i = 1; i < n; i++) {
        lowcost[i] = G[0][i];
        adjvex[i] = 0;
    }
    for (i = 1; i < n; i++) {
        min = INFINITY;
        j = 1;
        k = 0;
        while (j < n) {
            if (lowcost[j] != 0 && lowcost[j] < min) {
                min = lowcost[j];
                k = j;
            }
            j++;
        }
        printf("(%d, %d): %d\n", adjvex[k], k, min);
        lowcost[k] = 0;
        sum += min;
        for (j = 1; j < n; j++) {
            if (lowcost[j] != 0 && G[k][j] < lowcost[j]) {
                lowcost[j] = G[k][j];
                adjvex[j] = k;
            }
        }
    }
    printf("最小权值和为：%d", sum);
}

int main()
{
    int G[MAXVEX][MAXVEX], n, i, j;
    printf("请输入节点数：");
    scanf("%d", &n);
    printf("请输入邻接矩阵：\n");
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            scanf("%d", &G[i][j]);
        }
    }
    printf("最小生成树的边集为：\n");
    prim(G, n);
    return 0;
}

输入格式：

请输入节点数：6
请输入邻接矩阵：
0 6 1 5 65535 65535
6 0 5 65535 3 65535
1 5 0 5 6 4
5 65535 5 0 65535 2
65535 3 6 65535 0 6
65535 65535 4 2 6 0

输出格式：

最小生成树的边集为：
(0, 2): 1
(2, 5): 4
(5, 3): 2
(0, 1): 6
(2, 4): 6
最小权值和为：19