algorithm - Tarjan 找到强连通分量后折叠顶点

Question

假设在一个圆圈图中有许多具有某个值的顶点。

在使用Tarjan找出这些SCC之后，我想将每个整个SCC变成两个顶点（不是一个），一个在这个SCC的这些顶点中具有最高值，另一个具有最低值。

让连接到这个SCC的那些顶点指向具有最低值的顶点，并且让从SCC指向的顶点指向具有最高值的顶点。

也就是说，像 1(4) -> 2(3) <-> 3(5) -> 5(1) <-> 4(6) -> 1(4)，括号中的权重，是一个圆圈。我想把它翻译成类似的东西1(4) -> 2(3) -> 3(5) -> 4(1) -> 5(6) , 1(4) -> 4(1)

但我不知道如何实现这一点，请帮忙。

我正在使用 C 和邻接列表来存储图形。

对不起英语不好，我希望它足够清楚，可以理解。

Answer 1

以下想法应该可以帮助您入门：

• 用 表示原始图，用 表示Gscc 集，用S表示互连 scc 的新图SG。
• 您需要 vertices 到 scc 的映射scc: V(G) -> S，以及 sccs 到 min 和 max valued vertices的映射min/max: S -> V(G)，这可以在 tarjan scc 构建期间构建。
• 将顶点设置SG为最小/最大的图像。
• 之后，您将 SG通过迭代所有边缘(u,v)来为每个边缘E(G)创建边缘(max(scc(u)),min(scc(v)))，E(SG)除非它已经存在。
• 对于每个 scc添加s到.S(min(S), max(S))E(SG)

您可能需要考虑如何解决 scc 中的 max-/min-valuesd 节点之间的关系。