我正在尝试编写一个 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/