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)、そしてその理由についての直感が本当にありがたいです。ありがとうございます
ベストアンサー1
あなたの合計
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)。