Применение решения для LCA в DAG на циклических графах?
Ответ на Мой вопрос может быть очевидным, и я знаю этот очевидный ответ на бумаге. Я имею в виду, что когда дело доходит до некоторых примеров, я понимаю, почему нам не разрешено иметь циклы для запуска алгоритма Lowest Common Ancestor, но у меня возникают проблемы с пониманием статей, написанных для решения LCA в DAG. и так, какая часть решения мешает нам использовать его на циклических графах..
что я хочу знать и буду благодарен за информацию:
- Можете ли вы объяснить одно из решений проблемы LCA в группах доступности баз данных, не слишком много формулировок?
- Вы можете определить, на каком шаге возникают проблемы с цилиндрами и почему?
в моей задаче пары узлов, чтобы найти их LCA, не находятся внутри одного цикла, поэтому я думаю, что может быть способ решить эту проблему..
заранее спасибо
1 ответ
Проблема с циклами начинается с самого определения.
ДМС u а также v определяется как набор таких узлов z тот z доступен от u а также v а также z недоступен из любого другого узла z' такой, что z' доступен от u а также v,
Может не существовать в циклическом графе. Например, если есть цикл 1->2->3 и два других узла и ребра: 4->3 а также 5->3нет LCA для 4 а также 5 (это все 1, 2 а также 3 достижимы от них обоих, но они также достижимы друг от друга).
Вы можете найти все узлы, которые доступны из u а также v (используя dfs или что-то еще), а затем проверяем, есть ли такой узел z это достижимо от них обоих, но не от любого другого узла, который удовлетворяет этому условию (это будет работать за полиномиальное время).
Так что речь идет скорее о значимом определении наименьшего общего предка, чем о возможности его вычисления (как я показал выше, вы можете вычислить что-то подобное, но это может не иметь смысла даже для двух узлов, которые не находятся на одном и том же цикл).