Динамическая очередь для эффективной реализации алгоритма Breadth-First

Question

Я нахожусь в процессе построения алгоритма поиска по графу в ширину для поиска в лондонском метро.

Я понял алгоритм, но, как вы, наверное, знаете, алгоритм требует ADS очереди вЧтобы отслеживать все ребра, которые нужно искать (в правильном порядке).

Я читал о проблемах эффективности, связанных с управлением очередью и большим или очень большим количеством элементов в очереди (ребер).

Может кто-нибудь сказать, пожалуйста, как реализовать на основе очередивокруг Java ArrayList, который может отслеживать голову и хвост и эффективно управлять памятью во время ее роста?

Любые советы / указатели очень ценятся !!

Answer 1

Имейте в виду, что вам понадобится быстрый тест, чтобы увидеть, находится ли ваш объект в очереди или нет.Ни ArrayList, ни Queue не предоставляют эту функцию (их contains проверка O(n)).Если вы можете изменить объекты, с которыми вы имеете дело, добавив дополнительное поле, то это легко.Если нет, вам нужно будет поддерживать какой-то быстрый Set (вероятно, HashSet), чтобы отслеживать, какие объекты находятся в очереди.

Answer 2

Я думаю, что ваш вопрос тесно связан с этой темой: Поиск в ширину в Java

Не используйте ArrayList, если у вас нет действительно веских причин. Java уже поставляется с большим набором реализаций очереди - подробности смотрите в интерфейсе Queue .

В вашем случае может быть достаточно выбрать LinkedList в качестве реализации очереди. См. Также http://www.codeproject.com/KB/java/BFSDFS.aspx для простого примера реализации поиска в ширину, которая использует LinkedList в качестве очереди.