ruby - Ruby 中的这种拓扑排序有缺陷吗？

Question

我在看拓扑排序，感觉很复杂。我想出了这个，它似乎适用于我能找到的所有示例。这个逻辑有问题吗？

@tsort_array = []
def tsort item, dependencies_array
  if index = @tsort_array.index(item)
    @tsort_array = @tsort_array.insert(index, dependencies_array).flatten
  else
    @tsort_array += dependencies_array
    @tsort_array << item
  end

  @tsort_array = @tsort_array.uniq
end

使用 http://ruby-doc.org/stdlib-1.9.3/libdoc/tsort/rdoc/TSort.html 中的示例有相同的结果。

>> tsort 1, [2,3]
=> [2, 3, 1]
>> tsort 2, [3]
=> [3, 2, 1]
>> tsort 3, []
=> [3, 2, 1]
>> tsort 4, []
=> [3, 2, 1, 4]

Answer 1

这是一个有趣的想法，但不幸的是该算法存在一些缺陷。

首先，让我们总结一下算法，以确保我们有一个共同的理解:有一个全局数组tsort_array。 tsort 方法将一个顶点 item 和一个包含 item 依赖关系的数组 dependencies_array 作为输入(意味着顶点必须在拓扑排序中位于顶点 item 之前)。然后该方法将检查 item 是否已存在于 tsort_array 中。如果是这样，item 的依赖项将直接插入到 item 之前。如果不是，则将依赖项附加到 tsort_array 的末尾，然后再附加 item。最后，tsort_array 扫描重复项，仅保留每个顶点的第一次出现。在每次调用 tsort 之后，到目前为止添加的图的拓扑顺序应该包含在 tsort_array 中。

如果每个添加的 item 到目前为止都没有被添加到 tsort_array(意味着每次调用 tsort 都命中 其他案例)。但是，这需要按拓扑顺序添加顶点(即之前添加的顶点不依赖于当前 item)。因此，您必须已经知道拓扑顺序才能以这种方式添加顶点。

算法在以下情况下会出现错误:

• 算法不检测循环:

  

  > tsort 2, [1]
  => [1, 2]
  > tsort 3, [2]
  => [1, 2, 3]
  > tsort 1, [3]
  => [3, 1, 2]
  

  这当然不是一个有效的拓扑排序，但算法并没有指出任何错误。如果假设算法的输入图始终是非循环的，这很好。

• 如果顶点的依赖项是递增添加的，则算法不会正确运行:

  

   tsort 1, []
   => [1]
   tsort 3, [2]
   => [1, 2, 3]
   tsort 1, [3]
   => [3, 1, 2]
  

  该示例最初添加了没有依赖项的 1。然后 3 添加了对 2 的依赖。这两个顶点将插入到 1 之后。最后，1 更新为 3 的依赖项。这会将 3 移动到 1 之前，因此移动到它对 2 的依赖之前。

  如果假设不会发生此类更新，这很好，即顶点的依赖关系将始终在对 tsort 的一次调用中指定。

• 以下示例排序不正确:

  

  > tsort 4, [2,3]
  => [2, 3, 4]
  > tsort 3, [1]
  => [2, 1, 3, 4]
  > tsort 2, [3]
  => [3, 2, 1, 4]
  

  通过按照2,3的顺序指定4的依赖，然后添加依赖1 -> 3，顶点1 将被插入到 2 和 3 之间，因此在 2 之后和 3 之前。因此，2 在此步骤之后位于列表的开头。最后，添加依赖项 3 -> 2 会将 3 放在 2 之前。因此，3 将位于列表的开头，因此在它对 1 的依赖之前。