在有向非循环图中查找层次树的算法？

Question

我有一个属性图,如下所示:

邻接矩阵:

图形表示:

可以应用哪种算法来查找上图的层次树？在我看来,层次结构树是节点连接并仅指向其直接子节点的树,并且应该删除从子节点到子节点或任何其他节点的任何边缘.

对于上图,层次结构树将如下所示:

层次结构树:

Answer 1

我认为Transitive Reduction是您正在寻找的.检查一下:https://cs.stackexchange.com/questions/7096/transitive-reduction-of-dag

实施链接