有向无环图(DAG)可添加无环新边的判定方法及算法咨询

现有一有向无环图G，需生成一种数据结构以判定哪些新边(u,v)添加后仍能保持图的无环性。例如左侧图G（顶点集[A,B,C,D]），需生成右侧图G_（顶点集[A_,B_,C_,D_]），其中包含所有可单独添加至G的合法新边。G_本身可能存在环，但每条边单独添加至G不会导致环；每次向G添加新边后会重新计算G_，且G允许存在重复边。

本人提出的方法如下：

• 生成图的传递闭包；
• 对传递闭包进行转置，得到G_t；
• 对每个顶点u，获取G_t中u的邻接顶点列表u_，这些顶点v对应的边(u,v)添加后会导致环；
• 用所有顶点集合减去u_，得到的结果即为可添加边(u,v)对应的合法v列表。

现咨询两点：
a) 该方法是否为最优方案；
b) 该方法或所得图G_是否已有特定名称，或已被某一算法涵盖。

背景信息：图的顶点数约为10-100个。

a) 该方法是否为最优方案 #

对于顶点数10-100的规模来说，你的方法已经非常高效实用。
传递闭包可以用Floyd-Warshall算法（时间复杂度O(n³)）或者基于DFS的方法（时间复杂度O(n(n+m))）计算，在n=100的情况下，O(n³)仅为1e6级别的运算量，普通计算机完全可以轻松处理，不会有性能瓶颈。
从逻辑上看，判断边(u,v)是否导致环的核心就是是否存在从v到u的路径（原图是DAG，添加(u,v)后形成环等价于v可达u），你的方法通过传递闭包转置获取u的前驱可达顶点，本质就是找出所有能到达u的v，逻辑完全正确。
如果追求极致优化，稀疏图可以用DFS/BFS逐个判断(u,v)组合，但实现复杂度更高，而你的方法代码简洁、维护性好，在当前场景下完全没必要替换，属于最优实用方案。

b) 相关名称与算法关联 #

• 你生成的图G_通常被称为DAG的传递补图（Transitive Complement Graph）——传递补图的定义就是原传递闭包中不存在的边所构成的图，正好对应这里的合法可加边集合（传递闭包中存在v→u时，u→v不能添加，反之则可以）。也有资料将其称为DAG的可加边图。
• 你的方法本质是利用传递闭包与传递补图的关系生成合法边集合，这是DAG无环性维护中的经典思路，很多DAG扩展、拓扑排序相关的场景都会用到这个逻辑，比如动态维护DAG拓扑序时，就会依赖传递闭包判断新边合法性。

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