我知道 BFS 需要 O(n+m) 时间，其中 n 是节点，m 是弧。
在执行 BFS 时构建树怎么样？
只要在最坏的情况下树完全不平衡，它是否会增加另一个 n？
问问题
520 次
1 回答
3
不完全确定我是否在关注，但如果是：
它是否增加了另一个 n
您的意思是复杂性将是O(n+m+n)，请注意O(n+m+n) = O(n+m)，所以这里没有真正的问题。
树的构建可以在 中完成O(n+m)，因为它可以表示为一个数组a[1,...,n]，其中a[i] = j if and only if node i is connected to node j in the tree（以及根的特殊标记）
所以，在 BFS 期间，当节点v“发现”节点u时，你只需要做a[u]=v，这是在恒定时间内完成的，并且是精确地完成n的，所以总复杂度保持不变O(n+m)
于 2012-07-09T14:42:27.890 回答