recursion - 如何找到图中所有等效的顶点？

Question

等效顶点是指具有相同“入口”和“出口”顶点的那些顶点。



有人可以帮助我如何处理算法吗？

我在想这样的事情：要同时搜索两个顶点，如果我发现相等的输入和输出顶点以打印它们，依此类推，所以这将是实际的蛮力，但是如何使用递归来做到这一点？
最好的解决方案是什么？

Answer 1

这是我想出的一个递归解决方案。

想象一下，我们删除了除两个顶点以外的所有顶点（与两个顶点无关）。

在您的示例中，假设我们删除了除a和b之外的所有顶点。请注意，当且仅当存在从a到b的边，并且存在从b到a的边时，a和b是等价的。这是我们的基本情况。

想象一下，我们一个接一个地添加缺失的顶点（顺序无关紧要）。我们需要考虑两种情况。 i）我们需要检查在添加顶点时是否有任何一组顶点相等。 ii）我们需要检查是否有任何等效的顶点集仍然相等。

情况1。

在您的示例中，假定我们添加了c（回想起我们从顶点a和b开始）。我们肯定知道a和b仍然不相等。为什么？因为a缺少出站顶点b，而该出站顶点不是c，因为c不在图形上。因此，我们只需要检查是否存在任何等于c的顶点。我们只需检查c的输出顶点的传入顶点和c的输入顶点的传出顶点，便可以有效地做到这一点。然后，我们发现a和c是等价的。

注意：我使用=符号表示帖子其余部分的顶点相等性。

更笼统地说，每当我们在图上添加一个新顶点（比如说z）时，我们就知道不存在一对顶点（比如说x和y），这样x！= y在添加z之前，x = y在添加z之后。这是因为：

假设x具有传出或传入的顶点w，而y没有不失一般性。我们知道w！= z，因为我们还没有加z。然后，在我们加上z之后，y仍会遗漏顶点w。因此，在添加顶点z之后，x！= y。因此，我们仅需要检查是否存在与z相等的顶点。

情况二

这种情况要简单得多。在您的示例中，假设我们最终添加了d，（请注意，我们之前添加了顶点a，b和c）。我们已经计算出a和c是等效的，在添加d之后，我们需要检查它们是否仍然等效。注意，我们需要做的只是检查a和c是否都将d作为传出或传入顶点。并比较它们。



因此，总而言之，我们从两个任意顶点开始，并检查它们是否相等。此后，我们将每个顶点一个接一个地添加，并如上所述检查情况1和情况2。

因此，假设您有一个递归函数EQ（n），该函数返回所有等效的顶点。然后，给定一个具有n个顶点的图，您称EQ（n-1），即缺少一个顶点（比如说z）。然后检查案例1和案例2，以了解z如何影响整体解决方案。在开始的情况下，您有n = 2，就像我在一开始提到的那样。

因此，算法的运行时间为递归T（2）= O（1）和T（n）= T（n-1）+ O（n）。因此，运行时间为O（n ^ 2）。