0

我目前正在做一个项目，我需要找出图中存在多少强连通分量（SCC），然后，我需要检查是否有任何边从任何 SCC 到另一个 SCC。

我正在使用 Tarjan 的算法，我已经可以从给定的图表中获取所有 SCC，但我无法计算下一部分。

我有两个想法：

  1. 删除每个 SCC 内的所有边。唯一剩下的将是可能的候选人。
  2. 不知何故，将每个 SCC 变成一个“顶点”或一个超级顶点，然后检查是否有到任何其他超级顶点的传出连接。

我唯一的限制是：

  • 如果同一个 SCC 有多个连接，我只需要显示一次；

  • 当我显示连接时，我需要始终显示属于 SCC 的最小顶点 id，无论是传出 SCC 还是传入 SCC。

一个小例子：

输入作为从 x 到 y 的边

1 2; 2 3; 3 1; 2 4; 4 5; 5 4;

这是上图的图像，其中 1 = A，2 = B 等等......

我的问题是：我如何计算这个？我似乎想出的每一个选择，似乎都太耗费时间和资源了。

感谢所有帮助:)

4

0 回答 0