4
Я использую очередь STL для реализации BFS (поиск по ширине первого) на графике. Мне нужно нажать узел в очереди, если этот узел уже не существует в очереди. Однако очередь STL делает not allow iteration through its elements, и поэтому я не могу использовать функцию поиска STL.Найти, если элемент уже существует в очереди STL
Я могу использовать флаг для каждого узла, чтобы пометить их при их посещении, и нажимать их только тогда, когда флаг является ложным, однако мне нужно запустить BFS несколько раз и после каждого раза мне придется сбросить все флаги , поэтому я использовал счетчик вместо флага, но мне все же хотелось бы знать, есть ли стандартный способ поиска элемента в очереди.
Для хранения цвета узлов на вашем графике требуется отдельный хранилище данных. Если каждый узел имеет уникальный идентификатор, который можно использовать как ключ, вы можете использовать 'std :: map' для хранения цвета (белый, серый, черный) узлов. Это будет «O (log (n)», поскольку «std :: map» реализовано как дерево RB в большинстве реализаций. – Vikas
@Vikas: Я считаю, что это эквивалентно назначению счетчика каждому узлу. – Ari
каждый узел в BFS проходит через три состояния, не посещенные, посещенные, но не завершенные, завершенные. Я действительно не знаю, что вы имели в виду, назначая счетчики для каждого узла. Но если вы можете добиться поддержания трехсостояний узла, вы может использовать его. – Vikas