最小生成树---Prime算法和Kruskal算法

序言

生活中最小生成树,的实例非常常见,它可以用来花费最小的代价两两联通。如城市之间如何修建公路,铺设电话线路之类的。希望注意的是这里生成的是最小联通图,而不是最短路径。。反例很容易举出来,在此不做解释了。 很遗憾,这两种算法都是只能解决的无向图的最小生成树。如果是有向图呢?有解决办法吗?答案是肯定的。而且还是中国人发明了,1965年有中国人朱永津和刘振宏。证明中华民族还是挺有创造力的,只是教育事业一直被耽误~ 题外话:这两位在1965年发明的这种算法,按照年龄推算,他们受到教育水平还是民国时期的教学机制,不多BB(逃)

Prime算法

此算法的核心是贪心。

  1. 清空生成树,任取一个顶点加入生成树

  2. 在那些一个端点在生成树里,另一个端点不在生成树里的边中,选取一条权最小的边,将它和另一个端点加进生成树

  3. 重复步骤2,直到所有的顶点都进入了生成树为止,此时的生成树就是最小生成树

代码实现

Kruskal算法

此算法的核心也是贪心。

  1. 新建图G,G中拥有原图中相同的节点,但没有边;

  2. 将原图中所有的边按权值从小到大排序;

  3. 从权值最小的边开始,如果这条边连接的两个节点于图G中不在同一个连通分量中,则添加这条边到图G中;

  4. 重复3,直至图G中所有的节点都在同一个连通分量中。

代码实现

坚持原创技术分享,您的支持将鼓励我继续创作!
  • 本文作者: 带带蓝蜗牛
  • 本文链接: 254.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处!