小编典典

识别连接节点堆中的图-这怎么称呼?

algorithm

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

由于Y = 34的值与存储区1中的第一行相同,因此最后一行位于存储区1中。


阅读 202

收藏
2020-07-28

共1个答案

小编典典

它看起来不像图,更像是单纯形。但是,如果我们将此复合体视为其骨架图(数字被视为顶点,并且表中的一行表示所有三个顶点都由一条边连接),那么我们可以使用任何算法来查找该图的连接组件。我不确定在SQL中是否有可行的方法来执行此操作,也许以某种方式使用图形数据库会更加谨慎。

但是,对于这个特定的问题,也许可以通过我没有寻找的SQL来获得一些简单的解决方案。

2020-07-28