Как я могу просмотреть связанный список, который может включать не только циклы, но и несколько ссылок с одного узла? (VB6)

Question

У меня есть связанный список, составленный из NODE_.Эти узлы на самом деле не указывают на другие узлы, а скорее на связанный список NODELINK_, который хранит связанные узлы.

Это позволяет формировать неправильные графы, такие как:

N------N---------N-------N
      / \        |        \
     /   \       N---N-----N
    /     \      |    \    |  
   N-------N-----N     N---N            

Вы поняли идею.Очень динамичные данные.Типичный узел может выглядеть так:

NOODE_1 -> NODELINK_1 -> NODELINK_2 -> NODELINK_3 -> NULL
               |             |             |
               V             V             V
             NODE2_        NODE3_        NODE4_

Проблема возникает при обходе такого графа.Обходить график довольно легко, но как я могу убедиться, что не застрял, пересекая цикл внутри графика (ПРИМЕЧАНИЕ: небезопасно предполагать, что голова будет частью этого цикла, поэтому ваштипичный алгоритм «обхода кругового связанного списка» здесь не будет сокращен), и как я могу убедиться, что знаю, когда узел был обработан ранее?

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

Answer 1

Вы делаете обход графика . Установка флага visited для каждого узла, безусловно, является распространенным подходом, например, оба алгоритма поиск в ширину и поиск в глубину алгоритмы в Википедии mark посещенные узлы.

Answer 2

Единственный другой способ, который я могу себе представить, - это сохранить структуру данных, такую ​​как Dictionary, для перечисления тех узлов, которые вы уже посетили, и проверить членство перед посещением узла, который вы уже посетили. Это избавит вас от необходимости создавать дополнительные поля в ваших узлах.