使用perl进行递归查询

Question

我在 db 上有下表，其中有 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 中，队列和堆栈自然由数组表示）

• < p>将原始节点存储到队列中。

• 当队列不为空时，重复：

  • 将第一个节点 N 从队列中弹出。

  • 将该节点标记为“已遍历”。最简单的方法是将 %seen 哈希中键为 N 的哈希元素设置为值 1。

  • 将 N 打印到路径

  • 从 N 个连接的 DB 中查找所有节点。

  • 将上一步中尚未看到的节点添加到队列末尾。

• 结束循环。

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);