sql-server-2008 - 如何在深度优先搜索中正确标记树的分支

Question

我有一棵树的结构是这样的:

     __2__3__4
    /   \__5__6
0__1___7/__8__9
   \\
    \\__10__11__12
     \__  __  __
        13  14  15

节点 1 有四个子节点 (2,7,10,13)，节点 2 和 7 各有两个子节点(都共享节点 5 作为子节点)。我想要做的是创建一个 CTE，它提供包含父节点、节点、距根的距离及其包含的分支(或 fork )的记录。

IF (OBJECT_ID('tempdb..#Discovered') IS NOT NULL)
BEGIN
    DROP TABLE #Discovered
END

CREATE TABLE #Discovered
(
    ID int PRIMARY KEY NOT NULL,
    Predecessor int NULL,
    OrderDiscovered int
);

INSERT INTO #Discovered (ID, Predecessor, OrderDiscovered)
VALUES (@nodeId, NULL, 0);

    --loop through node connections table in a breadth first manner
WHILE @@ROWCOUNT > 0
BEGIN
    INSERT INTO #Discovered (ID, Predecessor, OrderDiscovered)
    SELECT c.node2_id
               ,MIN(c.node1_id)
               ,MIN(d.OrderDiscovered) + 1

    FROM #Discovered d JOIN node_connections c ON d.ID = c.node1_id
    WHERE c.node2_id NOT IN (SELECT ID FROM #Discovered)
    GROUP BY c.node2_id
END;

SELECT * FROM #Discovered;

WITH BacktraceCTE(Id, Predecessor, OrderDiscovered, Path, fork)

 AS 

 (  

     SELECT d.ID, d.Predecessor, d.OrderDiscovered, CAST(d.ID AS varchar(MAX)), 0

     FROM #Discovered d

     WHERE d.Id = @itemId


     UNION ALL             

     -- Recursive member, select all the nodes which have the previous

     SELECT d.ID, d.Predecessor, d.OrderDiscovered,  

         CAST(cte.Path + '->' + CAST(d.ID as varchar(10)) as varchar(MAX)),
         fork + CONVERT ( Integer, ROW_NUMBER() OVER (ORDER BY d.ID)) - 1

     FROM #Discovered d JOIN BacktraceCTE cte ON d.Predecessor = cte.ID

 )          

 SELECT  Predecessor as node1_id, OrderDiscovered as hop, fork, ID as node2_id, Path FROM BacktraceCTE  
 ORDER BY fork, OrderDiscovered;

问题在于叉是如何计算的。每次 CTE 返回到前一级别时，它只有可用的行号以及该级别的 fork 号。我想要实现的是记录，其中每一个跳和叉的组合都是独一无二的。

但是，使用上面的代码，我会得到结果，说节点 2 到 5 最终成为第 3 跳叉 1，节点 7 到 5 也最终成为第 3 跳叉 1。

这又是树，带有分支的标签以及它们应该如何出现:

     __2__3__4      :0
    /   \__5__6     :1,2
0__1___7/__8__9     :3
   \\
    \\__10__11__12  :4
     \__  __  __
        13  14  15  :5

正如您所看到的 fork 1 和 2，我认为最好的方法是将分支计数两次并为其提供自己的标识符，从而保留 hop 和 fork 组合的唯一性。

请帮助我弄清楚我需要做什么才能实现这一目标。我觉得这应该可以通过 CTE 实现，但也许我错了，如果我错了，我很想知道解决这个问题的更好方法是什么。

编辑
结果集如下所示:

前身，ID，发现的顺序，路径， fork

空, 0, 0, 0, 0

0, 1, 1, 0->1, 0

1, 2, 2, 0->1->2, 0

2, 3, 3, 0->1->2->3, 0

3, 4, 4, 0->1->2->3->4, 0

2, 5, 3, 0->1->2->5, 1

5, 6, 4, 0->1->2->5->6, 1

1, 7, 2, 0->1->7, 2

7, 5, 3, 0->1->7->5, 2

5, 6, 4, 0->1->7->5->6, 2

7, 8, 3, 0->1->7->8, 3

8, 9, 4, 0->1->7->8->9, 3

1, 10, 2, 0->1->10, 4

10, 11, 3, 0->1->10->11, 4

11, 12, 4, 0->1->10->11->12, 4

1, 13, 2, 0->1->13, 5

13, 14, 3, 0->1->13->14, 5

14, 15, 4, 0->1->13->14->15, 5

Answer 1

好的，我会尽量避免再次调整这个答案。学习 VarBinary 的排序顺序、找到 POWER 函数、CTE 相互竞争，真是太有趣了……

您是否正在寻找以下内容:

declare @Nodes as Table ( NodeId Int Identity(0,1), Name VarChar(10) )
declare @Relations as Table ( ParentNodeId Int, ChildNodeId Int, SiblingOrder Int )
insert into @Nodes ( Name ) values
--  ( '0' ), ( '1' ), ( '2' ), ( '3' ), ( '4' ), ( '5' ), ( '6' ), ( '7' ), ( '8' ),
--  ( '9' ), ( '10' ), ( '11' ), ( '12' ), ( '13' ), ( '14' ), ( '15' )
  ( 'zero' ), ( 'one' ), ( 'two' ), ( 'three' ), ( 'four' ), ( 'five' ), ( 'six' ), ( 'seven' ), ( 'eight' ),
  ( 'nine' ), ( 'ten' ), ( 'eleven' ), ( 'twelve' ), ( 'thirteen' ), ( 'fourteen' ), ( 'fifteen' )

insert into @Relations ( ParentNodeId, ChildNodeId, SiblingOrder ) values
  ( 0, 1, 0 ),
  ( 1, 2, 0 ), ( 1, 7, 1 ), ( 1, 10, 2 ), ( 1, 13, 3 ),
  ( 2, 3, 0 ), ( 2, 5, 1 ),
  ( 3, 4, 0 ),
  ( 5, 6, 0 ),
  ( 7, 5, 0 ), ( 7, 8, 1 ),
  ( 8, 9, 0 ),
  ( 10, 11, 0 ),
  ( 11, 12, 0 ),
  ( 13, 14, 0 ),
  ( 14, 15, 0 )

declare @MaxSiblings as BigInt = 100
; with
DiGraph ( NodeId, Name, Depth, ParentNodeId, Path, ForkIndex, DepthFirstOrder )
as (
  -- Start with the root node(s).
  select NodeId, Name, 0, Cast( NULL as Int ), Cast( Name as VarChar(1024) ),
    Cast( 0 as BigInt ), Cast( Right( '00' + Cast( 0 as VarChar(2) ), 2 ) as VarChar(128) )
    from @Nodes
    where not exists ( select 42 from @Relations where ChildNodeId = NodeId )
  union all
  -- Add children one generation at a time.
  select R.ChildNodeId, N.Name, DG.Depth + 1, R.ParentNodeId, Cast( DG.Path + ' > ' + N.Name as VarChar(1024) ),
    DG.ForkIndex + R.SiblingOrder * Power( @MaxSiblings, DG.Depth - 1 ),
    Cast( DG.DepthFirstOrder + Right( '00' + Cast( R.SiblingOrder as VarChar(2) ), 2 ) as VarChar(128) )
    from @Relations as R inner join
      DiGraph as DG on DG.NodeId = R.ParentNodeId inner join
      @Nodes as N on N.NodeId = R.ChildNodeId inner join
      @Nodes as Parent on Parent.NodeId = R.ParentNodeId
  ),

DiGraphSorted ( NodeId, Name, Depth, ParentNodeId, Path, ForkIndex, DepthFirstOrder, RowNumber )
as ( select *, Row_Number() over ( order by DepthFirstOrder ) as 'RowNumber' from DiGraph )

select ParentNodeId, NodeId, Depth, Path,
  ( select Count(*) from DiGraphSorted as L
    left outer join DiGraphSorted as R on R.RowNumber = L.RowNumber - 1 where
    R.RowNumber < DG.RowNumber and L.ForkIndex <> R.ForkIndex ) as 'ForkNumber' -- , '', *
  from DiGraphSorted as DG
  order by RowNumber