Вопрос по algorithm, c++, stl – Найти, если элемент уже существует в очереди STL

5

Я использую очередь STL для реализации BFS (поиск в ширину) на графике. Мне нужно вставить узел в очередь, если этот узел уже не существует в очереди. Тем не менее, очередь STL делаетне разрешать итерацию по его элементам и, следовательно, я не могу использовать функцию поиска STL.

Я мог бы использовать флаг для каждого узла, чтобы отмечать их, когда они посещаются, и нажимать их только тогда, когда флаг ложен, однако мне нужно запускать BFS несколько раз, и после каждого раза мне придется сбрасывать все флаги, поэтому я закончил использовать счетчик вместо флага, но я все же хотел бы знать, существует ли стандартный способ поиска элемента в очереди.

@Vikas: я считаю, что это эквивалентно назначению счетчика для каждого узла. Ari
каждый узел в BFS проходит три состояния: не посещено, посещено, но не завершено, завершено. Я действительно не знаю, что вы имели в виду, назначая счетчики для каждого узла. Но если вы можете добиться поддержания трех состояний узла, вы можете использовать его. Vikas
То, что вы хотите, это отдельное хранилище данных для хранения цвета узлов в вашем графике. Если каждый узел имеет уникальный идентификатор, который можно использовать в качестве ключа, то вы можете использоватьstd::map хранить цвет (белый, серый, черный) узлов. Это будетO(log(n) какstd::map реализован в виде дерева RB в большинстве реализаций. Vikas

Ваш Ответ

1   ответ
6

Я предполагаю, что вы реализуете концепцию "закрытого набора". в вашем BFS? Стандартный способ сделать это состоит в том, чтобы просто поддерживать отдельныйstd::set или жеstd::unordered_set элементов уже встречались. Таким образом, вы получите O (LGn) или O (1), при переборе очереди, если бы она была поддержана, потребовалось бы O (nВремя

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded Ari
Error: User Rate Limit Exceeded
Error: User Rate Limit ExceedediError: User Rate Limit ExceededcError: User Rate Limit Exceeded Ari
Error: User Rate Limit Exceeded Ari

Похожие вопросы