数据结构与算法之带权图的最小生成树

时间:2021-12-04 12:36:47

 

  http://blog.csdn.NET/xinzhi8/article/details/62222154 图介绍与深度优先搜索

  http://blog.csdn.Net/xinzhi8/article/details/62222154 广度优先搜索

  http://blog.csdn.net/xinzhi8/article/details/63682781 有向图的拓扑排序


 数据结构与算法之带权图的最小生成树

如图,有abcdef,6个城市,数字为城市之间路径长短,现在要造路,从a-f,现在从a点出发,怎么选择路径可以用最短距离到达f。

不妨我们先脱离程序,用现实生活中的经验去思考这问题。

即:

1,要从A点开始造路,那我先在A点设立办事处(办事处的重要性在后面的探索过程中很重要),派2名技术人员去探索到B,D的路径长短。

得知:AB6,AD4,将这2条数据发送给总部(总部很重要,它将决定留下哪些数据,决定选择哪个数据造路),每一次的探索反馈给总部,总部便去派发一个造路的路径。

2,第一次探索完成后,总部拿到AB6,AD4数据,选择最小路径AD4去造路,AD4数据删除同时在D出设立办事处,从D处派遣技术员去探索,根据图信息可知,探索结果应该是DA4,DB7,DC8,DE12,注意:因为A出已经设立了办事处,因此到A处的路径已经考虑过了,不需要再次考虑。因此返回给总部的数据应该是DB7,DC8,DE12,还有原先第一次探索的数据AB6,现在总部手里有4条数据(DB7,DC8,DE12,AB6)。仔细看看这4条数据,到B点有2条数据分别是DB7,AB6。所以总部删除DB7数据(此处便是图的剪边)。最终总部手里有(AB6,DC8,DE12)。

3,根据数据,总部决定造AB这条路径,从数据中删除AB6,同时在B处设立办事处,以此类推。


全部过程如下:

数据结构与算法之带权图的最小生成树

1,办事处的作用就是以后探索时,有办事处的顶点不用再次探索。

2,每次探索完成后,要进行剪边操作,即只保留到达一个顶点的最小路径。

2,过程中的优先级集合便是总部保存的路径数据,优先级集合中必须保证到达同一处顶点的路径只有一个,这一路径便是到达同一个顶点所有路径中最短的那条。优先级集合用堆的思想设计。


主体思想便是这样,下面上代码说话。

数据结构与算法之带权图的最小生成树


数据结构与算法之带权图的最小生成树

 优先级PQ,用堆的思想设计,这里用数组实现,将路径最小的放在最后面,游标始终指向最小值

数据结构与算法之带权图的最小生成树

下面是Edge与Vertex类

数据结构与算法之带权图的最小生成树

数据结构与算法之带权图的最小生成树


 其余算法部分与前两篇博文一致,不再阐述

此篇文章参考Java数据结构算法,转载请标识来源。

 要源码可向我留言。