如何在图中找到所有等价顶点？
How to find all equivalent vertices in graph?
等价顶点是指具有相同 'ingoing' 和 'outgoing' 顶点的顶点。
有人可以帮助我如何处理算法吗？
我在想这样的事情： 同时搜索两个顶点，如果我找到相等的传入和传出顶点打印它们..等等，等等这将是实际的蛮力，但是如何使用递归来做到这一点？
什么是最好的解决方案？
一种方法是向每个顶点添加列表，一个用于传入顶点，List ingoingVertices，一个用于传出顶点，List outgoingVertices。然后遍历每个顶点的边，将访问的顶点添加到第一个顶点内的 List outgoingVertices，每次从第一个顶点取出一条边时，将第一个顶点添加到访问顶点的 List ingoingEdges .然后遍历顶点检查两个顶点之间的列表是否相同以找到它们的等价性。
递归访问每个顶点然后执行该顶点与遍历每个顶点大致相同。暴力破解一次只比较两个顶点是可行的，但在运行时需要更多的代码和时间。
这是我想出的递归解决方案。
假设我们删除了除两个顶点之外的所有顶点（哪两个无关紧要）。
在您的示例中，假设我们删除了除 a 和 b 之外的所有顶点。请注意 a 和 b 等价当且仅当存在从 a 到 b，从b到a有一条边。这是我们的基本案例。
假设我们一个一个地添加缺失的顶点（顺序无关紧要）。我们需要考虑两种情况。 i) 我们需要检查添加顶点时是否有任何一组顶点变得等价。 ii) 我们需要检查任何一组等价的顶点是否仍然等价。
案例一
在您的示例中，假设我们添加了 c，（回想一下我们从顶点 a 和 b).我们肯定知道 a 和 b 仍然不等价。为什么？因为，a 有一个 b 缺失的输出顶点，而那个输出顶点不是 c，因为 c 之前不在图表上。因此，我们只需要检查是否有任何顶点等同于c。我们可以简单地通过检查 c 的输出顶点的输入顶点和 c 的输入顶点的输出顶点来高效地完成它。然后，我们发现 a 和 c 是等价的
注：我用=符号来表示post的其余部分顶点相等。
更一般地说，每当我们向图中添加一个新顶点（假设 z）时，我们就知道不存在一对顶点，（假设 x 和 y），使得 x != y 在我们添加 z，加上z后x = y。这是因为：
假设 x 有一个输出或输入顶点 w 而 y 没有具有不失一般性。我们知道 w != z 因为我们还没有添加 z。那么，在我们添加z之后，y仍然遗漏顶点w。因此，在我们添加顶点z之后，x != y。所以我们只需要检查是否有任何顶点等同于 z.
案例二
这个案例就简单多了。在您的示例中，假设我们最终添加了 d，（回想一下我们添加了顶点 a、b和 c 之前）。我们已经计算出 a 和 c 是等价的，我们需要在添加 d[ 之后检查它们是否仍然等价=109=]。请注意，我们需要做的就是检查 a 和 c 是否都有 d 作为传出或传入顶点。并比较它们。
所以，总而言之，我们从任意两个顶点开始，检查它们是否等价。此后，我们逐一添加每个顶点，并检查 case 1 和 case 2 如上所述。
因此，假设您有一个递归函数 EQ(n) returns 所有等效顶点。然后，给定一个包含 n 个顶点的图，您调用 EQ(n-1)，即缺少一个顶点（假设 z)。然后检查 case 1 和 case 2 以了解 z 如何影响整体解决方案。在你的基本情况下，你有 n = 2，正如我在开头提到的那样。
所以算法的 运行 时间作为这个递归给出 T(2) = O(1) 和 T(n) = T(n - 1) + O(n)。因此，运行时间为O(n^2).
等价顶点是指具有相同 'ingoing' 和 'outgoing' 顶点的顶点。
有人可以帮助我如何处理算法吗？
我在想这样的事情： 同时搜索两个顶点，如果我找到相等的传入和传出顶点打印它们..等等，等等这将是实际的蛮力，但是如何使用递归来做到这一点？ 什么是最好的解决方案？
一种方法是向每个顶点添加列表，一个用于传入顶点，List ingoingVertices，一个用于传出顶点，List outgoingVertices。然后遍历每个顶点的边，将访问的顶点添加到第一个顶点内的 List outgoingVertices，每次从第一个顶点取出一条边时，将第一个顶点添加到访问顶点的 List ingoingEdges .然后遍历顶点检查两个顶点之间的列表是否相同以找到它们的等价性。
递归访问每个顶点然后执行该顶点与遍历每个顶点大致相同。暴力破解一次只比较两个顶点是可行的，但在运行时需要更多的代码和时间。
这是我想出的递归解决方案。
假设我们删除了除两个顶点之外的所有顶点（哪两个无关紧要）。
在您的示例中，假设我们删除了除 a 和 b 之外的所有顶点。请注意 a 和 b 等价当且仅当存在从 a 到 b，从b到a有一条边。这是我们的基本案例。
假设我们一个一个地添加缺失的顶点（顺序无关紧要）。我们需要考虑两种情况。 i) 我们需要检查添加顶点时是否有任何一组顶点变得等价。 ii) 我们需要检查任何一组等价的顶点是否仍然等价。
案例一
在您的示例中，假设我们添加了 c，（回想一下我们从顶点 a 和 b).我们肯定知道 a 和 b 仍然不等价。为什么？因为，a 有一个 b 缺失的输出顶点，而那个输出顶点不是 c，因为 c 之前不在图表上。因此，我们只需要检查是否有任何顶点等同于c。我们可以简单地通过检查 c 的输出顶点的输入顶点和 c 的输入顶点的输出顶点来高效地完成它。然后，我们发现 a 和 c 是等价的
注：我用=符号来表示post的其余部分顶点相等。
更一般地说，每当我们向图中添加一个新顶点（假设 z）时，我们就知道不存在一对顶点，（假设 x 和 y），使得 x != y 在我们添加 z，加上z后x = y。这是因为：
假设 x 有一个输出或输入顶点 w 而 y 没有具有不失一般性。我们知道 w != z 因为我们还没有添加 z。那么，在我们添加z之后，y仍然遗漏顶点w。因此，在我们添加顶点z之后，x != y。所以我们只需要检查是否有任何顶点等同于 z.
案例二
这个案例就简单多了。在您的示例中，假设我们最终添加了 d，（回想一下我们添加了顶点 a、b和 c 之前）。我们已经计算出 a 和 c 是等价的，我们需要在添加 d[ 之后检查它们是否仍然等价=109=]。请注意，我们需要做的就是检查 a 和 c 是否都有 d 作为传出或传入顶点。并比较它们。
所以，总而言之，我们从任意两个顶点开始，检查它们是否等价。此后，我们逐一添加每个顶点，并检查 case 1 和 case 2 如上所述。
因此，假设您有一个递归函数 EQ(n) returns 所有等效顶点。然后，给定一个包含 n 个顶点的图，您调用 EQ(n-1)，即缺少一个顶点（假设 z)。然后检查 case 1 和 case 2 以了解 z 如何影响整体解决方案。在你的基本情况下，你有 n = 2，正如我在开头提到的那样。
所以算法的 运行 时间作为这个递归给出 T(2) = O(1) 和 T(n) = T(n - 1) + O(n)。因此，运行时间为O(n^2).