1

像列表形式的图表：

1 : 2 -> 3
2 : 3 -> 4 -> 1
3 : 2 -> 1 -> 4
4 : 3 -> 2

whew 1 : 2 -> 3 表示节点 1 连接到节点 2 和 3。

所以输出应该是每个节点列表排序：

1 : 2 -> 3
2 : 1 -> 3 -> 4
3 : 1 -> 2 -> 4
4 : 2 -> 3

因此，这可以通过对每个列表进行排序在 n * O(log n) 时间内完成，但是对于这个问题的最佳算法是什么？

4

1 回答 1

1

对所有单独的列表进行排序将是获得所需内容的最简单方法。但是，如果您有 n 个节点，则必须对 n 个列表进行排序。每个列表可以有 n-1 个条目。对 n-1 个条目的 1 个列表进行排序将具有复杂性 O(n*log(n))。您的总复杂度为 O(n²*log(n))。

您可以尝试通过按顺序对列表进行排序并利用该信息来解决此问题。从您的示例中，我假设您的图是无向的，这允许进行以下优化。

先举个例子：

  1. 您首先对第一个列表进行排序，这将产生 2->3。然后你的第一个列表就完成了。然后，您可以将“1”添加到节点 2 和 3 的列表中（因为 1 将作为第一项出现在它们的列表中）。这将为您提供这些列表的开始。然后您转到节点 2 的列表。
  2. 看到您已经知道它的开始 (1)，您可以在排序期间跳过所有该节点。您可以快速浏览您的链接列表并从集合中删除 1。然后你对其余的进行排序（这将给出 3->4）并将其附加到你已经拥有的 1 上。与 1 一样，您现在拥有 2 的完整排序列表，您可以将“2”添加到 3 和 4 的列表中。
  3. 然后您继续执行 3，快速通过以删除您已经知道的所有节点，并对其余节点进行排序。这将为您提供 4，然后将其附加到您已经获得的 1->2->4 中。将 3 添加到节点 4 的列表中。
  4. 节点 4 的列表已经完成，因为列表中没有 id > 4 的节点。

更正式地说：

initialize the final sorted list of every node to null;
for(i=1;i<=nrNodes;i++){
    remove all nodes with id<i from linked list;
    A:=sort remainder of list
    append A to the final sorted list of i;
    for (every node n in A){
        append i to final sorted list of node n
    }
}

这应该比顺序排序所有列表更快，因为要排序的列表更小。

于 2012-10-18T08:51:05.267 回答