0

令 G=(V,E) 为有向图，k 为整数。我需要在线性时间内找到顶点组，以便该组中的每个顶点都可以恰好到达 k 个顶点（包括它自己）。

我想到的第一件事是使用 Kosaraju 的算法来找到图的强连通分量。连通分量内的每个顶点显然至少可以到达该连通分量中的顶点，所以剩下的就是看分量是如何连接的。但是，我没有提出线性解决方案。

有什么提示吗？

谢谢。

4

2 回答 2

1

你的第一步是正确的。每个强连接的组件都可以用一个顶点替换，其中起始的可达顶点数是该组件中的元素数。代入运算后得到有向无环图。现在对于这些超级顶点中的每一个，我们想找出可以从它到达多少个顶点。一个想法是对这个图进行拓扑排序。在此操作之后，所有箭头都指向一个方向。不失一般性，我们可以假设它们指向右边，所以我们的图表或多或少看起来像这样：

a -> b ----> e -> f -> g
  \             /
    -> c -> d -

对于每个顶点，我们都有它的起始计数器，这是我们从一个强连接组件组装顶点的第一阶段获得的。我们现在想做的是从右到左，每个顶点都有一组可以从它到达的顶点。我们需要的操作是快速合并这些集合。Find-Union 数据结构提供了帮助。您可以在通常情况下再添加一个字段size，rank该字段将存储可到达顶点的数量，并在union两组时更新它。

这将导致几乎线性的时间：阿克曼函数O(n * alpha(n))的alpha(n)倒数是非常非常小的。对于大数据，它不会大于5，因此您可以将其视为常数。

我想知道是否有人可以在没有alpha.

于 2013-04-21T17:53:25.500 回答
0

我认为第一个答案是不正确的。您可能能够从 scc 图中的儿子的可达性的联合中为每个节点创建可达的节点组，但是您需要制作儿子的组的副本才能做到这一点（否则你会弄乱他们的可达性）。因此，如果我没记错的话，复杂度是 n*n 最小值，或者实际上是 n * E。那是因为需要在 * 联合操作之前制作副本，所以你需要为每个节点遍历 n*(num of sons) ..这的复杂性是 n*E + n(alpha(n)) . 因此使用联合查找是完全多余的。您可以为每个节点使用 n 大小的数组。

于 2016-07-09T09:45:08.970 回答