教程目录

想要实际看看算法是如何工作的吗?

通过交互式可视化深入理解算法运行过程

查看算法可视化

Kruskal最小生成树算法

介绍

Kruskal算法是一种用于带权无向图的最小生成树算法,该算法基于贪心策略,通过选择权值最小的边构建最小生成树。

最小生成树是图中连接所有顶点的一个子图,它是一棵树(无环连通图),且所有边的权重总和最小。

算法步骤

  1. 将图中所有边按权重从小到大排序
  2. 创建一个森林(每个顶点初始时是一棵独立的树)
  3. 按排序后的顺序处理每条边(u, v):
    • 如果顶点u和v不在同一个连通分量中(即不在同一棵树中)
    • 则将这条边加入最小生成树中
    • 合并包含u和v的两棵树(连通分量)
  4. 重复步骤3,直到最小生成树包含图中所有顶点(即V-1条边,其中V是顶点数)

算法详解

以共有6个顶点(A-F)和10条边的带权无向图为例:

  • A-B:权重3
  • A-C:权重1

...

目录