通过选择根节点来减少宽度优先树的深度

如果可以在图中随机挑选根节点，是否存在一个现有算法来挑选根节点，从而导致宽度优先树的深度或高度最小？通过选择根节点来减少宽度优先树的深度

我有一种预感，我应该选择与最大的风机节点出作为根节点。

让我举一个例子。有一个循环有向图{（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

来源

2013-06-26 cxf54

做BFS时可以重复节点吗？我们可以假设图是非循环的，或者至少有一个没有外出边的节点（在这种情况下问题真的很容易）？ – Dukeling

节点由于白灰黑色标记而不能重复。图是循环的。 – cxf54

BFS是否需要跨越整个图形？例如，在这样的图表中：'1-> 2-> 3-> 4'，选择'4'作为根将会使深度为1，因为它不能被扩展。这种情况下期望的行为是什么？你是否有资格任何叶作为查询的答案？ – Sailesh

我假设你说的是加权图，否则它不会使以root身份从不同节点进行BFS的差异很大。

一个朴素的蛮力方法是将图的每个节点视为根，并构造BFS树。每次测量高度并在将所有节点作为根覆盖之后，我们得到BFS树产生最小高度的节点。做到这一点，你最终可能会花费指数的时间。时间：O(n * (v + e) + logxn)为每个节点我们做每个树的BFS +我们计算树中的高度x级别。但我怀疑动态编程我们可以把这个时间带到一个更可管理的水平。由于我们将结果存储在每个阶段，因此我们可以将其用于以后的计算。

想到的另一种方法是optimal binary search tree.你要做的是处理你的图&整理每个节点的权重到一个数组中。使用这个权重，我们将构建一个BST，使得具有最大权重的节点将落在BST的根部附近，并且具有较少权重的节点在BST中会下降（有些可能与叶子相同）。通过这种方式在BST中搜索您找到节点的可能性会更好。

更新：对上述方法扩展 - enter image description here

以上递归很简单，通过一个我们一个尝试每个节点根r。 r从i to j变化。我们递归计算从r到r-1和r + 1到j的最优代价，其中r代表根。我们加上从i到j的权重（或频率）的总和（参见上面的公式中的第一项），因为每次搜索都会经过根并且每次搜索都会进行一次比较，所以添加了这个总和。

希望这有助于...

来源

2013-06-26 07:22:03

通过选择根节点来减少宽度优先树的深度

回答

相关问题