識別連接節點堆中的圖形 - 這是如何調用的？

我有一個包含三列X，Y，Z的SQL表。我需要將它按組的方式拆分，使得具有相同X或Y或Z值的所有記錄都被分配到同一組。我需要確保具有相同值X或Y或Z的記錄不會跨多個組分割。識別連接節點堆中的圖形 - 這是如何調用的？

如果您將記錄視爲X，Y，Z的邊緣節點和值，則此問題與查找所有圖形相同，即每個圖形中的節點將通過X，Y或Z直接或間接連接 - 邊界，但每個圖形都沒有與其他圖形共有的邊緣（否則它將成爲同一圖形的一部分）。

幾年前，我知道這被稱爲什麼，甚至還記得算法，但現在它逃脫了我。請告訴我如何調用這個問題，以便我可以解決Google的問題。如果你現在是一個很好的算法 - 請告訴我。如果你有一個SQL實現 - 我會娶你:)

例子：

X     Y    Z   BUCKET 
---------  ----------------  ---------  ----------- 
    1     34    56    1 
    54     43    45    2 
    1     12    22    1 
    2     34    11    1

的最後一行是在水桶1，因爲Y = 34的值相同第一的行，這是鬥1

來源

2010-09-10 zvolkov

你在說[GROUP BY']（http://www.w3schools.com/sql/sql_groupby.asp）子句嗎？ – Oded 2010-09-10 20:58:57

@Oded我不知道如何處理你的評論，無論是作爲玩笑還是冒犯，但考慮到你的48k代表我會把它當作笑話。爲那些喜歡千言萬語的人添加了一個例子。 – zvolkov 2010-09-10 21:04:35

沒有冒犯的意思 - 不同的用戶對不同的技術有不同的知識水平。除非問題證明它，否則我不會假設知識。我認爲你的SQL不是很好......我也發現這個問題很難理解，並且有些模糊，因此我的評論。 – Oded 2010-09-10 21:08:13

它看起來不像一個圖，更像是一個simplicial complex。但是，如果我們將這個複合體作爲其骨架圖（數字被視爲頂點並且表中的一行表示所有三個頂點都被邊連接），那麼我們可以使用任何算法來查找該圖的connected components 。雖然我不確定在SQL中是否有可行的方法來實現這一點，但也許會以某種方式使用graph database更爲謹慎。

但是，對於這個特定的問題，可能有一些簡單的解決方案可以通過我沒有找到的SQL來實現。

來源

2010-09-10 21:20:32 viaclectic

連接組件是關鍵字！謝謝！ – zvolkov 2010-09-10 22:59:37

找到多少個節點，各組X：

select x, count(x) 
from mytable 
group by x

還是找套X名單：

select distinct x from mytable;

來源

2010-09-10 21:07:15 Randy

X的所有值都不代表完整的組。該組還包括Y的所有值，它們與具有相同X值的記錄中Y的任何值相匹配。依此類推，對於所有其他X，Y和Z值。 – zvolkov 2010-09-10 21:10:19

爲什麼最初GROUP BY其中一個colums（如X），製作桶，然後爲Y和Z這樣做，每次合併前一步中的所有桶時，如果發現新組。

重複X，Y和Z的過程，直到桶停止變化。

你在爲鏈接或Facebook工作嗎？ :)

來源

2010-09-10 21:25:02

識別連接節點堆中的圖形 - 這是如何調用的？

回答

相關問題