当前位置：首页 > news >正文

在duckdb 递归CTE中实现深度优先搜索DFS

news 2026/3/26 21:55:37

原帖地址 https://github.com/duckdb/duckdb/discussions/15386

通常的递归CTE都是广度优先搜索（BFS）

WITHRECURSIVE edges(a,b)as(VALUES(1,2),(1,3),(2,4),(4,5),(4,6)),bfs(node,path)AS(SELECT1ASnode,[]:: STRUCT("from"INT,"to"INT)[]ASpath-- Start with node 1 (root)UNIONALLSELECTe.b,bft.path||[{'from': bft.node,'to': e.b}]FROMbfsASbft,edgesASeWHEREbft.node=e.a)SELECT*FROMbfs;┌───────┬────────────────────────────────────────────────────────────────────┐ │ node │ path │ │ int32 │ struct("from"integer,"to"integer)[]│ ├───────┼────────────────────────────────────────────────────────────────────┤ │1│[]│ │2│[{'from':1,'to':2}]│ │3│[{'from':1,'to':3}]│ │4│[{'from':1,'to':2},{'from':2,'to':4}]│ │5│[{'from':1,'to':2},{'from':2,'to':4},{'from':4,'to':5}]│ │6│[{'from':1,'to':2},{'from':2,'to':4},{'from':4,'to':6}]│ └───────┴────────────────────────────────────────────────────────────────────┘

DuckDB CTE模块的设计者kryonix提供了如下技巧提供DFS，但是还有问题，没有求出全部路径。

WITHRECURSIVE edges(a,b)as(VALUES(1,2),(1,3),(2,4),(4,5),(4,6)),dfs(stack,path)AS(SELECT[1]ASstack,[]:: STRUCT("from"INT,"to"INT)[]ASpath-- Start with node 1 (root)UNIONALL(WITHsiblingsAS(SELECTARRAY_AGG(e.bORDERBYe.bASC)ASsiblings-- ^^^-- This determines the order of traversal of the siblingsFROMdfsASdft,edgesASeWHEREdft.stack[1]=e.a)SELECTx.*FROMsiblingsAS_(s),LATERAL(SELECTs||dft.stack[2:]ASstack,-- Push the stackdft.path||[{'from': dft.stack[1],'to': s[1]}]ASpath-- Add the edge to the pathFROMdfsASdftWHEREarray_length(s)>0-- There are more siblings to traverseUNIONALLSELECTdft.stack[2:],-- Pop the stack[]:: STRUCT("from"INT,"to"INT)[]ASpath-- Reset the pathFROMdfsASdftWHEREarray_length(s)ISNULLANDdft.stack<>[]-- No more siblings to traverse)ASx))SELECT*FROMdfs;┌───────────┬────────────────────────────────────────────────────────────────────┐ │ stack │ path │ │ int32[]│ struct("from"integer,"to"integer)[]│ ├───────────┼────────────────────────────────────────────────────────────────────┤ │[1]│[]│ │[2,3]│[{'from':1,'to':2}]│ │[4,3]│[{'from':1,'to':2},{'from':2,'to':4}]│ │[5,6,3]│[{'from':1,'to':2},{'from':2,'to':4},{'from':4,'to':5}]│ │[6,3]│[]│ │[3]│[]│ │[]│[]│ └───────────┴────────────────────────────────────────────────────────────────────┘