Алгоритм поиска минимального общего предка в ориентированном ациклическом графе?

Представьте ориентированный ациклический граф следующим образом:

"A" - это корень (всегда есть ровно один корень)
каждый node знает своего родителя (ов)
имена node произвольны - из них ничего нельзя сделать
мы знаем из другого источника, что узлы были добавлены в дерево в порядке от A до G (например, они совершают ошибку в системе управления версиями)

Какой алгоритм я могу использовать для определения самого низкого общего предка (LCA) двух произвольных узлов, например, общего предка:

B и E - B
D и F - B

Примечание:

Существует не обязательно один путь к данному node из корня (например, "G" имеет два пути), поэтому вы не можете просто пересечь пути от корня к двум узлам и искать последний равный элемент
Я нашел алгоритмы LCA для деревьев, особенно для двоичных деревьев, но они здесь не применяются, потому что node может иметь несколько родителей (т.е. это не дерево).

Ответ 1

Ссылка Den Roman кажется многообещающей, но мне это показалось немного сложнее, поэтому я попробовал другой подход. Вот простой алгоритм, который я использовал:

Предположим, вы хотите вычислить LCA (x, y) с x и y двумя узлами. Каждый node должен иметь значение color и count, соответственно. инициализируется до белого и 0.

Цвет всех предков x как синий (можно сделать с помощью BFS)
Цвет всех синих предков y как красный (снова BFS)
Для каждого красного node на графике увеличивайте число своих родителей count на один

Каждый красный node, имеющий значение count, установленное в 0, является решением.

В зависимости от вашего графика может быть несколько решений. Например, рассмотрим этот график:

LCA (4,5) Возможные решения: 1 и 2.

Обратите внимание, что все еще работает, если вы хотите найти LCA из 3 узлов или более, вам просто нужно добавить другой цвет для каждого из них.

Ответ 2

Я искал решение той же проблемы, и я нашел решение в следующей статье:

http://dx.doi.org/10.1016/j.ipl.2010.02.014

Короче говоря, вы не ищете самого низкого общего предка, но для самого низкого ОДНОГО общего предка, который они определяют в этой статье.

Ответ 3

Просто какое-то дикое мышление. Что касается использования обоих входных узлов в качестве корней и одновременного выполнения двух BFS шаг за шагом. На определенном этапе, когда в своих наборах BLACK перекрываются перекрытия (запись посещенных узлов), алгоритм останавливается, а перекрывающиеся узлы являются их LCA (s). Таким образом, любые другие общие предки будут иметь большие расстояния, чем то, что мы обнаружили.

Ответ 4

Если график имеет циклы, то "предок" определяется слабо. Возможно, вы имеете в виду предка на выходе дерева из DFS или BFS? Или, возможно, "предком" вы имеете в виду node в орграфе, который минимизирует количество переходов от E и B?

Если вас не беспокоит сложность, вы можете вычислить A * (или кратчайший путь Dijkstra) от каждого node до E и B. Для узлов, которые могут достигать как E, так и B, вы можете найти node, который минимизирует PathLengthToE + PathLengthToB.

EDIT: Теперь, когда вы прояснили некоторые вещи, я думаю, что понимаю, что вы ищете.

Если вы можете только "догнать" дерево, я предлагаю вам выполнить BFS из E, а также BFS из B. Каждый node в вашем графе будет иметь две переменные, связанные с ним: переходы из B и переходы из E. Пусть оба B и E имеют копии списка узлов графа. B список сортируется по хпс от B, а список E сортируется по хпс от E.

Для каждого элемента в списке B попытайтесь найти его в списке E. Поместите матчи в третий список, отсортированные по хмелям от B + hops от E. После того, как вы исчерпали список B, ваш третий отсортированный список должен содержать LCA. Это позволяет использовать одно решение, множество решений (произвольно выбранных по их порядку BFS для B) или без решения.

Ответ 5

Мне также нужна точно такая же вещь, чтобы найти LCA в DAG (направленный ациклический граф). Проблема LCA связана с RMQ (проблема минимального запроса диапазона).

Можно уменьшить LCA до RMQ и найти желаемую LCA двух произвольных node из направленного ациклического графа.

Я нашел ЭТОТ учебник подробно и хорошо. Я также планирую реализовать это.

Ответ 6

Я предлагаю решение временной сложности O (| V | + | E |), и я думаю, что этот подход правильный, иначе, пожалуйста, поправьте меня.

При заданном ациклическом графе нам нужно найти LCA двух вершин v и w.

Шаг1: найдите кратчайшее расстояние от всех вершин из корневой вершины, используя bfs http://en.wikipedia.org/wiki/Breadth-first_search со сложностью времени O (| V | + | E |), а также найти родительский элемент для каждой вершины.

Шаг 2. Найдите общих предков обеих вершин, используя родительский элемент, пока мы не достигнем корневой вершины. Сложность времени - 2 | v |

Шаг 3: LCA будет общим предком, имеющим максимальное кратчайшее расстояние.

Итак, это алгоритм временной сложности O (| V | + | E |).

Пожалуйста, исправьте меня, если я ошибаюсь или любые другие предложения приветствуются.

Ответ 7

http://www.gghh.name/dibtp/2014/02/25/how-does-mercurial-select-the-greatest-common-ancestor.html

В этой ссылке описано, как это делается в Mercurial - основная идея состоит в том, чтобы найти всех родителей для указанных узлов, группировать их на расстоянии от корня, а затем выполнять поиск в этих группах.

Ответ 8

Все. Попробуйте, пожалуйста, на Java.

static String recentCommonAncestor(String[] commitHashes, String[][] ancestors, String strID, String strID1)
{
    HashSet<String> setOfAncestorsLower = new HashSet<String>();
    HashSet<String> setOfAncestorsUpper = new HashSet<String>();
    String[] arrPair= {strID, strID1};
    Arrays.sort(arrPair);
    Comparator<String> comp = new Comparator<String>(){
        @Override
        public int compare(String s1, String s2) {
           return s2.compareTo(s1);
        }};
    int indexUpper = Arrays.binarySearch(commitHashes, arrPair[0], comp);
    int indexLower = Arrays.binarySearch(commitHashes, arrPair[1], comp);
    setOfAncestorsLower.addAll(Arrays.asList(ancestors[indexLower]));
    setOfAncestorsUpper.addAll(Arrays.asList(ancestors[indexUpper]));
    HashSet<String>[] sets = new HashSet[] {setOfAncestorsLower, setOfAncestorsUpper};
    for (int i = indexLower + 1; i < commitHashes.length; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            if (sets[j].contains(commitHashes[i]))
            {
                if (i > indexUpper)
                    if(sets[1 - j].contains(commitHashes[i]))
                        return commitHashes[i];
                sets[j].addAll(Arrays.asList(ancestors[i]));
            }
        }
    }
    return null;
}

Идея очень проста. Мы предполагаем, что commitHashes упорядочивается в последовательности понижения. Мы находим самые низкие и верхние индексы строк (хеши - это не значит). Очевидно, что (учитывая порядок потомков) общий предок может быть только после верхнего индекса (меньшее значение среди хешей). Затем мы начинаем перечислять хеши фиксации и строить цепочку дочерних родительских цепей. Для этого у нас есть два хэшета, которые инициализируются родителями самого низкого и верхнего хэша фиксации. setOfAncestorsLower, setOfAncestorsUpper. Если следующий хэш-коммит принадлежит любой из цепей (хешсет) то если текущий индекс является верхним, чем индекс нижнего хэша, то, если он содержится в другом наборе (цепочке), мы возвращаем текущий хеш в качестве результата. Если нет, мы добавляем его родителям (предкам [i]) в hashset, который отслеживает множество предков множества, где содержится текущий элемент. Это все, в основном