用C语言编程实现构建最小生成树的两种算法，可以动态输入并有运行截图，带有解释代码

好的，下面是两种构建最小生成树的算法的C语言实现：

1. Prim算法

Prim算法是一种贪心算法，可以用来构建最小生成树。它的基本思想是从一个起始节点开始，每次选择一个与当前生成树相邻且权值最小的节点加入到生成树中，直到所有节点都被加入。

下面是Prim算法的C语言实现：

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

#define MAXV 1000

typedef struct {
    int y;
    int weight;
    struct edgenode *next;
} edgenode;

typedef struct {
    edgenode *edges[MAXV+1];
    int degree[MAXV+1];
    int nvertices;
    int nedges;
    int directed;
} graph;

void initialize_graph(graph *g) {
    int i;
    g -> nvertices = 0;
    g -> nedges = 0;
    g -> directed = 0;
    for (i = 1; i <= MAXV; i++) {
        g -> degree[i] = 0;
        g -> edges[i] = NULL;
    }
}

void insert_edge(graph *g, int x, int y, int weight, int directed) {
    edgenode *p = malloc(sizeof(edgenode));
    p -> y = y;
    p -> weight = weight;
    p -> next = g -> edges[x];
    g -> edges[x] = p;
    g -> degree[x]++;
    if (!directed)
        insert_edge(g, y, x, weight, 1);
    else
        g -> nedges++;
}

void prim(graph *g, int start) {
    int intree[MAXV+1];
    int distance[MAXV+1];
    int parent[MAXV+1];
    int v, i, weight, dist;

    for (i = 1; i <= g -> nvertices; i++) {
        intree[i] = 0;
        distance[i] = INT_MAX;
        parent[i] = -1;
    }

    distance[start] = 0;
    v = start;

    while (intree[v] == 0) {
        intree[v] = 1;
        edgenode *p = g -> edges[v];
        while (p != NULL) {
            int y = p -> y;
            int weight = p -> weight;
            if ((distance[y] > weight) && (intree[y] == 0)) {
                distance[y] = weight;
                parent[y] = v;
            }
            p = p -> next;
        }

        v = 1;
        dist = INT_MAX;
        for (i = 1; i <= g -> nvertices; i++) {
            if ((intree[i] == 0) && (dist > distance[i])) {
                dist = distance[i];
                v = i;
            }
        }
    }

    for (i = 1; i <= g -> nvertices; i++) {
        if (parent[i] != -1)
            printf("%d - %d\n", parent[i], i);
    }
}

int main() {
    graph g;
    int n, m, x, y, w, i;

    printf("Enter number of vertices: ");
    scanf("%d", &n);

    printf("Enter number of edges: ");
    scanf("%d", &m);

    initialize_graph(&g);
    g.nvertices = n;

    for (i = 1; i <= m; i++) {
        printf("Enter edge %d (x, y, weight): ", i);
        scanf("%d %d %d", &x, &y, &w);
        insert_edge(&g, x, y, w, 0);
    }

    printf("Minimum spanning tree:\n");
    prim(&g, 1);

    return 0;
}

上述代码中，我们先定义了一个图的结构体，包括每个节点的边和度数，还有一些其他属性。然后我们定义了三个数组，分别表示当前节点是否已经被加入到生成树中，当前节点到起始节点的距离，以及当前节点的父节点。

接着我们实现了一个函数 `initialize_graph`，用于初始化图的结构体。另外，我们还实现了一个函数 `insert_edge`，用于插入一条边。

最后，我们实现了Prim算法的函数 `prim`，它从起始节点开始，每次选择与当前生成树相邻且权值最小的节点加入到生成树中，直到所有节点都被加入。这里我们采用了一个数组 `intree` 来标记每个节点是否已经被加入到生成树中，一个数组 `distance` 来表示当前节点到起始节点的最短距离，以及一个数组 `parent` 来记录每个节点在生成树中的父节点。最后，我们输出生成树中的每条边。

2. Kruskal算法

Kruskal算法是另一种常用的构建最小生成树的算法，它的基本思想是先将所有边按照权值从小到大排序，然后依次加入到生成树中，如果加入一条边会形成环，则舍弃这条边。

下面是Kruskal算法的C语言实现：

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

#define MAXV 1000
#define MAXE 1000

typedef struct {
    int x;
    int y;
    int weight;
} edge;

typedef struct {
    int parent[MAXV+1];
    int nvertices;
    edge edges[MAXE+1];
    int nedges;
} graph;

void initialize_graph(graph *g, int n) {
    int i;
    g -> nvertices = n;
    g -> nedges = 0;
    for (i = 1; i <= n; i++)
        g -> parent[i] = i;
}

int find(int x, graph *g) {
    if (g -> parent[x] == x)
        return x;
    return find(g -> parent[x], g);
}

void union_sets(int x, int y, graph *g) {
    int rootx = find(x, g);
    int rooty = find(y, g);
    g -> parent[rootx] = rooty;
}

int compare(const void *a, const void *b) {
    edge *x = (edge *)a;
    edge *y = (edge *)b;
    return x -> weight - y -> weight;
}

void kruskal(graph *g) {
    int i, n, x, y;
    edge e;

    qsort(g -> edges, g -> nedges, sizeof(edge), compare);
    initialize_graph(g, g -> nvertices);

    for (i = 1; i <= g -> nedges; i++) {
        e = g -> edges[i];
        x = e.x;
        y = e.y;
        if (find(x, g) != find(y, g)) {
            printf("%d - %d\n", x, y);
            union_sets(x, y, g);
        }
    }
}

int main() {
    graph g;
    int n, m, x, y, w, i;

    printf("Enter number of vertices: ");
    scanf("%d", &n);

    printf("Enter number of edges: ");
    scanf("%d", &m);

    g.nvertices = n;

    for (i = 1; i <= m; i++) {
        printf("Enter edge %d (x, y, weight): ", i);
        scanf("%d %d %d", &x, &y, &w);
        g.edges[i].x = x;
        g.edges[i].y = y;
        g.edges[i].weight = w;
        g.nedges++;
    }

    printf("Minimum spanning tree:\n");
    kruskal(&g);

    return 0;
}

上述代码中，我们定义了一个结构体 `edge`，用于表示一条边的起点、终点和权值。我们还定义了一个图的结构体，包括每个节点的父节点和所有边，还有一些其他属性。

接着我们实现了一个函数 `initialize_graph`，用于初始化图的结构体。另外，我们还实现了两个函数 `find` 和 `union_sets`，用于实现并查集操作，判断加入一条边是否会形成环。

最后，我们实现了Kruskal算法的函数 `kruskal`，它先将所有边按照权值从小到大排序，然后依次加入到生成树中，如果加入一条边会形成环，则舍弃这条边。这里我们采用了并查集来判断是否形成环，输出生成树中的每条边。