找到覆盖有向图的子图的任何生成树

Question

我们有一个业务用例，基本上可以归结为以下 CS 问题：

给定一个有向图

F

和顶点/子图

G

的子集=

v1

，

v2

，...，

vk

，我们想要找到跨越的任何

树

T

 G

（即所有

v1

、

v2

、...、

vk

都是

T

的顶点）及其根。

举个例子，如下图

F

，

G

= {

plan_description

,

person_id (+ temporal condition on effective_date | submission_date}

,

benefit_code

},

算法应该输出看起来像这样的树

并返回

person_id (+ temporal condition on effective_date | submission_date}

作为根。

就上下文而言，我们正在考虑在数据湖上构建一种可视化查询语言，允许用户根据其他列的条件（例如

plan_id

=

benefit_code

）请求接收器列（例如

MED

）。我们想要识别该生成树的根，以便确定需要生成的 SQL 的连接顺序。在此示例中，该连接顺序为：

1. 从橙色表到红色表进行连接。
2. 从 ^ 到绿色表进行连接。

或

1. 从橙色表到绿色表进行连接
2. 从 ^ 到红色表进行连接

这个抽象是否符合经过充分研究的问题原型？

Answer 1

这会稍微绕点弯路。

在 将循环有向图转换为非循环有向图 (DAG) 中，我展示了如何通过进行拓扑排序将循环图转换为非循环图，并在每个点贪婪地删除尽可能少的边。即使在相当大的图上，该算法也非常有效。

但是因为我贪婪地删除了尽可能少的边，所以如果原始图是连通的，那么生成的非循环图也是连通的。更好的是，非循环图到达拓扑排序 - 因此根被识别。

现在无环图不是树。但是您可以通过删除除一个传入边以外的所有边来将其变成一棵树。由于您尝试在数据湖上进行查询，因此我建议您尝试使用连接的基数估计进行修剪，而不是仅考虑图形结构。但您可以尝试一下，找出最有效的方法。

很抱歉这几天没有注意到这个问题。希望迟到的答案对您仍然有用。