Как найти круговые ссылки в дереве

Question

У меня есть древовидная структура, очень похожая на DOM.
Мне нужно отладить его и очистить от круговых ссылок (дочерний элемент является родителем родителя).
Я помню, что есть алгоритм для этого, не могу запомнить имя.
Какое имя.

Answer 1

Прогулка по дереву с использованием любого удобного алгоритма; поиск по глубине обычно является хорошим кандидатом. Следите за каждым узлом, который вы посещаете. Если вы дважды посещаете узел, у вас есть потенциальная округлость, которую вы могли бы разбить на эту конкретную округлость, удалив ссылку, которая приведет к пересмотренному узлу. Но это может быть просто объединение, что делает дерево ориентированным ациклическим графом (DAG). (См. Диаграмму ниже.)

Если вы в порядке с DAG, но не с округлостью, тогда вам нужно различать два случая. Самый простой способ - поддерживать два флага для каждого узла вместо одного: visited и completed. В DFS вы отмечаете узел как посещенный перед посещением детей и завершаетесь после посещения детей. (Если это лист, просто дать ему обе метки.) Теперь, есть три возможности при первом посещении узла:

1. Нет меток. Не беспокойся.

2. посетили, но не завершена: округлость

3. посетили и закончил: ациклический алмаз

Последний случай выглядит примерно так:

  root 
      /\ 
     / \ 
     / \ 
      a  b 
     /\ /\ 
     / \/ \ 
    / \/  \ 
     c  join  d