Нахождение лучшего общего предка двух листовых узлов, где узлы имеют ноль, одного или двух родителей - PullRequest
Новая
       19

Нахождение лучшего общего предка двух листовых узлов, где узлы имеют ноль, одного или двух родителей

2 голосов
/ 25 мая 2011

Гол :

Я ищу алгоритм, чтобы найти лучшего общего предка графа, в котором узлы графа могут иметь ноль, одного или двух родителей. Я не уверен в терминологии «лучший общий предок»: лучшей терминологией может быть «самый низкий общий предок» или «недавний общий предок» и т. Д. Если есть лучшая терминология, тогда, пожалуйста, предоставьте URL-адреса, которые описывают это.

Алгоритм имеет доступ к полной структуре данных графа.

У данного узла может быть ноль, один или два родителя. Это является ключевым, потому что алгоритмы, которые я видел в сети, предполагают, что у данного узла есть либо ноль, либо один родитель, но не два родителя (см. Ссылки ниже). Например, узел m1 на диаграмме ниже имеет нулевых родителей, поскольку он является корнем (может быть несколько корней графиков). У d3 двое родителей, один из них d2, а другой b2.

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

Узлы, расположенные ближе к двум входным узлам, предпочтительнее, чем узлы, расположенные дальше (то есть ближе к корням графа).

В качестве примера, один возможный график показан диаграммой, приведенной ниже. В этом сценарии входные данные для алгоритма будут узлами b5 и d4. Лучший общий предок узлов b5 и d4 - это b2. c2 не будет, потому что b3 находится в линии, ведущей к b5.

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

Справочный материал

Алгоритм автономных наименьших предков Тарьяна , по-видимому, подразумевает ноль или одного родителя, поэтому, если это решение, тогда ответ должен включать описание того, как два родителя учитываются в этом алгоритме. Страница википедии для Самый низкий общий предок , кажется, также учитывает только структуры данных, у узлов которых есть ноль или один родительский элемент, а не два:

В древовидной структуре данных, где каждый узел указывает на своего родителя, ...

Диаграмма

graph diagram

1 Ответ

1 голос
/ 25 мая 2011

Я запустил сайт по генеалогии, и раньше я решил эту проблему с помощью следующего алгоритма:

Для обоих узлов используйте рекурсию для создания массива, который связывает имя узла с генерацией.Используя ваш пример, b4 на 1 поколение выше b5;б3 - 2 поколения;etc: 

$b5Tree = array('b4'=>1, 'b3'=>2, 'c3'=>2, 'b2'=>3, 'c2'=>3, ...);
$d4Tree = array('d3'=>1, 'b2'=>2, 'd2'=>2, 'b1'=>3, 'd1'=>3, ...);

Базовый случай - проверить, появляется ли первый узел в дереве второго, и наоборот.Если он существует, то у вас есть ответ.

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

$minNodeID = null;
foreach ($b5Tree as $nID => $gen)
{
    if (($d4Tree[$nID] != 0) and (($d4Tree[$nID]  + $gen) < $minSummedGen))
    {
        $minSummedGen = $d4Tree[$nID] + $gen;
        $minNodeID = $nID;
    }
}
return $minNodeID;
...