mysql - MySQL中的深度优先搜索

Question

我正在尝试编写一个 MySQL PROCEDURE，它将一条边e和一条边集eset作为输入并输出一个布尔值iscyclic以确定附加边是否会导致循环图。除了创建一个包含所有顶点的表之外，还有什么更直接的方法可以做到这一点，其中包含类似“ visit count”的列，然后检查是否在运行边集时多次访问了任何顶点？

Answer 1

正如 Billiska 的评论所表明的，您需要跟踪您的森林中的各个树，即连接集。

不相交集数据结构的最简单实现将由一个临时表组成，该表将ID每个顶点的 映射到ID父节点的 。您可以从一个顶点跟随这些父链接到下一个顶点，直到您最终得到这棵树的根，它是一个指向自身的顶点。该根用作标识整个连接集的唯一代表。

因此，要检查两个集合是否已经连接，您可以计算它们的根并简单地比较它们。

• 最初每个顶点都是它自己的父节点。
• 连接两个节点是通过计算它们的根并使它们中的一个成为另一个的父节点来建模的。

还有其他工具可以保持树的深度较低：

• 您总是让较深的树成为较不深的树的父级，并且您可以执行路径压缩以减少找到的节点的深度。

所有这些也可以在 MySQL 中建模，但性能行为可能与内存中的实现不同。

所以我建议推迟它，直到你真正知道你需要更高的性能，并且有一些数据来测试和比较不同的实现。