Обнаружение цикла с помощью алгоритма триколора по сравнению с использованием набора - есть ли преимущество в использовании одного из них по сравнению с другим?

Question

Существует два, казалось бы, похожих подхода для обнаружения цикла на графике:

1. Обходите график в стиле DFS, предполагая, что все узлы имеют белый цвет, пока вы не посетите их в первый раз, делая их серыми.После того, как вся обработка сделана на узле, вы превращаете его в черный.Если вы когда-нибудь посещаете серый узел, вы знаете, что у вас есть цикл.

2. Обходите график, стиль DFS и сохраните набор S со всеми узлами, которые в настоящее время находятся в вашем стеке DFS (простов целях производительности).Каждый раз, когда вы посещаете узел, вы добавляете его в S, и каждый раз, когда вы завершаете работу с узлом, вы удаляете его из S. Цикл существует, если в любой момент вы пытаетесь посетить узел, который уже находится в S.

Есть ли практическое преимущество в выборе одной из альтернатив над другой?Какой-то компромисс, который я могу пропустить?Или использование одного или другого приводит к точно так же?

Спасибо

Answer 1

Эти два концептуально эквивалентны: набор S содержит в точности серые узлы, а алгоритмы одинаковы в противном случае.

На практике, однако, есть тонкие различия:

• Если набор S является реализацией на основе хеша, то узлы должны быть хэшируемыми.Если хеш-функция плохо спроектирована или данные выбираются по ошибке, производительность может снизиться.
• Если набор S является реализацией на основе дерева, то узлы должны быть сопоставимы.Кроме того, у вас больше нет (амортизированного) поиска по постоянному времени.
• Если используются цвета, то узлы должны иметь поле «цвет», которое не используется для других целей.Тем не менее, это дает самый быстрый «поиск по множеству», так как это всего лишь один поиск / сравнение.
• Если график направлен или отключен, то вам придется выполнять DFS несколько раз (из всех белых узлов).Отслеживание того, был ли посещен узел, требует второго набора, так как первый набор всегда пуст в конце DFS.Поскольку в действительности существует три «состояния» узла, для хранения этой информации требуется 2 набора.

В критических для производительности ситуациях цветной подход будет иметь меньшие постоянные коэффициенты для линейного времени выполнения.Но если добавление поля color к узлам не является вариантом, то использование множеств является хорошей альтернативой.Если узлы в настоящее время реализованы как int s или String s (в отличие от Node класса с возможностью добавления полей), тогда подход на основе набора будет легче кодировать, поскольку вы можете избежать изменения представления узлов.