上机实验四 图的最小生成树算法设计 西安石油大学数据结构

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 定义边的数据结构
struct Edge {
    int src, dest, weight;
};
// 定义图的数据结构
struct Graph {
    int V, E; // 顶点数和边数
    struct Edge* edge; // 边的数组
};
// 创建一个图
struct Graph* createGraph(int V, int E) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->V = V;
    graph->E = E;
    graph->edge = (struct Edge*)malloc(graph->E * sizeof(struct Edge));
    return graph;
}
// 查找包含顶点v的子集的根节点
int find(int parent[], int v) {
    if (parent[v] == -1)
        return v;
    return find(parent, parent[v]);
}
// 将两个子集进行合并
void Union(int parent[], int x, int y) {
    int xroot = find(parent, x);
    int yroot = find(parent, y);
    parent[xroot] = yroot;
}
// 实现Kruskal算法
void kruskalMST(struct Graph* graph) {
    int V = graph->V;
    struct Edge result[V]; // 存储最小生成树的结果
    int e = 0; // 用于结果数组的索引
    int i = 0; // 用于排序边的索引
    // 按权重对所有边进行排序
    qsort(graph->edge, graph->E, sizeof(graph->edge[0]), [](const void* a, const void* b) {
        struct Edge* a1 = (struct Edge*)a;
        struct Edge* b1 = (struct Edge*)b;
        return a1->weight > b1->weight;
    });
    int *parent = (int*)malloc(V * sizeof(int));
    memset(parent, -1, V * sizeof(int));
    // 将边加入最小生成树中，直到最小生成树中有V-1条边
    while (e < V - 1 && i < graph->E) {
        struct Edge next_edge = graph->edge[i++];
        int x = find(parent, next_edge.src);
        int y = find(parent, next_edge.dest);
        if (x != y) {
            result[e++] = next_edge;
            Union(parent, x, y);
        }
    }
    // 打印最小生成树的边及权重
    printf("Edge \tWeight\n");
    for (i = 0; i < e; i++)
        printf("%d - %d \t%d \n", result[i].src, result[i].dest, result[i].weight);
}
int main() {
    int V = 4; // 顶点数
    int E = 5; // 边数
    struct Graph* graph = createGraph(V, E);
    // 添加边的权重信息
    graph->edge[0].src = 0;
    graph->edge[0].dest = 1;
    graph->edge[0].weight = 10;
    graph->edge[1].src = 0;
    graph->edge[1].dest = 2;
    graph->edge[1].weight = 6;
    graph->edge[2].src = 0;
    graph->edge[2].dest = 3;
    graph->edge[2].weight = 5;
    graph->edge[3].src = 1;
    graph->edge[3].dest = 3;
    graph->edge[3].weight = 15;
    graph->edge[4].src = 2;
    graph->edge[4].dest = 3;
    graph->edge[4].weight = 4;
    // 使用Kruskal算法求解最小生成树
    kruskalMST(graph);
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#define MAX_EDGES 100
#define MAX_VERTICES 100
// 表示图中的一条边
typedef struct {
    int u, v, weight;  // 边的两个顶点及权重
} Edge;
// 表示整个图
typedef struct {
    int n, m;  // 图中顶点数和边数
    Edge edges[MAX_EDGES];  // 图中的边
} Graph;
int parent[MAX_VERTICES];  // 并查集的父节点数组
// 初始化并查集，将顶点x作为一个单独的集合
void makeSet(int x) {
    parent[x] = x;
}
// 查找顶点x所在集合的根节点，采用路径压缩
int findSet(int x) {
    while (x != parent[x]) {
        x = parent[x];
    }
    return x;
}
// 合并包含顶点x和顶点y的两个集合
void unionSet(int x, int y) {
    int rootX = findSet(x);
    int rootY = findSet(y);
    parent[rootX] = rootY;
}
// 交换两条边的函数
void swap(Edge* a, Edge* b) {
    Edge t = *a;
    *a = *b;
    *b = t;
}
// 对图中的边按权重进行排序
void sortEdges(Graph* graph) {
    int i, j;
    for (i = 0; i < graph->m - 1; i++) {
        for (j = 0; j < graph->m - i - 1; j++) {
            if (graph->edges[j].weight > graph->edges[j + 1].weight) {
                swap(&graph->edges[j], &graph->edges[j + 1]);
            }
        }
    }
}
// 使用Kruskal算法寻找最小生成树
void kruskal(Graph* graph) {
    int i, totalWeight = 0;
    for (i = 0; i < graph->n; i++) {
        makeSet(i);  // 初始化每个顶点为一个单独的集合
    }
    sortEdges(graph);  // 对边按权重进行排序
    printf("Minimum Spanning Tree:\n");
    for (i = 0; i < graph->m; i++) {
        int rootU = findSet(graph->edges[i].u);  // 查找边的两个顶点所在集合的根节点
        int rootV = findSet(graph->edges[i].v);
        if (rootU != rootV) {  // 如果两个顶点不在同一个集合中，说明加入这条边不会形成环路
            printf("Edge %c-%c: %d\n", 'a' + graph->edges[i].u, 'a' + graph->edges[i].v, graph->edges[i].weight);  // 输出该边
            totalWeight += graph->edges[i].weight;  // 累加总权重
            unionSet(rootU, rootV);  // 将这两个顶点所在集合合并
        }
    }
    printf("Total Weight: %d\n", totalWeight);  // 输出最小生成树的总权重
}
int main() {
    // 创建一个包含5个顶点和7条边的图
    Graph graph = {5, 7, {{0, 4, 1}, {0, 1, 3}, {4, 1, 4}, {4, 2, 6}, {4, 3, 7}, {1, 2, 5}, {2, 3, 2}}};
    kruskal(&graph);  // 寻找最小生成树
    return 0;
}