[解決済み] DFSとBFSの時間計算量がともにO( V + E )であるのはなぜか？

質問

BFSの基本的なアルゴリズムです。

set start vertex to visited

load it into queue

while queue not empty

   for each edge incident to vertex

        if its not visited

            load into queue

            mark vertex

だから、時間的な複雑さは、そうだろうと思います。

v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges) 

ここで v は頂点 1 から n

まず、私が言ったことは正しいのでしょうか？ 次に、この O(N + E) と、その理由を直感的に教えていただけると本当に助かります。 ありがとうございます。

どのように解決するのですか？

あなたの合計

v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges)

は次のように書き換えることができます。

(v1 + v2 + ... + vn) + [(incident_edges v1) + (incident_edges v2) + ... + (incident_edges vn)]

で、最初のグループは O(N) であるのに対し、もう一方は O(E) .