再帰的 CTE を使用して無向グラフ内の接続されたサブグラフを識別する方法

無向グラフの接続されたすべてのサブグラフを見つける方法

問題:

与えられた無向グラフ内の接続されたノードのペアを表す 2 つの列 (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>

仕組み:

CTE という名前の CTE (共通テーブル式) は、入力テーブル @T からすべての行を選択することから始まる再帰クエリとして機能します。次に、それ自体の再帰結合が実行され、UNION ALL 句によってグラフのエッジを表す行が CTE に追加されます。具体的には、t1.Ident2 が t2.Ident1 に等しいという条件で CTE と入力テーブル @T を結合し、各ノードからグラフのエッジを効果的に横断します。

接続されたサブグラフを識別するには、クエリ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 で接続された 1 つのサブグラフを形成し、ノード "b"、"d"、"f"、および "j" は GroupID=2 で別のサブグラフを形成します。ノード "e" と "k" は GroupID=3 の別のサブグラフにあり、ノード "i" は GroupID=4 の独自のサブグラフにあります (他のノードとの接続がないため)。

以上が再帰的 CTE を使用して無向グラフ内の接続されたサブグラフを識別する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。