我想知道是否可以通过SQL或一些基于SQL的工具(如Informatica，Talend等(实现dfs。
V1
V2 V3
V4 V5 V6 V7
V8
V1 有 V2,8,3
V2 有 V4,5
V3 有 V6,7
V4,5,6,7 已连接 V8
DFS是V12485673。
Vertices NodeRelated
1 2
1 3
1 8
2 4
2 5
3 6
3 7
4 8
5 8
6 8
7 8
8 null
O/p 12485673
深度优先搜索正是connect by遍历层次结构的方式。 因此，connect by生成行源时分配的rownum可用于定义顺序。
当特定父项有多个子项时，顶点将多次出现在结果中。 当给定节点具有多个父节点时，节点相关将出现多次。
在您的情况下，这两个条件都满足，因此两个顶点/节点相关都有"重复"，但为了返回唯一节点并保持 DFS 顺序，您可以依赖如下所示min(rownum)。
with t (vertices, noderelated) as
(
select 1, 2 from dual
union all select 1, 3 from dual
union all select 1, 8 from dual
union all select 2, 4 from dual
union all select 2, 5 from dual
union all select 3, 6 from dual
union all select 3, 7 from dual
union all select 4, 8 from dual
union all select 5, 8 from dual
union all select 6, 8 from dual
union all select 7, 8 from dual
union all select 8, null from dual
)
select listagg(vertices, ', ') within group (order by min(rownum)) result
from t
start with vertices = 1
connect by prior noderelated = vertices
group by vertices;
RESULT
------------------------------
1, 2, 4, 8, 5, 3, 6, 7
有了你的例子，这就是你可以做的。想法是将数据分为左元素和右元素。
WITH pre_a AS (
Select 1 as Vertices,2 as NodeRelated FROM DUAL UNION ALL
Select 1,3 FROM DUAL UNION ALL
Select 2,4 FROM DUAL UNION ALL
Select 2,5 FROM DUAL UNION ALL
Select 3,6 FROM DUAL UNION ALL
Select 3,7 FROM DUAL UNION ALL
Select 4,8 FROM DUAL UNION ALL
Select 5,8 FROM DUAL UNION ALL
Select 6,8 FROM DUAL UNION ALL
Select 7,8 FROM DUAL UNION ALL
Select 8,null FROM DUAL
) -- create parent/child and calculate dept level as col l
,r(Vertices,NodeRelated,l) as (
Select pre_a.*,0 as l from pre_a
Union all
Select t2.Vertices,t2.NodeRelated, l+1
from pre_a t2
join r ON t2.Vertices=r.NodeRelated
)
,s_one as ( -- mark left / right child assuming it will be always there
Select distinct r.*
,ROW_NUMBER() Over(partition by l order by Vertices) rn
,CASE WHEN MOD(ROW_NUMBER() Over(partition by l order by Vertices),2) = 0
THEN 'R' ELSE 'L' END L_R_Edge
from r
)
,top_LVL_Right_edge as ( -- Create clean temp table as per your visual representation
Select s_one.* , row_number() Over(Partition by l order by noderelated desc)
rn_by_vertices
from s_one
WHERE l = ( Select max(l) from r where vertices=s_one.vertices and
noderelated=s_one.noderelated group by vertices )
--and L_R_Edge='R'
order by vertices
)
,first_left_edge as -- Get only the left most elements
(
Select s_one.*,99 from s_one Where rn =1 and L_R_Edge = 'L' order by l
)
,right_edge_lvl_gt_1 as ( -- get the right elements and the inner left elements
Select s_one.*
,row_number() Over(Partition by vertices order by rn asc) n_rn
from s_one
Where NodeRelated IS NOT null
and l > 1
and rn !=1 order by l desc, vertices
)
,final as ( -- just combine all as per sequence
Select * from first_left_edge UNION ALL
Select * from right_edge_lvl_gt_1 where n_rn=1 union all
Select * from top_LVL_Right_edge WHERE L = 1 and rn_by_vertices = 1
)
Select listagg(Vertices,',') within group( order by rownum) as op
from final
输出
OP
-----------
1,2,4,8,5,6,7,3
有几件事：
- 我对深度优先搜索的理解是 V3 应该出现在输出中的 V6 和 7 之前，而不是之后
- 如果存储每个顶点的父顶点而不是其子项，则更容易沿着图形向下移动
如果这些调整对您来说没问题，那么深度优先搜索很容易：在recursive with的search子句中指定它！
with rws as (
select 1 v, null related from dual union all
select 2 v, 1 related from dual union all
select 8 v, 1 related from dual union all
select 3 v, 1 related from dual union all
select 4 v, 2 related from dual union all
select 5 v, 2 related from dual union all
select 6 v, 3 related from dual union all
select 7 v, 3 related from dual union all
select 8 v, 4 related from dual union all
select 8 v, 5 related from dual union all
select 8 v, 6 related from dual union all
select 8 v, 7 related from dual
), dfs ( v, related ) as (
select r.*
from rws r
where v = 1
union all
select r.v, r.related
from dfs d
join rws r
on r.related = d.v
) search depth first by v set seq
select * from dfs;
V RELATED SEQ
1 <null> 1
2 1 2
4 2 3
8 4 4
5 2 5
8 5 6
3 1 7
6 3 8
8 6 9
7 3 10
8 7 11
8 1 12
您在search depth first by中指定的列确定返回行的顺序。
您需要做的就是从那里获取按深度排序的不同顶点列表。在 19c 中listagg distinct
with rws as (
select 1 v, null related from dual union all
select 2 v, 1 related from dual union all
select 8 v, 1 related from dual union all
select 3 v, 1 related from dual union all
select 4 v, 2 related from dual union all
select 5 v, 2 related from dual union all
select 6 v, 3 related from dual union all
select 7 v, 3 related from dual union all
select 8 v, 4 related from dual union all
select 8 v, 5 related from dual union all
select 8 v, 6 related from dual union all
select 8 v, 7 related from dual
), dfs ( v, related ) as (
select r.*
from rws r
where v = 1
union all
select r.v, r.related
from dfs d
join rws r
on r.related = d.v
) search depth first by v set seq
select listagg ( distinct v, ',' )
within group ( order by seq ) route
from dfs;
ROUTE
1,2,4,8,5,3,6,7
在早期版本中，您可以通过首先按顶点分组并返回每个顶点的最小序列来获得此结果：
with rws as (
select 1 v, null related from dual union all
select 2 v, 1 related from dual union all
select 8 v, 1 related from dual union all
select 3 v, 1 related from dual union all
select 4 v, 2 related from dual union all
select 5 v, 2 related from dual union all
select 6 v, 3 related from dual union all
select 7 v, 3 related from dual union all
select 8 v, 4 related from dual union all
select 8 v, 5 related from dual union all
select 8 v, 6 related from dual union all
select 8 v, 7 related from dual
), dfs ( v, related ) as (
select r.*
from rws r
where v = 1
union all
select r.v, r.related
from dfs d
join rws r
on r.related = d.v
) search depth first by v set seq,
vals as (
select d.v,
min ( seq ) min_s
from dfs d
group by v
)
select listagg ( v, ',' )
within group (
order by min_s
) route
from vals;
ROUTE
1,2,4,8,5,3,6,7