1

我有一个成对的向量，表示节点之间的跃点，当有周期时我想折叠它（如在一个周期中的跃点之间的总时间中将其显示为一个）。因此，例如，路径 A --> B --> C --> D --> B --> C --> D --> E 遍历子路径 B--> C --> D 两次，所以在我的结构中，我会有类似的东西：

(A,B,1)(B,C,3)(C,D,2)(D,B,4)(B,C,5)(C,D,8)(D,E,6)

理想情况下，我会简化为：

(A,B,1)(B,C,3+5)(C,D,2+8)(D,E,6)

还存储从 D 到 B 的 4（环回边缘时间）以单独聚合，并能够以浓缩方式显示 B --> C --> D（所有的聚合边缘时间和聚合的环回时间D-->B 实例以及我们循环的次数）

我该怎么办？

4

2 回答 2

1

我会选择后缀数组或后缀树。只需生成标记（在本例中为 (from, to) ）并将其放入后缀数组或后缀树中。然后你可以得到对。简单但不高效的方式：

产生令牌，产生这个令牌流的所有后缀。对它们进行排序。然后您在该排序列表中的所有常见子序列彼此靠近（令牌流长度 - 令牌流后缀长度 = 位置） 例如，您可以使用快速排序进行排序，或者您只是寻找后缀数组的实现。后缀数组可以在O(n)和O(n)空间中构建。并且可以在O(n+k)中找到最大对/重复（这就是你想要的） （其中 n = tokennumber，并且 k = 你列表中的循环）

也许这会有所帮助。然后你可以生成一个令牌流，如：ABCDBCDE

快速而肮脏的解决方案就在这里

于 2012-06-25T19:24:14.937 回答
1

基本上，您通过路径，并将每个边缘（ (A, B), 1 ）存储在 a 中map，并将所有发现的节点存储在 aset

  • 每当您遇到目标点为已发现节点的边时，您就知道它是环回边。

  • 每当您遇到相同的优势时，将其价值加起来map

于 2012-06-25T23:52:44.507 回答