alexeykuzmin0 Nov 1 2013 at 18:08

Графы для самых маленьких: BFS 0-1

2 min

25K

Comments 3

DZhon Nov 3 2013 at 09:30

Позвольте, а почему не используется std::priority_queue?
В таком случае вставка в начало/конец определяется приоритетом и временная сложность на обе эти операции гарантирована быть O(logn) из-за свойств нижележащей кучи.
Появляется, конечно, небольшой оверхэд по памяти на хранение приоритета.

alexeykuzmin0 Nov 4 2013 at 01:32

priority_queue, насколько я помню, организована на основе бинарной кучи. Во-первых, это работает в log V раз дольше, а во-вторых, это уже будет алгоритм Дейкстры, который я расскажу чуть позже. Целью этого поста было рассказать именно про BFS 0-1.

DZhon Nov 4 2013 at 10:44

Не подумал, что вставка/удаление именно в начале или конце является константной по времени. Ваша правда.

Show the best of all time