Bagaimana Mengenalpasti Subgraf Bersambung dalam Graf Tidak Berarah Menggunakan CTE Rekursif?

Cara Mencari Semua Subgraf Bersambung bagi Graf Tidak Berarah

Masalah:

Diberikan jadual dengan dua lajur (Pengecam1 dan Pengecam2) yang mewakili pasangan nod bersambung dalam graf tidak berarah, kumpulkan nod ke dalam subgraf supaya setiap nod dalam subgraf disambungkan kepada setiap nod lain dalam subgraf yang sama.

Penyelesaian:

Pertanyaan asal daripada pernyataan masalah boleh diperhalusi menggunakan pendekatan rekursif untuk mengumpulkan nod ke dalam subgraf yang disambungkan. Di bawah ialah versi pertanyaan yang diubah suai yang menggunakan CTE rekursif untuk melintasi tepi graf dan mengenal pasti komponen yang disambungkan:

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

Cara ia Berfungsi:

The CTE (Ungkapan Jadual Biasa) bernama CTE bertindak sebagai pertanyaan rekursif yang bermula dengan memilih semua baris daripada jadual input @T. Kemudian, ia melakukan kesatuan rekursif dirinya sendiri, di mana klausa UNION ALL menambah baris pada CTE yang mewakili tepi graf. Khususnya, ia bergabung dengan CTE dengan jadual input @T dengan syarat t1.Ident2 adalah sama dengan t2.Ident1, dengan berkesan merentasi tepi graf dari setiap nod.

Untuk mengenal pasti subgraf yang disambungkan, pertanyaan memanfaatkan lajur GroupPath dalam CTE. Lajur ini dikira sebagai laluan terkumpul Pengecam yang ditemui semasa traversal rekursif. Dengan membahagikan CTE oleh GroupPath dan memilih nilai Ident minimum dalam setiap partition menggunakan MIN(CTE.Ident) OVER (PARTITION BY CTE.GroupPath), ia mengumpulkan nod ke dalam subgraf yang disambungkan.

Contoh :

Pertimbangkan jadual input berikut:

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

Menjalankan pertanyaan yang diubah suai akan menghasilkan hasil berikut:

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

Dalam contoh ini, nod " a", "c", "g", dan "h" membentuk satu subgraf bersambung dengan GroupID=1, manakala nod "b", "d", "f", dan "j" membentuk subgraf lain dengan GroupID=2. Nod "e" dan "k" berada dalam subgraf berasingan dengan GroupID=3 dan nod "i" berada dalam subgraf sendiri dengan GroupID=4 (kerana ia tidak mempunyai sambungan ke nod lain).

Atas ialah kandungan terperinci Bagaimana Mengenalpasti Subgraf Bersambung dalam Graf Tidak Berarah Menggunakan CTE Rekursif?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!