问题描述
是否有一个既定的算法来查找图中的冗余边?
Is there an established algorithm for finding redundant edges in a graph?
比如我想找出 a->d 和 a->e 是多余的，然后去掉它们，像这样:
For example, I'd like to find that a->d and a->e are redundant, and then get rid of them, like this:
=>
Strilanc 很好，可以帮我读懂我的想法.冗余"这个词太强了，因为在上面的例子中，a->b 或 a->c 都不被认为是冗余的，而 a->d 是.
Strilanc was nice enough to read my mind for me. "Redundant" was too strong of a word, since in the example above, neither a->b or a->c is considered redundant, but a->d is.
推荐答案
您想计算保持顶点可达性的最小图.
You want to compute the smallest graph which maintains vertex reachability.
这称为图的传递归约.维基百科文章应该会让你走上正确的道路.
This is called the transitive reduction of a graph. The wikipedia article should get you started down the right road.
这篇关于在图或树中寻找冗余边的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！