реализация BFS на узлах с отрицательным номером
Мы можем легко реализовать алгоритм поиска в ширину, если узлы или вершины нумеруются в C ++ положительно.
Но как с этим бороться, когда узлы или вершины нумеруются отрицательно.
Предположим, что узел имеет номер -200, и если мы назначим bool visited[-200] = true or false тогда это приведет к ошибке во время выполнения.
Какой будет подход в этом случае?
Решение
«если узлы нумеруются отрицательно» ~> В случае, если вам нужно, чтобы у каждого узла был уникальный идентификатор, который будет использоваться для доступа к этим узлам в некоторых контейнерах, нет причин, по которым вы бы допустили, чтобы значение такого идентификатора было отрицательным.
Так же, как вы указали: visited[-200] = true; не имеет смысла. В случае, если вам нужно, чтобы каждый узел имел уникальный id / index делайте это независимо от значения, хранящегося в нем, т.е.
struct Node {
unsigned int id;
int value;
...
};
Другие решения
При работе с графическими метками разумным подходом является использование карты недвижимости (см., например, Boost Graph Library. Основная идея состоит в том, чтобы получить доступ к свойствам узла с помощью структурированного подхода, при котором детали свойств фактически являются доступными в зависимости от используемой конкретной карты свойств.
Исходя из того, что вы говорите, вы получаете доступ к меткам, используя идентификатор узла. Существует два очевидных подхода с несколько различными характеристиками в зависимости от фактического расположения идентификаторов:
- Если метки узлов относительно плотны и диапазон идентификаторов узлов значений известен, использование массива с подходящей корректировкой с использованием смещения является разумным подходом. То есть вы бы использовали массив как
label[nodeID - minNodeID], - Если метки узла распределены случайным образом, вы бы использовали ассоциативный контейнер с идентификатором узла в качестве ключа контейнера.
Если вы можете управлять макетом представления вашего узла, вам, вероятно, следует рассмотреть возможность хранения меток в узле, особенно если идентификаторы узлов распределены случайным образом.
detector