algorithm - 带约束的强连通分量

Question

我遇到了一个类似这样的问题。

我们得到一个无向图，其中每条边都有一个值。现在额外的限制是不能从较高价值的边缘移动到较低价值的边缘。一个人总是必须从较低的价值转向较高的价值。

从图形上看，问题可以描述为

                                   1
                               1 /   \ 1
                                /     \
                               3       7
                            2 / \  3   
                             /   \
                            4     5

所以在这里我们可以从 7 -> 1 -> 3 -> 4 移动，但不能从 4 -> 3 -> 1 移动。所以在这个图中，我们被要求在这里找出像 (1, 3, 7) 这样的强连通分量.

---

我曾尝试将 Kosaraju 算法与这样的约束一起使用。

for v in adj[u]:
    if not visited[v] and v.edgeValue >= u.edgeValue:
        do work here

但我认为逻辑是错误的，我无法找出它失败的地方。有人可以指出错误并显示某种伪代码吗？

谢谢你。

Answer 1

好吧，在您的限制下，您允许的方向取决于您的旅行历史。这使得连接的组件有一点不同的含义。我假设强连通分量是指对于来自任何顶点的子图，可以到达该子图的任何其他顶点。由于您的约束指定您不能从较低值的边移动到较高的值，这意味着任何强连接的子图都包含具有相等加权边的树。

因此，在上面的示例中，您将 (4,3)(3,5)(3,1,7) 作为图形的一个特定分区，分成强分量。你可以通过做一个简单的 DFS 或 BFS 来获得这些，同时只包括特定权重的边缘。