MySQL中的广度优先搜索查询？

Question

我想构建一个 mySQL 查询，它从给定节点返回 x 深度图中的所有节点。深度将仅为 2-4。

表结构是（neighborIDs 可以包含多个值）：

Id  Name  Desc  neighborIDs

所以任务基本上是在 mySQL 中进行广度优先搜索。我在 T-SQL 中找到了一种方法，这在 mySQL 中可行吗？单个 SQL 查询是否比编写 PHP 函数更好，该函数在节点的每个邻居上运行一个简单的 SELECT（因此基本上是进行大量简单查询）？

感谢帮助

---

一试：

SELECT  root.ID,
        d1.ID,
        d2.ID
FROM    Locations root
        LEFT JOIN Locations d1 ON
          root.neighborIDs LIKE CONCAT('%',d1.id,'%')
        LEFT JOIN Locations d2 ON
          d1.neighborIDs LIKE CONCAT('%',d2.id,'%')
WHERE root.id = 1  # i guess this defines the starting node for the search..

一个示例表是：

id   name   desc                   neighborIDs  
1    id1    --     
2    id2    ---        
3    id3    neighborours are 1,2   1,2  
4    id4    neighbour is 3         3
10   id10   neigh is 4             4

如果我使用输入 id=1 运行查询，如果 BFS 深入 1 级，它应该返回 id=3 的行。

---

另一个尝试：

SELECT id,neighborIDs
FROM locations
WHERE id = 3
OR
neighborIDs LIKE '%3%'
OR (SELECT neighborIDs FROM locations WHERE id = 3) LIKE CONCAT('%',id,'%')

此查询选择 id = 3 的节点的邻居。

Answer 1

步骤 0：创建一个显示所有邻居对的视图

CREATE VIEW neighbour AS
( SELECT loc1.id AS a
       , loc2.id AS b
  FROM locations loc1
     , locations loc2
  WHERE FIND_IN_SET(loc1.id, loc2.neighbours)>0
     OR FIND_IN_SET(loc2.id, loc1.neighbours)>0
) ;

步骤 1：查找深度为 1 的邻居

SELECT b AS depth1
FROM neighbour
WHERE a = 1;               <-- for root with id=1

步骤 2：查找深度为 2 的邻居

SELECT DISTINCT d2.b AS depth2
FROM neighbour d1
  JOIN neighbour d2
    ON d1.b = d2.a
      AND d2.b != 1
WHERE d1.a = 1                <-- for root with id=1
  AND d2.b NOT IN
     ( SELECT b AS depth1     <- depth1 subquery
       FROM neighbour
       WHERE a = 1            <-- for root with id=1
      )
;

步骤 3：查找深度为 3 的邻居

SELECT d3.b as depth3
FROM neighbour d1
  JOIN neighbour d2
    ON d1.b = d2.a
    AND d2.b != 1
    AND d2.b NOT IN
       ( SELECT b as depth1
         FROM neighbour
         WHERE a = 1
       )
  JOIN neighbour d3
    ON d2.b = d3.a
    AND d3.b != 1
WHERE d1.a = 1
  AND d3.b NOT IN
     ( SELECT b as depth1
       FROM neighbour
       WHERE a = 1
      )
  AND d3.b NOT IN
     ( SELECT d2.b AS depth2
       FROM neighbour d1
         JOIN neighbour d2
           ON d1.b = d2.a
           AND d2.b != 1
       WHERE d1.a = 1
         AND d2.b NOT IN
            ( SELECT b AS depth1
              FROM neighbour
              WHERE a = 1
            )
     )
;

正如你所看到的，查询行数的增长是指数级的，所以我不会尝试级别 4。