【专题】最小生成树（prim算法、kruscal算法）

2023-12-16 05:16:25

目录

一、最小生成树

生成树中边的权值（代价）之和最小的树。
在这里插入图片描述

二、Prim算法

1. 算法思想

  • 设N=(V,{E})是连通网，TE是N上最小生成树中边的集合；
  • Step1:令U={u}，u∈V，TE={}；
  • Step2:在u∈U,v∈V-U的边(u,v)∈E中找一条代价最小的边(u,v)并入TE,v并入U；
  • Step3:重复Step2，直至U=V，T={U,{TE}}是N的最小生成树；
    在这里插入图片描述

2. 例题

在这里插入图片描述
在这里插入图片描述

3. 性能分析

  • 时间复杂度：O( n 2 n^2 n2) , 与网中的边数无关；
  • 适用于求边稠密的网的最小生成树；

三、Kruscal算法

1. 算法思想

  • 最小生成树上边权值之和最小，应使树上每一条边的权值尽量小；
  • Step1:令最小生成树T的初态为只有n个顶点的非连通图T=(V,{})；
  • Step2:从权值最小的边(u,v)开始，若该边依附的顶点落在TE的不同连通分量上，E=TE∪(u,v)，否则选择下一条代价最小的边；
  • Step3:重复Step2，直至T所有顶点在同一连通分量上；

2. 例题

在这里插入图片描述

3. 性能分析

  • 时间复杂度：O( e*log2e )；
  • 适合于求边稀疏的网的最小生成树；

文章来源:https://blog.csdn.net/qq_42340716/article/details/135014844
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。