使用SQL查找有向图中的循环

Question

已经有一些关于寻找循环的问题，但我没有在SQL（首选MSSQL）中找到解决方案。

表格将是Node（NodeID INT）和Edge（EdgeID INT，NodeID1 INT，NodeID2 INT）

如何高效地在有向图中查找循环?

- devio

Answer 1

这是一个非常好的资源："SQL图算法"，作者是Kendall Willets

- DVK

---

链接不可用。 - Monic

确认@Monic的评论。链接已损坏。 - Jorge E. Hernández

@lalongooo - 已修复。回溯机器是你的好朋友。 - DVK

Answer 2

你不能仅使用 SQL 完成它。在你的查询中，JOIN 的数量总是有限的。无论你将 JOIN 的数量设定为多大，你总是可以构造一个具有更多边缘的循环，从而证明查询不可行。

因此，你应该使用某种类型的循环，可以在某些 SQL 方言中实现，也可以在 Perl 或 Ruby 中实现。

- P Shved

---

SQL-2008规定了“WITH RECURSIVE”，因此现在可以在不使用奇怪方言的情况下实现。当然，首先你需要找到支持新SQL标准的数据库... - ephemient

Answer 3

解决方案其实很简单明了，但是有点长：

首先生成所有通过图的路径列表，以便没有任何一条路径包含相同的边。

从这些信息中，我们提取出起点和终点相同的路径列表。

基于前两步的计算，从这个“最终”边缘列表中重构所有带有循环的路径。

我在我的博客上发布了TSQL完整解决方案。

- devio

---

虽然这理论上回答了问题，但最好在此处包含答案的基本部分，并提供参考链接。 - Dan Oberlam