幅優先探索の計算量

質問

グラフG=(V, E)における幅優先探索の計算量について質問です．

　ある頂点rから幅優先探索で頂点tを探すとき，何冊かの本を見ると「計算量は(|E|)」となっています．これを理解できません．

　ある頂点に対して，その隣接頂点にtが含まれるかどうかを検索する関数を作ったとします．各頂点に対してこの関数を高々一度ずつ呼び出すことで，その頂点に接続している辺が高々一度ずつ検索されるので，計算量はO(|V|+|E|)になるのではないのでしょうか? |E|>|V|を仮定しているのかとも思ったのですが，それ以降にも「O(|V|^2|E|)」というような記述が出てきます．

　どなたかご教授下さい．

回答No.1

gakutensoku

G=(V,E)をSimpleな連結無向グラフとすると、以下の関係が成り立ちます。

|V|-1 ≦ |E| ≦ |V|*(|V|-1)/2

この関係により、計算量O(|V|+|E|)は漸近的な意味において
O(|E|)と等しくなります。

O(n^2+n) = O(n^2)みたいな関係です。