识别连接节点堆中的图形 - 这是如何调用的？

我有一个包含三列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

识别连接节点堆中的图形 - 这是如何调用的？

回答

相关问题