我连接了无向图 . 我正在寻找构建图的 balancer 生成树（T）的方法
具体关于 balancer 生成树，我可以定义如下：
-
如果树的根是r . 所有节点都可以划分为等级 . 即，与r（在T中）的距离为j的所有节点都在Lj等级中 .
-
对于每个节点w，可以为T的子树T_w定义，使得w是其根 .
-
目标是以这样的方式定义生成树：对于每个级别Li，对于级别Li中的每两个节点u和v，T_u和T_v中的节点数量是最大等效的 .
是否有人可以建议任何算法用于构建这种“相对” balancer 的生成树？
先感谢您 .
3 回答
我不确定你的表达“最大等价” .
这个问题可能没有一个完美的解决方案，所以显而易见的是我们能做得多好吗？
一般性的这个问题似乎是NP-Complete . 如果幸运的话，一些贪婪的方法可能会产生恒定的近似算法 .
这似乎是微不足道的 . 设G就是你的图 . 它是连接的，因此每对顶点之间有一条边 . 使用该定义，构造一个任意 balancer 生成树G'，其顶点数与G相同 . 从G ' and an arbitrarily chosen vertex of G, map each vertex in G'中的r开始到G中的顶点 . 删除G中的所有边缘't have a corresponding edge in G' .
得到的图形 - 将其称为“更新的G” - 通过构造具有与G'相同的顶点数量，并且通过构造，如果相应的边缘存在于G'中，则在U中存在边缘 . 因此U = G'，因此U是 balancer 生成树 .
您希望将树构造为AVL tree .
您可以在page 12 of this PDF document上找到用于实现它的其他信息和代码 .
This PowerPoint document有一些漂亮的图片来帮助解释正在发生的事情，还包括AVL Tree数据类型的Java实现 .