克鲁斯卡尔算法 C语言 并从起点到终点输出最小生成树

克鲁斯卡尔算法是一种求解最小生成树的经典算法，它通过贪心策略每次选择权值最小的边，直到生成树中包含所有节点为止。下面是一个使用C语言实现克鲁斯卡尔算法并输出从起点到终点的最小生成树的示例代码：

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

#define MAX_VERTICES 100
#define MAX_EDGES 100

typedef struct {
    int u, v;
    int weight;
} Edge;

typedef struct {
    Edge edges[MAX_EDGES];
    int num_edges;
} Graph;

Graph graph;

int parent[MAX_VERTICES];

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

void union_sets(int i, int j) {
    int x = find(i);
    int y = find(j);
    parent[x] = y;
}

int compare_edges(const void* a, const void* b) {
    Edge* edge1 = (Edge*)a;
    Edge* edge2 = (Edge*)b;

    return edge1->weight - edge2->weight;
}

void kruskal(int start, int end) {
    int i, j;
    int total_weight = 0;
    int num_edges = 0;

    // 初始化并查集
    for (i = 0; i < MAX_VERTICES; i++) {
        parent[i] = i;
    }

    // 按照边的权值排序
    qsort(graph.edges, graph.num_edges, sizeof(Edge), compare_edges);

    // 依次选择边，直到生成树包含所有节点
    for (i = 0; i < graph.num_edges; i++) {
        Edge edge = graph.edges[i];

        if (find(edge.u) != find(edge.v)) {
            union_sets(edge.u, edge.v);
            total_weight += edge.weight;
            num_edges++;
            if (num_edges == MAX_VERTICES - 1) {
                break;
            }
        }
    }

    // 输出最小生成树
    printf("The minimum spanning tree from vertex %d to vertex %d is:\n", start, end);
    for (i = 0; i < MAX_VERTICES; i++) {
        if (parent[i] == i) {
            for (j = i + 1; j < MAX_VERTICES; j++) {
                if (parent[j] == j) {
                    int k;
                    for (k = 0; k < graph.num_edges; k++) {
                        if ((graph.edges[k].u == i && graph.edges[k].v == j) ||
                            (graph.edges[k].u == j && graph.edges[k].v == i)) {
                            printf("(%d,%d) ", i, j);
                            printf("weight=%d\n", graph.edges[k].weight);
                            break;
                        }
                    }
                }
            }
        }
    }

    printf("Total weight of the minimum spanning tree: %d\n", total_weight);
}

int main() {
    int num_vertices, start, end;
    int i;

    // 读取输入数据
    printf("Enter the number of vertices: ");
    scanf("%d", &num_vertices);

    printf("Enter the start vertex: ");
    scanf("%d", &start);

    printf("Enter the end vertex: ");
    scanf("%d", &end);

    printf("Enter the edges (u, v, weight):\n");
    for (i = 0; i < MAX_EDGES; i++) {
        int u, v, weight;
        if (scanf("%d%d%d", &u, &v, &weight) != 3) {
            break;
        }
        if (u >= num_vertices || v >= num_vertices) {
            printf("Invalid vertex number.\n");
            return 1;
        }
        graph.edges[i].u = u;
        graph.edges[i].v = v;
        graph.edges[i].weight = weight;
        graph.num_edges++;
    }

    kruskal(start, end);

    return 0;
}

该代码实现了克鲁斯卡尔算法，并在输出最小生成树时只输出了从起点到终点的边。