郭其先生利用DeepSeek实现的PostgreSQL递归CTE实现DFS写法

测试用表

CREATETABLEtree_nodes(idINTPRIMARYKEY,parent_idINTREFERENCEStree_nodes(id),nameVARCHAR(50));INSERTINTOtree_nodesVALUES(1,NULL,'根节点'),(2,1,'子节点1'),(3,1,'子节点2'),(4,2,'孙子节点1'),(5,2,'孙子节点2'),(6,3,'孙子节点3');

使用递归 CTE 实现 DFS：

WITHRECURSIVE dfsAS(-- 锚点：从根节点开始SELECTid,parent_id,name,1ASdepth,ARRAY[id]ASpath,ARRAY[name]::text[]ASpath_names,FALSEASis_cycleFROMtree_nodesWHEREparent_idISNULLUNIONALL-- 递归部分：深度优先遍历SELECTtn.id,tn.parent_id,tn.name,d.depth+1,d.path||tn.id,d.path_names||tn.name,tn.id=ANY(d.path)ASis_cycleFROMtree_nodes tnJOINdfs dONtn.parent_id=d.idWHERENOTd.is_cycle-- 防止循环)-- 按深度优先顺序输出SELECTid,parent_id,name,depth,path,path_namesFROMdfsORDERBYpath;

使用栈模拟 DFS

WITHRECURSIVE dfs_stackAS(-- 初始栈：包含根节点SELECT1ASstep,idAScurrent_node,name,ARRAY[id]ASstack,ARRAY[]::INT[]ASvisited,'visit'ASactionFROMtree_nodesWHEREparent_idISNULLUNIONALL-- 模拟栈操作：弹出、压入SELECTd.step+1,CASE-- 如果有未访问的子节点，访问第一个WHENEXISTS(SELECT1FROMtree_nodes tnWHEREtn.parent_id=d.current_nodeANDtn.id!=ALL(d.visited))THEN(SELECTtn.idFROMtree_nodes tnWHEREtn.parent_id=d.current_nodeANDtn.id!=ALL(d.visited)ORDERBYtn.idLIMIT1)-- 否则回溯ELSEd.stack[array_length(d.stack,1)-1]END,tn.name,CASE-- 访问新节点：压栈WHENEXISTS(SELECT1FROMtree_nodes tnWHEREtn.parent_id=d.current_nodeANDtn.id!=ALL(d.visited))THENd.stack||(SELECTtn.idFROMtree_nodes tnWHEREtn.parent_id=d.current_nodeANDtn.id!=ALL(d.visited)ORDERBYtn.idLIMIT1)-- 回溯：出栈ELSEd.stack[1:array_length(d.stack,1)-1]END,d.visited||d.current_node,CASEWHENEXISTS(SELECT1FROMtree_nodes tnWHEREtn.parent_id=d.current_nodeANDtn.id!=ALL(d.visited))THEN'push'ELSE'pop'ENDFROMdfs_stack dLEFTJOINtree_nodes tnONtn.id=d.current_nodeWHEREarray_length(d.stack,1)>0-- 栈不为空时继续)SELECTstep,current_node,name,stack,action,visitedFROMdfs_stackORDERBYstep;