Господа, подскажите, почему у Breadth-first search сложность O(V + E)

Question

Господа, подскажите, почему у Breadth-first search сложность O(V + E)

если есть список с проверенными элементами? У нас же в худшем случае будет итерация через каждую ноду (значит уже O(V) ), плюс будет проход через всех соседей у каждой из нод, что даст O(E). То есть по сути два вложенных цикла. А это будет O(V * E) Почему тогда пишут что O(V + E) ?

#database #programming #russian #software

0

03.01.2022