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

实验名称：图的最小生成树算法设计

（1）实验目的：

掌握最小生成树算法，利用kruskal算法求解最小生成树。

（2）主要内容：

利用kruskal算法求一个图的最小生成树，设计Kruskal算法求解邻接矩阵存储结构下图的最小生成树的函数，并以下图为例设计一个主函数进行测试，要求输出最小生成树的各顶点及各边的权值。

边a-e的权值为1
边a-b的权值为3
边e-b的权值为4
边e-c的权值为6
边e-d的权值为7
边b-c的权值为5
边c-d的权值为2

知识储备

最小生成树（Minimum Spanning Tree，MST）是一种常见的图论算法，用于在一个加权连通图中寻找一棵生成树，使得树的所有边的权值之和最小。其中，Kruskal算法和Prim算法是两种常用的最小生成树算法。

1. Kruskal算法：

   • Kruskal算法是一种贪心算法，它通过将图中的所有边按权值从小到大进行排序，然后逐个考虑这些边，如果加入某条边不会构成环，则将其加入最小生成树中。这样直到最小生成树中包含了图中的所有顶点为止。
   • Kruskal算法适合于稀疏图，即顶点较多而边较少的图。

2. Prim算法：

   • Prim算法也是一种贪心算法，它从一个初始顶点开始，逐步长出最小生成树。在每一步中，选择与当前最小生成树相邻且权值最小的边所连接的顶点，并将该顶点加入最小生成树中。
   • Prim算法适合于稠密图，即顶点较少而边较多的图。

这两种算法都可以求解最小生成树，选择哪种算法取决于具体的应用场景和图的特点。在实际应用中，可以根据图的规模、边的数量、以及算法实现的难易程度等因素来选取合适的算法。

下面是使用C语言实现Kruskal算法来求解最小生成树的示例代码：

#include 
#include 
#include 

// 定义边的数据结构
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

在这个示例中，我们定义了结构体Edge来表示边，并使用结构体Graph来表示图。在main函数中，我们创建了一个包含四个顶点和五条边的图，并使用Kruskal算法来求解最小生成树，然后打印出最小生成树的边及权重。

• 这段C语言代码实现了Kruskal算法来求解最小生成树。让我来解释一下主要的步骤和代码逻辑：

• 1. 首先定义了表示边的结构体Edge，包括边的起点、终点和权重；定义了表示图的结构体Graph，包括顶点数、边数和边的数组。

• 2. 创建图的函数createGraph用于动态分配内存并初始化一个图的结构体。

• 3. 实现了find函数和Union函数来进行并查集操作，用于判断两个顶点是否连通以及合并不同的连通分量。

• 4. kruskalMST函数实现了Kruskal算法的核心逻辑。首先对所有边按照权重进行排序，然后遍历排序后的边数组，依次加入到最小生成树中，直到最小生成树中有V-1条边为止。在加入边的过程中，使用并查集来判断是否形成环路，从而保证最小生成树的连通性。

• 5. 在main函数中创建一个包含四个顶点和五条边的图，并手动设置每条边的起点、终点和权重。然后调用kruskalMST函数求解最小生成树，并打印出最小生成树的边及权重。
     -总体来说，这段代码通过实现Kruskal算法的关键步骤，使用并查集来维护最小生成树的连通性，以及对边进行排序和筛选，最终得到了输入图的最小生成树。希望以上解释能够帮助你理解这段代码的实现原理。

以下是基于邻接矩阵存储结构的 Kruskal 算法的 C 语言代码，用于找到图的最小生成树。在这个例子中，我将使用您提供的图来测试最小生成树的算法。

问题描述

1. 将图中的所有边按照权值从小到大进行排序。
2. 依次遍历排序后的边，如果当前考虑的边连接的两个顶点不在同一个连通分量中，则将该边加入最小生成树中，并合并这两个顶点所在的连通分量。
3. 重复步骤2，直到最小生成树中有n-1条边为止（n为顶点数）。

基本要求

1. 输入：从标准输入或文件中读取图的顶点数、边数以及各条边的起点、终点和权值。
2. 输出：将最小生成树的每条边及其权值输出到标准输出或文件中。
   正确性：确保程序能够正确地找到给定图的最小生成树。
3. 效率：保证算法的时间复杂度在合理范围内，尽量提高程序的执行效率。

算法思想

Kruskal算法是一种用来寻找最小生成树的贪心算法。最小生成树是指在一个连通的无向图中找到一棵包含图中所有顶点的生成树，并且使得这棵树的边的权重之和尽可能小。

Kruskal算法的主要思想是通过不断地选择图中权重最小的边，并且保证不形成环路，逐步构建最小生成树。具体来说，算法按照边的权重从小到大的顺序进行处理，每次选择一条权重最小的边，如果这条边连接了两个不在同一个连通分量中的顶点，那么就将这条边加入最小生成树中，并且合并这两个连通分量，直到最小生成树中包含了图中所有的顶点为止。

模块划分

这段代码可以划分为几个功能模块：

1. 数据结构定义模块：

   • 定义了表示图中边的数据结构 Edge；
   • 定义了表示整个图的数据结构 Graph。

2. 并查集相关函数模块：

   • makeSet(int x)：初始化并查集，将顶点x作为一个单独的集合；
   • findSet(int x)：查找顶点x所在集合的根节点，采用路径压缩；
   • unionSet(int x, int y)：合并包含顶点x和顶点y的两个集合。

3. 辅助函数模块：

   • swap(Edge* a, Edge* b)：交换两条边的函数；
   • sortEdges(Graph* graph)：对图中的边按权重进行排序。

4. Kruskal算法实现模块：

   • kruskal(Graph* graph)：使用Kruskal算法寻找最小生成树。

在文件组织结构上，可以将这些函数放在同一个源文件中，比如 kruskal.c，然后在主程序文件中调用这些函数即可。当然，也可以根据需要将这些函数分别放在不同的文件中，并通过头文件来进行声明和引用。例如，可以创建 graph.h 和 graph.c 来存放数据结构定义和相关操作函数，以及 kruskal.h 和 kruskal.c 来存放Kruskal算法实现相关的函数。

数据结构

边的数据结构 Edge：

用于表示图中的一条边，包括这条边连接的两个顶点（u, v）以及边的权重。
在代码中被定义为一个结构体，包括三个整型成员 u、v 和 weight。
图的数据结构 Graph：

用于表示整个图，包括图中顶点数 n、边数 m，以及边的具体信息。
在代码中被定义为一个结构体，包括两个整型成员 n 和 m，以及一个 Edge 类型的数组 edges。

#include 
#include 

#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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

存在的问题和建议

可能存在的问题：

代码中未进行输入校验，如果输入的图不符合预期格式，可能会导致程序出错。
如果图中存在负权边，Kruskal 算法可能无法得到正确的最小生成树。代码中未对此进行处理。

建议：

可以添加输入校验的部分，确保输入的图符合预期格式。
对于负权边的情况，可以在算法中进行处理，或者在输入时进行限制。