Для поиска в ширину вам нужно хранить как минимум две вещи. Один - это набор уже посещенных узлов, а другой - набор узлов, к которым можно напрямую добраться из посещенных узлов, но которые сами не посещаются. Затем вы продолжаете перемещать состояния из последнего набора в первый, добавляя недавно достижимые состояния ко второму. Если вам нужен путь от корня до какого-либо узла (ов), вам также необходимо сохранить родительский узел для каждого узла (кроме корня) в вышеупомянутых наборах.
Обычно объединение набора посещенных узлов и набора непосещенных дочерних узлов (то есть набора видимых узлов) сохраняется в хэш-таблице. Это должно быть в состоянии быстро определить, было ли «новое» состояние замечено ранее, и игнорировать его, если это так. Если у вас действительно большое количество состояний, вам действительно может понадобиться битовый массив (как упомянул Джозеф Буй ( 57509 )), но если ваши состояния не могут использоваться (прямо или косвенно) в качестве индексов для этого массива, вы потребуется использовать хеш-функцию для сопоставления состояний с индексами. В последнем случае вы можете полностью игнорировать определенные состояния, потому что они отображаются на тот же индекс, что и другой (и видимый) узел, поэтому вы можете быть осторожны с этим. Кроме того, чтобы получить путь, вам все равно нужно хранить родительскую информацию, которая в значительной степени сводит на нет использование битового массива.
Набор не посещенных, но видимых узлов может быть сохранен в виде очереди. (Битовые массивы для этого набора бесполезны, потому что массив будет в основном пустым, а поиск следующего установленного бита относительно дорог.)