3

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

@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]
4

1 回答 1

1

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

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

item如果到目前为止还没有添加每个添加的算法tsort_array（这意味着每次调用都tsort命中else案例），则该算法将正常工作。但是，这需要按拓扑顺序添加顶点（即，以前添加的顶点不依赖于当前的item）。因此，您必须知道以这种方式添加顶点的拓扑顺序。

该算法将在以下情况下表现不正确：

  • 该算法不检测循环：

    示例 1：循环图

    > 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]

    通过4在 order 中指定依赖关系，2,3然后添加依赖关系1 -> 3，顶点1将插入到 and 之间2，3因此 after2和 before 3。因此，2是在此步骤之后的列表的开头。最后，添加依赖3 -> 2会放在3前面2。因此，3将位于列表的开头，因此在其依赖于1.

于 2020-12-09T23:55:50.820 回答