Leader
Leader
发布于 2023-09-25 / 20 阅读 / 0 评论 / 1 点赞

最小生成树算法

最小生成树算法

在了解最小生成树之前,我们需要了解什么是连通图

所谓连通图,即任意一个顶点都与另外任意一个顶点连通的图

生成树即在遍历连通图时所走过的顶点及边的连通子图

最小生成树即对于有权值边的图中,边的权值之和最小的生成树

最小生成树算法:Kruskal算法和Prim算法

Kruskal算法

将连通图的边按从小到大的顺序依次排列,并从小到大遍历边,若将该条边添加到生成树后不构成回环,则将该条边加入树。

构成回环的条件:该条边的两个端点的终点都不想用即不构成回环,反之则构成回环。

终点:与该顶点连接的索引最大的顶点即为终点,若该顶点不与任何顶点连接(即初始状态),则该顶点的终点为其本身。

Prim算法

将连通图的顶点分为两类,一类为已添加的顶点(称为a类),另一类为除已添加的顶点之外的顶点(称为b类)。

先将任意一点加入a类,然后循环遍历a类顶点的边,将与已连接a类顶点且其另一顶点不与a类权值最小的边添加到生成树中,直到b类中无顶点为止,最后所得的即为最小生成树。


评论