トポロジカルソートの計算量がわかりません。

Question

トポロジカルソート に関しての質問です。

BFSを利用したトポロジカルソート の計算量が頂点数n辺の数mのときO(m+n)というのはなぜでしょうか？
mがどこで出てくるのかがわからないです。
回答お願いします。

Comments

[maisumakun]

質問が重複していますので、どちらかを削除依頼したほうがいいかと思います。

Answer 1

O(n+m)って言うとわかりづらい(教科書に書いてあったんでしょうか？)ですが、ようはO(|V|+|E|)、つまりグラフの頂点(Vertex)と辺(Edge)の数です。
そしてこれはそのまんまbfsの計算量です。bfsは基本全ての頂点と辺を走査する必要があるのでその２つの合計が計算量になるんですね。
bfsのトポロジカルソートは最初に全頂点(|V|個)の辺数を数えた後にbfsしたりしてますが、V+(V+E)=2V+Eでも計算量では定数倍は無視するので結局O(|V|+|E|)です。