C 语言 Kruskal 算法

贪婪的 Kruskal 方法在连接的加权网络中搜索最快的路线。在此算法中，我们从一个空边集开始，一次将一条边添加到该集中，直到获得生成树为止。

Kruskal 方法是一种用于确定连接的加权网络中最短生成树的著名算法。最小生成树是一棵使用尽可能少的总边权重连接图中每个节点的树。

该算法按升序考虑图中所有边的权重，并将它们添加到最小生成树中，前提是它们不会与树中已有的边形成环。Kruskal 方法采用不相交集数据结构来防止形成环。

特性

• 如果一条边不会与树中已有的边形成环，则该方法按升序考虑图中所有边的权重，并将它们添加到最小生成树中。
• 该算法维护一组不相交的顶点子集，每个子集代表图的连通分量。随着边被添加到选定集中，子集会被合并，直到所有顶点都属于同一个子集。

用途

Kruskal 算法可用于各种应用，例如网络设计、聚类和图像分割。它经常用于工程、计算机科学和其他需要图分析的学科。

Kruskal 算法的步骤如下

• 按非递减顺序对所有边按权重排序。
• 初始化一个用于最小生成树的空集和一个空的不相交集数据结构。
• 对于排序顺序中的每条边，如果添加该边不会导致循环，则将该边添加到树中，并在不相交集数据结构中合并该边的两个端点所属的集合。
• 重复步骤 3，直到考虑了所有边，或者最小生成树包含 n-1 条边（其中 n 是图中的节点数）。
• 算法结束时，最小生成树将是步骤 3 中添加到树中的边集。Kruskal 算法的时间复杂度，其中 E 是边数，V 是图中的顶点数，为 O(ElogE) 或 O(ElogV)。

以下是 C 语言实现 Kruskal 算法的代码

C 语言程序

此代码从用户那里读取图的顶点数和边数，以及边及其权重。然后，它在图上运行 Kruskal 算法并打印出最小生成树。

C 语言实现 Kruskal 算法的输入和输出

输入

输出

Minimum Spanning Tree:
(0, 1) -> 2
(1, 2) -> 3
(1, 4) -> 5
(0, 3) -> 6

在此示例中，输入指定了一个具有 5 个顶点和 7 条边的图。然后从用户那里读取边权重。Kruskal 算法的输出显示了构成最小生成树的边。

优点

• Kruskal 算法易于实现和理解。
• 它能在合理的时间内找到图的最小生成树，因此适用于大型图。
• 该算法适用于各种应用。

缺点

• 该算法可能找不到图中唯一的最小生成树，因为可能存在具有相同总权重的多个最小生成树。
• 该算法需要按权重对图的边进行排序，这对于大型图可能耗时。
• 该算法需要额外的空间来存储顶点的不相交子集。

结论

Kruskal 算法是一种简单有效的确定图的最小生成树的方法。E 是图中边的数量，其时间复杂度为 O(E log E)。因此，它适用于大型图。