一尘不染

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

algorithm

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

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

替代文字 =>
替代文字

编辑:Strilanc足以让我读懂我的想法。“冗余”这个词太强了,因为在上面的示例中,a-> b或a-> c都不被认为是冗余的,而a->
d则被认为是冗余的。


阅读 256

收藏
2020-07-28

共1个答案

一尘不染

您要计算保持顶点可达性的最小图形。

这称为图形的传递归约。维基百科文章应该使您开始正确的道路。

2020-07-28