Comments 3
Позвольте, а почему не используется std::priority_queue?
В таком случае вставка в начало/конец определяется приоритетом и временная сложность на обе эти операции гарантирована быть O(logn) из-за свойств нижележащей кучи.
Появляется, конечно, небольшой оверхэд по памяти на хранение приоритета.
В таком случае вставка в начало/конец определяется приоритетом и временная сложность на обе эти операции гарантирована быть O(logn) из-за свойств нижележащей кучи.
Появляется, конечно, небольшой оверхэд по памяти на хранение приоритета.
0
priority_queue, насколько я помню, организована на основе бинарной кучи. Во-первых, это работает в log V раз дольше, а во-вторых, это уже будет алгоритм Дейкстры, который я расскажу чуть позже. Целью этого поста было рассказать именно про BFS 0-1.
0
Sign up to leave a comment.
Графы для самых маленьких: BFS 0-1