在有向无环图中找到层级树的算法？

Question

我有一个具有以下属性的图表：

邻接矩阵：

图表表示：

哪种算法可以应用于查找上述图形的层次树？在我的话中，层次树是一种只连接并指向其直接子节点的节点，并且应删除从当前到子代或任何其他子代的边缘。

对于上面的图表，层次树将如下所示：

层次树：

- Sai Nikhil

---

图片应该上传到StackOverflow（技术上是imgur），以防外部链接失效。在编辑页面时，单击“添加图像”并将其指向存储在计算机或在线上的文件。 - Bernhard Barker

现在你能看到它们吗？ - Sai Nikhil

据我所理解，所有指向非子代祖先的边都应该被删除。 - Bernhard Barker

@Dukeling 你所说的“非子代祖先”是什么意思？ - luiso1979

@luiso1979 祖先 不是子节点。5不是4的祖先，因此不应删除4-5。6-5是从节点到其非子孙的唯一边缘（5是6的祖先，但不是其子节点）。 - Bernhard Barker

Answer 1

我认为传递闭包约简可能是你正在寻找的。查看这个链接：https://cs.stackexchange.com/questions/7096/transitive-reduction-of-dag 实现链接

- Danstahr