在图或树中查找冗余边的算法

Question

是否存在用于在图中查找冗余边的既定算法？

例如,我想发现a-> d和a-> e是多余的,然后摆脱它们,如下所示:

=>

编辑:Strilanc很高兴能为我读懂我的想法."冗余"太强了,因为在上面的例子中,a-> b或a-> c都不被认为是冗余的,但a-> d是.

Answer 1

您想要计算保持顶点可达性的最小图.

这称为图的传递减少.维基百科文章应该让你开始走正确的道路.