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

以下是使用C语言实现Kruskal算法和Prim算法求解最小生成树的代码：

Kruskal算法：

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

#define MAX_VERTICES 100
#define MAX_EDGES 100

typedef struct edge {
    int start, end, weight;
} Edge;

int parent[MAX_VERTICES];

int find(int i) {
    while (parent[i])
        i = parent[i];
    return i;
}

void unionSet(int i, int j) {
    if (i != j)
        parent[j] = i;
}

void kruskal(Edge edges[], int n, int m) {
    int i, j, k, sum = 0;
    for (i = 1; i <= n; i++)
        parent[i] = 0;
    for (i = 0; i < m; i++) {
        int start = edges[i].start;
        int end = edges[i].end;
        int weight = edges[i].weight;
        int x = find(start);
        int y = find(end);
        if (x != y) {
            unionSet(x, y);
            printf("(%d, %d) %d\n", start, end, weight);
            sum += weight;
        }
    }
    printf("Weight of MST is %d\n", sum);
}

int main() {
    int n, m, i;
    Edge edges[MAX_EDGES];
    printf("Enter number of vertices: ");
    scanf("%d", &n);
    printf("Enter number of edges: ");
    scanf("%d", &m);
    printf("Enter details of edges (start, end, weight):\n");
    for (i = 0; i < m; i++) {
        scanf("%d %d %d", &edges[i].start, &edges[i].end, &edges[i].weight);
    }
    kruskal(edges, n, m);
    return 0;
}

Prim算法：

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

#define MAX_VERTICES 100

int graph[MAX_VERTICES][MAX_VERTICES];
int visited[MAX_VERTICES];
int parent[MAX_VERTICES];
int key[MAX_VERTICES];

void prim(int n) {
    int i, j, k, min, sum = 0;
    for (i = 1; i <= n; i++) {
        visited[i] = 0;
        key[i] = INT_MAX;
    }
    key[1] = 0;
    parent[1] = -1;
    for (i = 1; i <= n; i++) {
        min = INT_MAX;
        for (j = 1; j <= n; j++) {
            if (!visited[j] && key[j] < min) {
                min = key[j];
                k = j;
            }
        }
        visited[k] = 1;
        for (j = 1; j <= n; j++) {
            if (graph[k][j] && !visited[j] && graph[k][j] < key[j]) {
                parent[j] = k;
                key[j] = graph[k][j];
            }
        }
    }
    printf("Edges of MST:\n");
    for (i = 2; i <= n; i++) {
        printf("(%d, %d)\n", parent[i], i);
        sum += graph[i][parent[i]];
    }
    printf("Weight of MST is %d\n", sum);
}

int main() {
    int n, i, j;
    printf("Enter number of vertices: ");
    scanf("%d", &n);
    printf("Enter adjacency matrix of graph:\n");
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            scanf("%d", &graph[i][j]);
        }
    }
    prim(n);
    return 0;
}