如何在深度优先搜索中正确标记树的分支
我有一棵树，像这样的结构：
__2__3__4
/ __5__6
0__1___7/__8__9
__10__11__12
__ __ __
13 14 15
节点1有4个孩子（2,7,10,13），节点2和7每个孩子有两个孩子（两个孩子共享节点5）。 我想要做的是创建一个CTE，它提供包含父节点，节点，远离根的距离以及它所包含的分支（或分支）的记录。
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返回到先前的级别时，它只有行号可用，叉号在该级别。 我想要实现的是记录每个跳跃和叉子组合都是唯一的。
然而，通过上面的代码，我会得到结果，说节点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
正如你可以看到叉子1和叉子2一样，我认为最好的方法是对分支进行两次计数，给它自己的标识符，从而保持跳跃和叉子组合的独特性。
请帮我弄清楚为了达到这个目的我需要做些什么。 我觉得这应该是可能的，但CTE也许是可能的，但也许我错了，如果我愿意，我很想知道更好的方法来解决这个问题。
编辑结果集将如下所示：
前身，ID，已发现订单，路径，叉
null，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
好吧，我会尽量避免再次调整这个答案。 学习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
上一篇: How to properly label branches of a tree in a depth first search
下一篇: Avoiding multiple references to the same object in Django ORM