算法寻找多余的边以图或树 [英] Algorithm for Finding Redundant Edges in a Graph or Tree

问题描述

有没有一个既定的算法找出多余的边在图形？

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.

这篇关于算法寻找多余的边以图或树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！