基于TypeORM/SQL/NestJS的产品循环关系检测方案问询

问题背景 #

当前定义的Product实体类如下：

@Entity()
export class Product {
  @PrimaryGeneratedColumn()
  id: number;

  @ManyToMany(() => Product, (product) => product.id, {
    onDelete: 'RESTRICT',
    onUpdate: 'CASCADE',
  })
  @JoinTable({ joinColumn: { name: 'product_id_1' } })
  sub_products: Product[];

  ...
}

在用户创建/更新产品时，需要检测产品间是否存在循环关系。例如：

• ID为1的产品A包含子产品[B]
• ID为2的产品B包含子产品[C]
• 用户尝试将ID为3的产品C的子产品设为[A]，此操作需被阻止

拟定的解决思路：

1. 通过递归查询数据库构建图结构，顶点为产品，边代表父产品到子产品的关系
2. 运行DFS循环检测算法

现有两个疑问：

1. 构建图时，仅为未访问过的节点构建顶点/边是否可行？即维护已访问产品集合，若后续产品在集合中则跳过构建
2. 通过以下测试用例能否验证方案的正确性？
   测试用例：

• 无循环结构
• 简单循环结构
• 树形结构（节点4被访问两次但无循环）
• 复杂循环结构

解答 #

1. 构建图时跳过已访问节点的可行性 #

完全可行。因为在循环检测的时间窗口内，数据库中的产品关系是固定的，每个产品节点只需要被处理一次：

• 维护已访问集合，遇到已存在的节点直接跳过，能避免重复构建顶点和边，显著提升构建效率，尤其是产品数量较多时
• 注意：如果是更新操作，要先把当前待更新产品的新子产品关系临时加入图中再执行检测，不能直接复用旧的已访问集合，否则会漏掉新关系可能引入的循环

2. 测试用例的覆盖性验证 #

这四个测试用例基本能覆盖核心场景，可以有效验证方案的正确性：

• 无循环结构：验证算法不会误判正常的层级关系
• 简单循环结构：验证算法能识别最基础的闭环（如A→B→C→A）
• 树形结构（节点被重复访问但无循环）：验证算法不会把共享子节点的情况误判为循环（比如A和B都包含C，遍历A时访问C，遍历B时再次访问C，此时不应触发循环检测）
• 复杂循环结构：验证算法能识别嵌套、多分支的闭环（比如A→B→C，B→D→A这种跨分支的循环）

如果要进一步提升严谨性，可以补充自循环测试用例（比如产品A的子产品包含自己），因为ManyToMany关系默认可能允许这种情况，需要确保算法能检测到。

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