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 に答える