问题描述
有没有一个既定的算法找出多余的边在图形？
Is there an established algorithm for finding redundant edges in a graph?
例如，我想找到A-> D和A->电子是多余的，然后摆脱他们，像这样的：
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.
这篇关于算法寻找多余的边以图或树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！