У меня есть дерево со структурой, как это:Как правильно маркировать ветви дерева в глубине первого поиска
__2__3__4
/ \__5__6
0__1___7/__8__9
\\
\\__10__11__12
\__ __ __
13 14 15
Узел 1 имеет четверых детей (2,7,10,13), узлы 2 и 7 имеют по два ребенка каждый (оба разделяют узел 5 как ребенок). То, что я пытаюсь сделать, это создать ОТВ, которые обеспечивают записи, содержащие родительский узел, узел, расстояние от корня и ветви (или вилку) его содержимое в.
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
как вы можете видеть на вилках 1 и 2, я думаю, что лучший метод будет подсчитывать ветвь дважды придав ему свой собственный идентификатор, таким образом, сохраняя уникальность комбинации хопа и вилки.
Пожалуйста, помогите мне выяснить, что мне нужно сделать, чтобы достичь этого. Я считаю, что это должно быть возможно с помощью CTE, но, возможно, я ошибаюсь, и если бы я был бы рад узнать, какой лучший способ справиться с этим был бы.
EDIT Результирующий набор будет выглядеть так:
Предшественник, ID, заказ Обнаружен, Путь, вилка
нуль, 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
Поскольку узел '5' имеет двух родителей, это ** не дерево **, а просто ** ** графа – AakashM
Можете ли вы предоставить сценарий с вашей структурой таблицы и примерами данных и показать, какой желаемый набор результатов для этих данных? –
@AakashM - Не просто график, а ориентированный граф (ака орграф). – HABO