如何在深度优先搜索中正确标记树的分支 [英] How to properly label branches of a tree in a depth first search
问题描述
我有一棵树，其结构如下：
I have a tree with a structure like this:
__2__3__4
/ \__5__6
0__1___7/__8__9
\\
\\__10__11__12
\__ __ __
13 14 15
节点1有四个子节点（2、7、10、13），节点2和7各自有两个子节点（两个节点都作为子节点共享）。我正在尝试做的是创建一个CTE，该CTE提供包含父节点，该节点，到根的距离以及其中包含的分支（或分支）的记录。
Node 1 has four children (2,7,10,13), nodes 2 and 7 have two children each (both sharing node 5 as a child). What I am trying to do is create a CTE that provide records containing the parent node, the node, the distance away from the root, and the branch (or fork) its contained in.
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返回到先前的级别时，它只有可用的行号以及该级别的分叉号。我想要实现的是记录，其中跳和叉的每个组合都是唯一的。
The problem is with how the fork is calculated. Every time the CTE returns back to a previous level it only has the row numbers available and what the fork number was at that level. What I'd like to achieve is records where each combination of hop and fork are unique.
但是，使用上面的代码，我将得到表示节点2到5最终成为跃点3分支1，而节点7至5也最终成为跃点3分支1。
However, with the above code I'll get results that say node 2 to 5 end up being hop 3 fork 1 AND node 7 to 5 also end up being hop 3 fork 1.
这又是带有分支标签的树它们应该出现：
Here is the tree again with the labeling of the branches with how they should appear:
__2__3__4 :0
/ \__5__6 :1,2
0__1___7/__8__9 :3
\\
\\__10__11__12 :4
\__ __ __
13 14 15 :5
对于派生1和派生2，我认为最好的方法是对分支进行两次计数，为其赋予自己的标识符，从而保留分支的唯一性。
As you can see for forks 1 and 2 I think that the best method would be to count the branch twice giving it its own identifier thus preserving the uniqueness of the combination of hop and fork.
请帮助我弄清楚实现此目的所需要做的事情。我认为CTE应该可以实现，但也许我错了，如果我愿意，我想知道解决这个问题的更好方法。
Please help me figure out what I need to do in order to achieve this. I feel this should be possible with a CTE but perhaps I am wrong and if I am I'd love to know what the better method to tackle this would be.
编辑
结果集如下：
EDIT The result set would look like:
前身，ID，发现的订单，路径，叉子
Predecessor, ID, Order Discovered, Path, Fork
-
null，0，0，0，0
null, 0, 0, 0, 0
0，1，1 ，0-> 1，0
0, 1, 1, 0->1, 0
1,2,2,0-> 1-> 2，0
1, 2, 2, 0->1->2, 0
2，3，3，0-> 1-> 2-> 3，0
2, 3, 3, 0->1->2->3, 0
3，4，4， 0-> 1-> 2-> 3-> 4，0
3, 4, 4, 0->1->2->3->4, 0
2，5，3，0-> 1-> 2-> 5， 1
2, 5, 3, 0->1->2->5, 1
5，6，4，0-> 1-> 2-> 5-> 6，1
5, 6, 4, 0->1->2->5->6, 1
1，7，2，0-> 1-> 7，2
1, 7, 2, 0->1->7, 2
7，5，3，0-> 1-> 7-> 5，2
7, 5, 3, 0->1->7->5, 2
5，6，4，0-> 1-> 7-> 5-> 6，2
5, 6, 4, 0->1->7->5->6, 2
7，8，3，0-> 1-> 7-> 8，3
7, 8, 3, 0->1->7->8, 3
8、9、4、0-> 1-> 7-> 8-> 9、3
8, 9, 4, 0->1->7->8->9, 3
1、10、2、0-> 1-> 10，4
1, 10, 2, 0->1->10, 4
10，11，3，0-> 1-> 10-> 11，4
10, 11, 3, 0->1->10->11, 4
11，12，4，0-> 1-> 10-> 11-> 12，4
11, 12, 4, 0->1->10->11->12, 4
1 ，13，2，0-> 1-> 13， 5
1, 13, 2, 0->1->13, 5
13，14，3，0-> 1-> 13-> 14，5
13, 14, 3, 0->1->13->14, 5
14、15、4、0-> 1-> 13-> 14-> 15、5
14, 15, 4, 0->1->13->14->15, 5
推荐答案
好的，我会尽量避免重新调整此答案。了解VarBinary的排序顺序，找到POWER函数，CTE互相殴打，... ...真是太有趣了。
Okay, I'll try to refrain from tweaking this answer again. It's just been so fun learning about the sort order of VarBinary, finding the POWER function, CTEs beating on one another, ... .
您是否正在寻找类似的东西：
Are you looking for anything like:
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
这篇关于如何在深度优先搜索中正确标记树的分支的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
