如何使用递归 CTE 识别无向图中的连通子图？

如何查找无向图的所有连通子图

问题：

给定一个具有两列（Identifier1 和 Identifier2）的表，表示无向图中的连接节点对，将节点分组为子图，以便子图中的每个节点都连接到同一子图中的每个其他节点。

解决方案：

问题陈述中的原始查询可以使用递归方法将节点分组为连接的子图来细化。下面是查询的修改版本，它使用递归 CTE 来遍历图的边缘并识别连接的组件：

<code class="sql">WITH RECURSIVE CTE AS (
    SELECT * FROM @T
    UNION ALL
    SELECT t2.Ident1, t2.Ident2 
    FROM CTE t1
    JOIN @T t2 ON t1.Ident2 = t2.Ident1
)
SELECT CTE.Ident, GroupID = MIN(CTE.Ident) OVER (PARTITION BY CTE.GroupPath)
FROM CTE
ORDER BY CTE.Ident</code>

它的工作原理：

The名为 CTE 的 CTE（通用表表达式）充当递归查询，首先从输入表 @T 中选择所有行。然后，它执行自身的递归联合，其中 UNION ALL 子句将表示图边缘的行添加到 CTE。具体来说，它将 CTE 与输入表 @T 连接，条件是 t1.Ident2 等于 t2.Ident1，有效地从每个节点遍历图的边。

为了识别连接的子图，查询利用 CTE 中的 GroupPath 列。该列被计算为递归遍历期间遇到的标识符的累积路径。通过按 GroupPath 对 CTE 进行分区，并使用 MIN(CTE.Ident) OVER (PARTITION BY CTE.GroupPath) 选择每个分区内的最小 Ident 值，它将节点分组为连接的子图。

示例:

考虑以下输入表：

Identifier1	Identifier2
a	c
b	f
a	g
c	h
b	j
d	f
e	k
i	NULL
c	b

运行修改后的查询将产生以下结果：

Identifier	GroupID
a	1
b	2
c	1
d	2
e	3
f	2
g	1
h	1
j	2
k	3
l	4

在此示例中，节点 " a”、“c”、“g”和“h”形成一个GroupID=1的连通子图，而节点“b”、“d”、“f”和“j”形成另一个GroupID=2的子图。节点“e”和“k”位于 GroupID=3 的单独子图中，节点“i”位于其自己的 GroupID=4 的子图中（因为它与其他节点没有连接）。

以上是如何使用递归 CTE 识别无向图中的连通子图？的详细内容。更多信息请关注PHP中文网其他相关文章！