」工欲善其事,必先利其器。「—孔子《論語.錄靈公》
首頁 > 程式設計 > 我們如何在由兩列「Identifier1」和「Identifier2」所表示的無向圖中將相關識別碼分組,並為它們指派唯一的群組ID?

我們如何在由兩列「Identifier1」和「Identifier2」所表示的無向圖中將相關識別碼分組,並為它們指派唯一的群組ID?

發佈於2024-10-31
瀏覽:124

How do we group related identifiers in an undirected graph represented by two columns, \'Identifier1\' and \'Identifier2\', and assign them unique group IDs?

在無向圖中查找連通子圖

問題:

給定一個由兩列「Identifier1」和「Identifier2」表示的無向圖,我們如何將彼此相關的識別碼進行分組並為它們分配唯一的群組ID?

解決方案:

這個問題可以透過將資料視為圖中的邊並遍歷所有邊來解決遞歸地。

遞歸演算法:

  1. 建立一個包含兩列中所有唯一識別碼的表。
  2. 建立一個包含兩列中所有邊(識別碼對)的表格方向。
  3. 定義一個遞歸查詢,從每個標識符開始遍歷圖形,並建立遍歷標識符的路徑。
  4. 以起始標識符(錨點標識符)將結果分組,以識別連接的元件。
  5. 根據錨點識別碼為每個連接的元件分配唯一的群組 ID。

範例查詢 (SQL):

WITH
CTE_Idents AS (
    SELECT Ident1 AS Ident
    FROM @T

    UNION

    SELECT Ident2 AS Ident
    FROM @T
),
CTE_Pairs AS (
    SELECT Ident1, Ident2
    FROM @T
    WHERE Ident1 <> Ident2

    UNION

    SELECT Ident2 AS Ident1, Ident1 AS Ident2
    FROM @T
    WHERE Ident1 <> Ident2
),
CTE_Recursive AS (
    SELECT
        CAST(CTE_Idents.Ident AS varchar(8000)) AS AnchorIdent 
        , Ident1
        , Ident2
        , CAST(','   Ident1   ','   Ident2   ',' AS varchar(8000)) AS IdentPath
        , 1 AS Lvl
    FROM 
        CTE_Pairs
        INNER JOIN CTE_Idents ON CTE_Idents.Ident = CTE_Pairs.Ident1

    UNION ALL

    SELECT 
        CTE_Recursive.AnchorIdent 
        , CTE_Pairs.Ident1
        , CTE_Pairs.Ident2
        , CAST(CTE_Recursive.IdentPath   CTE_Pairs.Ident2   ',' AS varchar(8000)) AS IdentPath
        , CTE_Recursive.Lvl   1 AS Lvl
    FROM
        CTE_Pairs
        INNER JOIN CTE_Recursive ON CTE_Recursive.Ident2 = CTE_Pairs.Ident1
    WHERE
        CTE_Recursive.IdentPath NOT LIKE CAST('%,'   CTE_Pairs.Ident2   ',%' AS varchar(8000))
),
CTE_RecursionResult AS (
    SELECT AnchorIdent, Ident1, Ident2
    FROM CTE_Recursive
),
CTE_CleanResult AS (
    SELECT AnchorIdent, Ident1 AS Ident
    FROM CTE_RecursionResult

    UNION

    SELECT AnchorIdent, Ident2 AS Ident
    FROM CTE_RecursionResult
)
SELECT
    CTE_Idents.Ident
    ,CASE WHEN CA_Data.XML_Value IS NULL 
    THEN CTE_Idents.Ident ELSE CA_Data.XML_Value END AS GroupMembers
    ,DENSE_RANK() OVER(ORDER BY 
        CASE WHEN CA_Data.XML_Value IS NULL 
        THEN CTE_Idents.Ident ELSE CA_Data.XML_Value END
    ) AS GroupID
FROM
    CTE_Idents
    CROSS APPLY
    (
        SELECT CTE_CleanResult.Ident ','
        FROM CTE_CleanResult
        WHERE CTE_CleanResult.AnchorIdent = CTE_Idents.Ident
        ORDER BY CTE_CleanResult.Ident FOR XML PATH(''), TYPE
    ) AS CA_XML(XML_Value)
    CROSS APPLY
    (
        SELECT CA_XML.XML_Value.value('.', 'NVARCHAR(MAX)')
    ) AS CA_Data(XML_Value)
WHERE
    CTE_Idents.Ident IS NOT NULL
ORDER BY Ident;

重點:

  • 遞歸CTE(公共表表達式)遍歷圖並建立連通分量。
  • 最終的SELECT語句指派群組ID 並以所需格式產生輸出。
  • 此解決方案經過最佳化,可避免冗餘計算並提供高效的結果。
最新教學 更多>
  • 如何使用PHP將斑點(圖像)正確插入MySQL?
    如何使用PHP將斑點(圖像)正確插入MySQL?
    essue VALUES('$this->image_id','file_get_contents($tmp_image)')";This code builds a string in PHP, but the function call fil...
    程式設計 發佈於2025-04-28
  • 在UTF8 MySQL表中正確將Latin1字符轉換為UTF8的方法
    在UTF8 MySQL表中正確將Latin1字符轉換為UTF8的方法
    在UTF8表中將latin1字符轉換為utf8 ,您遇到了一個問題,其中含義的字符(例如,“jáuòiñe”)在utf8 table tabled tablesset中被extect(例如,“致電。為了解決此問題,您正在嘗試使用“ mb_convert_encoding”和“ iconv”轉換受...
    程式設計 發佈於2025-04-28
  • 如何將來自三個MySQL表的數據組合到新表中?
    如何將來自三個MySQL表的數據組合到新表中?
    mysql:從三個表和列的新表創建新表 答案:為了實現這一目標,您可以利用一個3-way Join。 選擇p。 *,d.content作為年齡 來自人為p的人 加入d.person_id = p.id上的d的詳細信息 加入T.Id = d.detail_id的分類法 其中t.taxonomy ...
    程式設計 發佈於2025-04-28
  • 如何使用“ JSON”軟件包解析JSON陣列?
    如何使用“ JSON”軟件包解析JSON陣列?
    parsing JSON與JSON軟件包 QUALDALS:考慮以下go代碼:字符串 } func main(){ datajson:=`[“ 1”,“ 2”,“ 3”]`` arr:= jsontype {} 摘要:= = json.unmarshal([] byte(...
    程式設計 發佈於2025-04-28
  • FastAPI自定義404頁面創建指南
    FastAPI自定義404頁面創建指南
    response = await call_next(request) if response.status_code == 404: return RedirectResponse("https://fastapi.tiangolo.com") else: ...
    程式設計 發佈於2025-04-28
  • 解決Spring Security 4.1及以上版本CORS問題指南
    解決Spring Security 4.1及以上版本CORS問題指南
    彈簧安全性cors filter:故障排除常見問題 在將Spring Security集成到現有項目中時,您可能會遇到與CORS相關的錯誤,如果像“訪問Control-allo-allow-Origin”之類的標頭,則無法設置在響應中。為了解決此問題,您可以實現自定義過濾器,例如代碼段中的MyFi...
    程式設計 發佈於2025-04-28
  • 如何限制動態大小的父元素中元素的滾動範圍?
    如何限制動態大小的父元素中元素的滾動範圍?
    在交互式接口中實現垂直滾動元素的CSS高度限制問題:考慮一個佈局,其中我們具有與用戶垂直滾動一起移動的可滾動地圖div,同時與固定的固定sidebar保持一致。但是,地圖的滾動無限期擴展,超過了視口的高度,阻止用戶訪問頁面頁腳。 $("#map").css({ margin...
    程式設計 發佈於2025-04-28
  • 如何在無序集合中為元組實現通用哈希功能?
    如何在無序集合中為元組實現通用哈希功能?
    在未訂購的集合中的元素要糾正此問題,一種方法是手動為特定元組類型定義哈希函數,例如: template template template 。 struct std :: hash { size_t operator()(std :: tuple const&tuple)const {...
    程式設計 發佈於2025-04-28
  • 如何使用PHP從XML文件中有效地檢索屬性值?
    如何使用PHP從XML文件中有效地檢索屬性值?
    從php $xml = simplexml_load_file($file); foreach ($xml->Var[0]->attributes() as $attributeName => $attributeValue) { echo $attributeName,...
    程式設計 發佈於2025-04-28
  • 左連接為何在右表WHERE子句過濾時像內連接?
    左連接為何在右表WHERE子句過濾時像內連接?
    左JOIN CONUNDRUM:WITCHING小時在數據庫Wizard的領域中變成內在的加入很有趣,當將c.foobar條件放置在上面的Where子句中時,據說左聯接似乎會轉換為內部連接。僅當滿足A.Foo和C.Foobar標準時,才會返回結果。 為什麼要變形?關鍵在於其中的子句。當左聯接的右側...
    程式設計 發佈於2025-04-28
  • 如何在JavaScript對像中動態設置鍵?
    如何在JavaScript對像中動態設置鍵?
    在嘗試為JavaScript對象創建動態鍵時,如何使用此Syntax jsObj['key' i] = 'example' 1;不工作。正確的方法採用方括號: jsobj ['key''i] ='example'1; 在JavaScript中,數組是一...
    程式設計 發佈於2025-04-28
  • 如何在Chrome中居中選擇框文本?
    如何在Chrome中居中選擇框文本?
    選擇框的文本對齊:局部chrome-inly-ly-ly-lyly solument 您可能希望將文本中心集中在選擇框中,以獲取優化的原因或提高可訪問性。但是,在CSS中的選擇元素中手動添加一個文本 - 對屬性可能無法正常工作。 初始嘗試 state)</option> < o...
    程式設計 發佈於2025-04-28
  • Java開發者如何保護數據庫憑證免受反編譯?
    Java開發者如何保護數據庫憑證免受反編譯?
    在java 在單獨的配置文件保護數據庫憑證的最有效方法中存儲憑據是將它們存儲在單獨的配置文件中。該文件可以在運行時加載,從而使登錄數據從編譯的二進製文件中遠離。 使用prevereness class import java.util.prefs.preferences; 公共類示例{ 首選...
    程式設計 發佈於2025-04-28
  • 如何在鼠標單擊時編程選擇DIV中的所有文本?
    如何在鼠標單擊時編程選擇DIV中的所有文本?
    在鼠標上選擇div文本單擊單擊單個鼠標單擊單擊單擊?這允許用戶輕鬆拖放所選的文本或直接複製它。 在單個鼠標上單擊的div元素中選擇文本,您可以使用以下Javascript函數: function selecttext(canduterid){ if(document.Selection)...
    程式設計 發佈於2025-04-28
  • 為什麼使用Firefox後退按鈕時JavaScript執行停止?
    為什麼使用Firefox後退按鈕時JavaScript執行停止?
    導航歷史記錄問題:JavaScript使用Firefox Back Back 此行為是由瀏覽器緩存JavaScript資源引起的。要解決此問題並確保在後續頁面訪問中執行腳本,Firefox用戶應設置一個空功能。 警報'); }; alert('inline Alert')...
    程式設計 發佈於2025-04-27

免責聲明: 提供的所有資源部分來自互聯網,如果有侵犯您的版權或其他權益,請說明詳細緣由並提供版權或權益證明然後發到郵箱:[email protected] 我們會在第一時間內為您處理。

Copyright© 2022 湘ICP备2022001581号-3