如何建立gazebo world model

[TOC]

最小生成树。

Kruskal算法

由美国数学家Joseph Kruskal 1956年发现。

思路是：使用优先队列（边的权重排序）和并查集（UF）

• 创建一个queue，保存最小生成树的边
• 创建一个集合S（优先队列），包含图中的所有边
• 创建一个并查集UF，包含图中的所有顶点（所有顶点看做单独的树）
• 当集合非空时或者queue的大小小于V-1时（最小生成树最多为V-1条边）
  • 删除集合S中的最小权重的边
  • 如果这条边连接了两个不同的树（没有环出现，UF.connected）， 把这条边加到queue中，将两棵树合并成一棵树（UF.union）