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