рекурсивный запрос с Perl

Question

У меня есть следующая таблица на БД, которая имеет 2 столбца:

from      to    
00001     00002
00001     00003
00002     00003
00002     00004
00003     00001
00003     00004
00002     00004
00004     00002
00005     00003
00005     00001
00006     00007
00009     00006

Мне нужно получить с помощью perl и dbi соединение определенного числа, например, выход 00001 будет следующим соединением:

00001 00002 0003 00004 00005

потому что 00001 подключен к 00002 и 00003, 00002 и 00003 подключен к этим новым номерам 00004 и 00005.

Есть ли алгоритм для реализации этого и что является лучшим решением в perlреализовать такой алгоритм?

Answer 1

Кажется, что вы хотите найти подключенное поддерево (это ориентированный граф, например, дерево, поэтому вам нужны древовидные алгоритмы).

Это делается с помощью алгоритмов поиска по дереву - DFS (Поиск в глубину вначале) или BFS (Поиск в выдохе).Вы можете реализовать один из них в SQL или в Perl (или в смеси DBI, хотя это более раздражает, чем чистый SQL или чистое решение Perl).

Общая BFS будет:

• Создание очереди (Подсказка: в Perl очереди и стеки естественным образом представлены массивами)

• Сохранение исходного узла в очереди.

• Пока очередь не пуста, повторите:

  • Извлеките первый узел N из очереди.

  • Отметьте этот узелкак "пройденный".Самый простой подход - установить хеш-элемент в хеш-коде %seen с ключом N равным 1.

  • Печать N по пути

  • Найти все узлы из подключенной БД из N.

  • Добавить те узлы из последнего шага, которые еще не были видныдо конца очереди.

• Конец цикла.

Answer 2

Один из возможных подходов:

sub AllReachable {
    my ( $dbi, $sql, @todo ) = @_;
    my %done;
    while (@todo) {
        my $res = $dbi->selectcol_arrayref( sprintf $sql, join( ",", @todo ) );
        @done{@todo} = ();
        @todo = grep {!exists $done{$_}} @$res;
    }
    return keys %done;
}

my @result = AllReachable($dbi, 'SELECT DISTINCT to FROM table WHERE from IN (%s)', 1);