MySQL中的深度优先搜索

Question

我正在尝试编写一个MySQL PROCEDURE,它将边缘e和边缘设置eset为输入并输出一个布尔值,iscyclic以确定附加边缘是否产生循环图.除了创建一个包含类似" visit count" 的列的所有顶点的表格,然后检查在运行边缘集时是否多次访问任何顶点时,还有更简单的方法吗？

Answer 1

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

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

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

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

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

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

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

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