如果可以在图形中随机选取根节点，是否存在选择根节点的现有算法，使得生成的广度优先树具有最小的深度或高度？
我有一种预感，我应该选择具有最大扇出的节点作为根节点 .
让我举一个例子 .
有一个循环有向图{（0,1），（1,2），（1,5），（1,6），（2,3），（3,4），（4,2），（ 5,2），（6,0）}
如果节点0被选为根，则广度优先树为{（0,1），（1,2），（1,5），（1,6），（2,3），（3,4）}深度是5
如果节点6被选为根，则广度优先树为{（6,0），（0,1），（1,2），（1,5），（2,3），（3,4）}深度是6
1 回答
我假设你正在谈论一个加权图，否则它作为root从不同节点做BFS没有多大区别 .
一种天真的暴力方法是将图的每个节点视为根并构造BFS树 . 每次测量高度，在覆盖所有节点作为根之后，我们得到BFS树产生最小高度的节点 . 做到这一点，你最终可能会花费指数时间 . 时间：
O(n * (v + e) + logxn)对于每个节点我们为每棵树做BFS我们在树中计算高度x等级 . 但我怀疑动态编程我们可以把这个时间带到一个更易于管理的层面 . 由于我们在每个阶段存储结果，因此我们可以将其重复用于以后的计算 .想到的另一种方法是optimal binary search tree.您要做的是处理图形并将每个节点的权重整理成一个数组 . 使用这个权重，我们将构造一个BST，使得具有最大权重的节点将落在BST的根附近，而具有较小权重的节点将在BST中降低（一些可能作为叶子） . 这样，在BST中搜索您找到节点的可能性更好 .
update: 扩展上述方法 -
上面的递归很简单，我们逐个尝试每个节点作为root
r.r与i to j不同 . 我们递归地计算从i到r-1和r 1到j的最优成本，其中r作为根 . 我们从i到j添加权重（或频率）的总和（参见上面公式中的第一项），这是因为每次搜索都将通过root进行，并且每次搜索都会进行一次比较 .希望这可以帮助...