深度优先搜索在SQLlite

Question

我试图实现SQLite的深度优先搜索： 我有如下表：

CREATE TABLE table1(id INTEGER PRIMARY KEY ,id_parrent INTEGER ,id_child INTEGER); 

INSERT INTO table1(id_parrent,id_child) VALUES('1','4'); 
INSERT INTO table1(id_parrent,id_child) VALUES('1','1'); 
INSERT INTO table1(id_parrent,id_child) VALUES('1','3'); 
INSERT INTO table1(id_parrent,id_child) VALUES('1','2'); 
INSERT INTO table1(id_parrent,id_child) VALUES('2','8'); 
INSERT INTO table1(id_parrent,id_child) VALUES('2','7'); 
INSERT INTO table1(id_parrent,id_child) VALUES('2','3'); 
INSERT INTO table1(id_parrent,id_child) VALUES('2','6'); 
INSERT INTO table1(id_parrent,id_child) VALUES('2','10'); 
INSERT INTO table1(id_parrent,id_child) VALUES('2','5'); 
INSERT INTO table1(id_parrent,id_child) VALUES('2','9'); 
INSERT INTO table1(id_parrent,id_child) VALUES('2','2');  

，我尝试使用以下查询深度优先搜索：

WITH RECURSIVE 
under_parrent(id_child,level) AS (
    VALUES('1','0') 
UNION ALL 
SELECT table1.id_child, under_parrent.level+1 
    FROM table1,under_parrent 
    WHERE table1.id_parrent = under_parrent.id_child 
ORDER BY 2 DESC 
) 
SELECT id_child FROM under_parrent; 

我的问题是，结果被无限循环，如本图片：

Answer 1

你的第二个记录共自己提供1;查询正确报告这个无限循环。

通常情况下，避免重复是通过使用UNION而不是UNION ALL来完成的，但是在这种情况下这不起作用，因为level值不同。 您必须过滤掉WHERE（table1.id_parrent <> table1.id_child）中的那些循环，但如果有较大的循环（例如1→2→1），则这不太可能。