最小生成树prim的时间复杂度
时间: 2024-05-24 11:08:43 浏览: 213
最短生成树的Prim算法
5星 · 资源好评率100%
最小生成树Prim算法的时间复杂度为O(ElogV),其中E为边数,V为顶点数。具体实现方式为从任意一个点开始,不断地向外扩张,每次选择连接当前点集和未连接点集的边权值最小的那个点加入当前点集中,直到所有点都加入点集为止。这个过程中,需要用一个优先队列来维护每个点到当前点集的最短距离,所以时间复杂度为O(ElogV)。
阅读全文
最短生成树的Prim算法