如何使用遞歸 CTE 辨識無向圖中的連通子圖？

如何找出無向圖的所有連通子圖

問題：

問題：

給定一個具有兩個欄位（Identifier1 和Identifier2）的表，表示無向圖中的連接節點對，將節點分組為子圖，以便子圖中的每個節點連接到同一子圖中的每個其他節點。

解：

<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>

問題陳述中的原始查詢可以使用遞歸方法將節點分組為連接的子圖來細化。以下是查詢的修改版本，它使用遞歸CTE 來遍歷圖的邊緣並識別連接的組件：

它的工作原理：

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中文網其他相關文章！