我想构建一个 mySQL 查询,它从给定节点的 x 深度返回图中的所有节点。深度将只有 2-4。
表结构为(neighborIDs可以包含多个值):
Id Name Desc neighborIDs
因此,该任务基本上是 mySQL 中的广度优先搜索。我找到了 way to do it in 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 的节点的邻居。
最佳答案
第 0 步:创建显示所有邻居对的 View
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。
关于mysql - MySQL中的广度优先搜索查询?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5357211/