我正在尝试编写一个 MySQL PROCEDURE,它以边 e 和边集 eset 作为输入并输出一个 bool 值 iscyclic。除了创建一个包含诸如“visit count ”之类的列的所有顶点的表,然后检查是否在运行边集时多次访问任何顶点之外,还有其他更直接的方法吗?

最佳答案

正如 Billiska 的评论所表明的那样,您需要跟踪森林中的每棵树,即连接集。

disjoint set data structure 的最简单实现将包含一个临时表,它将每个顶点的 ID 映射到父节点的 ID。您可以沿着这些父链接从一个顶点到下一个顶点,直到最终得到这棵树的根,这是一个指向自身的顶点。这个根作为唯一的代表来标识整个连接集。

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

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

  • 还有其他工具可以保持树的深度较低:
  • 你总是让较深的树成为较不深的树的父级,
    并且您可以执行路径压缩以减少找到的深度
    节点。

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

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

    关于mysql - MySQL中的深度优先搜索,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/13535733/

    10-16 13:13
    查看更多