浅入浅出数据结构(25)——最小生成树问题 (4)

  

浅入浅出数据结构(25)——最小生成树问题

  接着处理边[v3,v4],其连接的v4未知,将v4设为已知,连起来:

  

浅入浅出数据结构(25)——最小生成树问题

  接着处理边[v1,v4],其连接的两个顶点均为已知,故跳过

  接着处理边[v4,v6],其连接的v6未知,将v6设为已知,连起来:

  

浅入浅出数据结构(25)——最小生成树问题

  接着处理边[v2,v5],其连接的v2和v5均为未知,所以将v2、v5均设为已知,连起来(注意,此时产生了两棵树):

  

浅入浅出数据结构(25)——最小生成树问题

  接着处理边[v5,v6],其连接的顶点均为已知,但是v5和v6处于不同的树,所以我们将其连起来(这部分的相关判断和处理需要树的集合知识,以及不相交集数据结构):

  

浅入浅出数据结构(25)——最小生成树问题

  接下来处理的所有边都是所连接顶点已知,且所连接顶点处于同一棵树中,所以均会跳过,然后算法结束。

 

 

  没有掌握住博文的顺序和铺垫,实在是失败 ̄△ ̄

  不过Kruskal算法的思路我想我应该讲清楚了,就是Dijkstra算法和Prim算法的讲解可能太生硬了一些,但是细细地读、细细地理解、细细地过一遍,应该还是能明白的◑ω◐

 

  这个系列的博文的主体部分到这儿就算结束了,从第一篇博文一路看到这儿的话,基本的数据结构和算法应该都能掌握。而像什么B+树、红黑树、算法设计技巧等更特殊的知识我没有算在主体部分中,以后可能会以“浅入浅出数据结构(附)”的标题形式写出。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpsjww.html