基于SQL Server表模拟的全图节点查询问题

在SQL Server 2019中，通过NODE（ID、NAME列）和EDGE（PARENTELEMENTID、CHILDELEMENTID列）两张表模拟图结构时，原有递归CTE仅支持树结构遍历，无法从任意节点出发获取所属全图的所有节点。以下是针对该问题的解决方案：

表结构与测试数据 #

CREATE TABLE NODE(ID int, NAME varchar(1));
CREATE TABLE EDGE(PARENTELEMENTID int, CHILDELEMENTID int);

INSERT INTO NODE (Id, Name) VALUES(1, 'A');
INSERT INTO NODE (Id, Name) VALUES(2, 'B');
INSERT INTO NODE (Id, Name) VALUES(3, 'C');
INSERT INTO NODE (Id, Name) VALUES(4, 'D');
INSERT INTO NODE (Id, Name) VALUES(5, 'E');
INSERT INTO NODE (Id, Name) VALUES(6, 'F');
INSERT INTO NODE (Id, Name) VALUES(7, 'G');
INSERT INTO NODE (Id, Name) VALUES(8, 'H');
INSERT INTO NODE (Id, Name) VALUES(9, 'I');
INSERT INTO NODE (Id, Name) VALUES(10, 'J');

INSERT INTO EDGE (ParentElementId, ChildElementId) VALUES (1, 4);
INSERT INTO EDGE (ParentElementId, ChildElementId) VALUES (1, 5);
INSERT INTO EDGE (ParentElementId, ChildElementId) VALUES (2, 4);
INSERT INTO EDGE (ParentElementId, ChildElementId) VALUES (2, 6);
INSERT INTO EDGE (ParentElementId, ChildElementId) VALUES (3, 7);
INSERT INTO EDGE (ParentElementId, ChildElementId) VALUES (4, 7);
INSERT INTO EDGE (ParentElementId, ChildElementId) VALUES (5, 8);
INSERT INTO EDGE (ParentElementId, ChildElementId) VALUES (6, 9);
INSERT INTO EDGE (ParentElementId, ChildElementId) VALUES (10, 9);

现有查询的问题 #

原有查询仅通过“先找父节点到根，再从根向下遍历子节点”的单向逻辑处理，无法覆盖图结构中双向的关联路径，导致遗漏部分节点（例如从节点1出发时，无法关联到节点10）。

解决方案：双向递归遍历全图 #

使用双向递归CTE，同时遍历当前节点的所有父节点和子节点，并通过已访问节点集合避免循环，最终获取所有可达节点：

DECLARE @StartNodeId INT = 1; -- 可替换为任意节点ID

WITH GraphTraversal AS (
    -- 初始节点：起始节点
    SELECT 
        Id = @StartNodeId,
        -- 用字符串记录已访问节点，避免循环
        VisitedNodes = CONCAT(',', @StartNodeId, ',')
    FROM NODE
    WHERE Id = @StartNodeId

    UNION ALL

    -- 递归遍历：同时处理父节点和子节点
    SELECT
        -- 取新的可达节点
        CASE 
            WHEN e.ParentElementId NOT IN (SELECT value FROM STRING_SPLIT(gt.VisitedNodes, ',')) THEN e.ParentElementId
            ELSE e.ChildElementId
        END AS Id,
        -- 更新已访问节点集合
        CONCAT(gt.VisitedNodes, 
            CASE 
                WHEN e.ParentElementId NOT IN (SELECT value FROM STRING_SPLIT(gt.VisitedNodes, ',')) THEN CONCAT(e.ParentElementId, ',')
                ELSE CONCAT(e.ChildElementId, ',')
            END) AS VisitedNodes
    FROM GraphTraversal gt
    -- 关联EDGE表，找出所有与当前节点关联的父/子节点
    JOIN EDGE e 
        ON e.ParentElementId = gt.Id OR e.ChildElementId = gt.Id
    -- 过滤已访问过的节点，避免循环
    WHERE 
        (e.ParentElementId NOT IN (SELECT value FROM STRING_SPLIT(gt.VisitedNodes, ',')) 
        OR e.ChildElementId NOT IN (SELECT value FROM STRING_SPLIT(gt.VisitedNodes, ',')))
)
-- 去重后返回所有节点信息
SELECT DISTINCT n.*
FROM GraphTraversal gt
JOIN NODE n ON gt.Id = n.Id
ORDER BY n.Id;

逻辑说明 #

1. 初始节点：指定起始节点，初始化已访问节点集合。
2. 递归遍历：每次递归时，找出当前节点关联的所有父节点和子节点，过滤掉已访问的节点，更新已访问集合。
3. 去重返回：由于递归过程中可能重复获取同一节点，最终通过DISTINCT去重后返回全量节点。

验证 #

将@StartNodeId替换为任意节点ID（例如1、10、3等），均可返回所有10个节点，实现从任意节点获取全图所有节点的需求。

内容的提问来源于stack exchange，提问作者Zyan