Это свойство позволяет использовать простую очередь вместо очереди с приоритетами. Неплохо, учитывая, что время добавления и удаления элемента для первой в худшем случае равно O(1) (тогда как для куч, например, эти операции выполняются за O(log(n))), что обеспечивает линейное время работы BFS. В худшем случае оно будет линейно зависеть от наибольшего числа вершин и ребер, то есть O(|V| + |E|). Для связных графов эту оценку можно упростить до O(|E|).