如何通过匹配查询导出层级树形图数据及适配循环场景

我有一个图结构，节点和关系的层级定义为：节点类型1（NT1）->关系类型1（RT1）->节点类型2（NT2）->关系类型2（RT2）->节点类型3（NT3）。

样本节点数据（格式：类型, ID） #

NT1, A_1
NT2, B_1
NT2, B_2
NT2, B_3
NT3, C_1
NT3, C_2
NT3, C_3

样本关系数据（格式：类型, 节点ID1, 节点ID2） #

RT1, A_1, B_1
RT1, A_1, B_2
RT1, A_1, B_3
RT2, B_1, C_1
RT2, B_1, C_2
RT2, B_3, C_3

我需要导出嵌套式JSON树形结构，子节点直接嵌入父节点下，示例格式如下（无需严格匹配，只要能直接解析层级获取子节点即可）：

[
  { 
    "id": "A_1",
    "RT1": [ 
      {
        "id": "B_1",
        "RT2": [ {"id": "C_1"}, {"id": "C_2"} ]
      },
      {
        "id": "B_2",
        "RT2": []
      },
      {
        "id": "B_3",
        "RT2": [ {"id": "C_3"} ]
      }
    ]
  }  
]

实际场景中图存在循环（比如C_1关联回A_1和B_1），但本次只需要仅遍历指定关系类型的通用解决方案。我试过BFS、DFS和Stack Overflow上的示例，但得到的都是展开的节点列表，仍需自行关联数据，请问该怎么解决？

解决方案 #

核心思路 #

要构建嵌套结构，关键是按指定的关系层级顺序，将每个节点的子节点（通过指定关系关联的节点）直接挂载到父节点对象中，同时记录已访问节点避免循环（如果有需要）。

步骤1：预处理数据，建立关系映射 #

先把关系数据转换成按「关系类型+父节点ID」分组的映射，方便快速查找子节点。比如用字典存储：{关系类型: {父节点ID: [子节点ID列表]}}

步骤2：递归/迭代构建树形结构 #

从根节点（比如NT1类型的节点）出发，按照指定的关系层级依次向下遍历，为每个节点创建包含子节点的对象。如果遇到循环，通过记录已访问的节点ID来跳过，避免无限递归。

代码示例（Python） #

def build_nested_tree(nodes, relations, hierarchy):
    # 预处理关系：{relation_type: {parent_id: [child_ids]}}
    relation_map = {}
    for rt, parent_id, child_id in relations:
        if rt not in relation_map:
            relation_map[rt] = {}
        if parent_id not in relation_map[rt]:
            relation_map[rt][parent_id] = []
        relation_map[rt][parent_id].append(child_id)
    
    # 建立节点ID到类型的映射（用于过滤根节点）
    node_type_map = {id: typ for typ, id in nodes}
    
    # 构建节点的递归函数
    def build_node(node_id, current_hierarchy_idx, visited):
        # 标记当前节点已访问，避免循环
        visited.add(node_id)
        node_obj = {"id": node_id}
        
        # 如果当前层级还有下一个关系类型，继续构建子节点
        if current_hierarchy_idx < len(hierarchy) - 1:
            current_rt = hierarchy[current_hierarchy_idx][1]
            # 获取当前关系下的子节点ID列表
            child_ids = relation_map.get(current_rt, {}).get(node_id, [])
            child_nodes = []
            for child_id in child_ids:
                if child_id not in visited:
                    child_nodes.append(build_node(child_id, current_hierarchy_idx + 1, visited.copy()))
                else:
                    # 处理循环：可选标记为循环节点或直接跳过
                    child_nodes.append({"id": child_id, "is_cycle": True})
            node_obj[current_rt] = child_nodes
        return node_obj
    
    # 根节点是层级第一个节点类型的所有节点
    root_type = hierarchy[0][0]
    root_ids = [id for typ, id in nodes if typ == root_type]
    
    # 构建整个树
    tree = []
    for root_id in root_ids:
        tree.append(build_node(root_id, 0, set()))
    return tree

# 测试数据
nodes = [
    ("NT1", "A_1"),
    ("NT2", "B_1"),
    ("NT2", "B_2"),
    ("NT2", "B_3"),
    ("NT3", "C_1"),
    ("NT3", "C_2"),
    ("NT3", "C_3")
]

relations = [
    ("RT1", "A_1", "B_1"),
    ("RT1", "A_1", "B_2"),
    ("RT1", "A_1", "B_3"),
    ("RT2", "B_1", "C_1"),
    ("RT2", "B_1", "C_2"),
    ("RT2", "B_3", "C_3")
]

# 指定层级：[(节点类型, 对应关系类型), ...]，最后一个节点无后续关系则设为None
hierarchy = [("NT1", "RT1"), ("NT2", "RT2"), ("NT3", None)]

# 生成树形结构并打印
import json
result = build_nested_tree(nodes, relations, hierarchy)
print(json.dumps(result, indent=2))

输出结果 #

[
  {
    "id": "A_1",
    "RT1": [
      {
        "id": "B_1",
        "RT2": [
          {
            "id": "C_1"
          },
          {
            "id": "C_2"
          }
        ]
      },
      {
        "id": "B_2",
        "RT2": []
      },
      {
        "id": "B_3",
        "RT2": [
          {
            "id": "C_3"
          }
        ]
      }
    ]
  }
]

关键说明 #

• 层级指定：通过hierarchy参数明确节点类型和对应的关系类型，确保只遍历指定的关系路径，不会走其他关联。
• 循环处理：用visited集合记录已访问的节点ID，遇到已访问的节点时可以跳过或标记为循环节点，避免无限递归。
• 灵活性：代码可扩展支持更多层级，只需修改hierarchy参数即可。

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