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

Question

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

• «А» есть корень (всегда есть ровно один корень)
• каждый узел знает своего родителя (ей)
• имена узла произвольно - ничто не может быть выведен из них
• мы знаем из другого источника, что узлы были добавлены в дерево в порядке А до G (например, они коммиты в системе управления версий)

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

• B и Е представляет собой В
• D и F является B

Примечание:

• Существует не обязательно единственный путь к данный узел из корня (например, «G» имеет два пути), поэтому вы не можете просто traverse paths from root to the two nodes and look for the last equal element
• Я нашел алгоритмы LCA для деревьев, особенно двоичных деревьев, но они здесь не применяются, поскольку узел может иметь несколько родителей (т. Е. Это не дерево)

Answer 1

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

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

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

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

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

Answer 2

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

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

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

Answer 3

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

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

Я нашел THIS TUTORIAL подробно и хорошо. Я также планирую реализовать это.

Answer 4

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

Answer 5

Я предлагаю решение временной сложности 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 |).

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

Answer 6

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

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

Answer 7

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

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

1. цвета всех предки х в синего (может быть сделано с помощью BFS)
2. цвета всех голубых предков у в красного (BFS снова)
3. Для каждого red узел на графике, увеличьте число его родителей count на

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

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

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

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

Answer 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, который отслеживает множество предков множества, где содержится текущий элемент. Это все, в основном