Prim Algoritm(最小生成树)

简介: Prim Algorithm。这个算法可以分为下面几个步骤:将顶点集V分成两个集合A和B,其中集合A表示目前已经在MST中的顶点,而集合B则表示目前不在MST中的顶点。在B寻找与集合A连通的最短的边(u,v),将这条边加入最小生成树中。

Prim Algorithm。这个算法可以分为下面几个步骤:

  • 将顶点集V分成两个集合A和B,其中集合A表示目前已经在MST中的顶点,而集合B则表示目前不在MST中的顶点。
  • 在B寻找与集合A连通的最短的边(u,v),将这条边加入最小生成树中。(此时,与(u,v)相连的顶点,不妨设为C,也应加入集合A中)
  • 重复第二步,直至集合B为空集。

最小生成树: 通俗地讲,就是使得图GG连通时,所选取的边的长度的和最小。

 

目录
相关文章
|
10月前
|
算法 C++
用prim和kruskal算法求最小生成树问题
用prim和kruskal算法求最小生成树问题
72 0
|
机器学习/深度学习 算法 程序员
【算法合集】深搜广搜Prim与Kruskal
广度优先搜索(BFS)又叫广搜,它像一个有远见的人,它是一层一层来实现搜索的,也挺像下楼梯的。 思路: 1.先初始化队列 q; 2.从起点开始访问,并且改变他的状态为已经访问; 3.如果他的队列非空,取出首个元素,将它弹出! 4.如果u == 目标状态,然后对所以与 u 邻近的点进入队列; 5.标记它已经被访问!...............
155 1
【算法合集】深搜广搜Prim与Kruskal
|
算法 调度
最小生成树(Prim、Kruskal)算法,秒懂!
在数据结构与算法的图论中,(生成)最小生成树算法是一种常用并且和生活贴切比较近的一种算法。但是可能很多人对概念不是很清楚,什么是最小生成树?
158 0
最小生成树(Prim、Kruskal)算法,秒懂!
Floyd-Warshall算法 五行解决 (最短路径)
Floyd-Warshall算法 五行解决 (最短路径)
Floyd-Warshall算法 五行解决 (最短路径)
|
存储 算法
Kruskal
复习acwing算法基础课的内容,本篇为讲解基础算法:Kruskal,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上。
90 0
Kruskal
|
算法
图论最短路及生成树(Prim,Djikstra,Spfa,Bellan-ford,kruskal,topsort)
图论最短路及生成树(Prim,Djikstra,Spfa,Bellan-ford,kruskal,topsort)
134 1