#c #data-structures #graph
#c #структуры данных #График
Вопрос:
При попытке выполнить DFS, какая структура данных является наилучшей для хранения списка всех уже посещенных узлов? Если каждый узел имеет уникальный идентификатор, одним из способов было бы поддерживать хэш этих уникальных идентификаторов. Если у них нет уникального идентификатора, является ли хеширование узлов жизнеспособным?
Комментарии:
1. Почему вы не можете просто привести указатель к
size_t?2. Разве указатель сам по себе не является уникальным идентификатором (при сериализации сохраняются данные и их исходный адрес). Таким образом, при десериализации вам просто нужно сопоставить указатель с новой ячейкой памяти.
Ответ №1:
Вместо того, чтобы помещать все посещенные вами узлы в хэш-таблицу, поместите их в стек. Если вы помещаете посещенные узлы в стек, вы значительно упрощаете обратный поиск и следуете другим ветвям поиска.
Ответ №2:
Давайте подумаем о причинах, по которым адреса не были бы уникальным идентификатором…
-
Если вы когда-либо копируете узлы, то они получат новый адрес.
-
Если вы когда-нибудь освободите узлы и выделите новые, то вновь выделенные узлы могут повторно использовать какой-либо предыдущий адрес.
Если вы можете удовлетворительно сказать, что вышесказанное не применимо (я предполагаю, что они этого не сделают), тогда, конечно, продолжайте.