В алгоритме графа, каков наилучший способ определить, посещается ли узел?
Первоначально я делал это двумя способами. Одним из способов является сохранение посещенных узлов в списке и обход списка, чтобы определить, посещался ли ранее узел. Другой использовал логический массив, который отслеживает как посещенные, так и не посещенные узлы. Меня это действительно интересовало, как лучше?
Решение
Один из подходов, который может быть полезен для микрооптимизации (улучшенное поведение кэша, исключает поиск), заключается в сохранении флага для каждого объекта узла. Очевидным недостатком является то, что графовые алгоритмы не являются повторными. Хочу сделать разные График обхода, чтобы принять решение во время обхода? Ну, ты не можешь. Вы также должны помнить, чтобы очистить все эти флаги впоследствии.
Другая категория поддерживает отдельную структуру данных для каждого обхода. Оба подхода, которые вы даете, подпадают под это, хотя подход списка очень неэффективен — O (n) время для каждого поиска. Логический массив (возможно, сжатый в битовый набор; эта опция очень экономия пространства) проста и эффективна как во времени, так и в пространстве, но требует, чтобы узлы имели последовательные индексы / идентификаторы. Это не всегда дано, и имеет последствия для других частей обработки графа.
Если у вас этого нет, и вместо этого вы ссылаетесь на графические объекты с указателями, вы можете использовать отображение, основанное на этом. В языках более высокого уровня, таких как Python, это очень просто (и из-за хорошо настроенных структур данных хеш-таблиц / наборов, также довольно эффективно).
Очевидное преимущество состоит в том, что обходы графа являются повторными. Хотя это может показаться не таким уж большим, я могу засвидетельствовать, что ситуации, когда это полезно, иногда возникают.
Другие решения
Зависит от вашего использования,
Для лучшей производительности времени вы можете использовать хеш-карты
Вы также можете использовать b-дерево для хранения вставки и поиска узлов O (logn)
Лично я бы использовал хэш-карту, основанную на уникальном значении для каждого узла. Вы можете контролировать размер хеш-карты в соответствии с вашими потребностями, а с хорошей функцией хеширования можно контролировать коллизии. Посмотрите на этот код для примера https://github.com/himanshujindal/Reconstructing-Books-from-Google-Ngrams