任意点网格的拓扑排序？

Question

我有一组坐标点x,y，从一个点可以到达一个立即可见的点，只要新点的x或y大于当前点。那么如何对此进行拓扑排序？

- MyNameIsKhan

---

为什么您不能只是采用拓扑排序算法并将其适应于您的特定情况？ - Oliver Charlesworth

尝试理解如何进行适应。我手头只有一组点的数组x，y。 - MyNameIsKhan

好的，哪一部分让你遇到了问题？ - Oliver Charlesworth

确定连接点，适当的数据结构，以及在我的情况下最终结果应该是什么。 - MyNameIsKhan

Answer 1

这个网格有大量的拓扑排序方式。然而，其中一些排序方式非常容易计算且不需要额外的空间开销：

1. 从下往上、从左往右遍历每一行。
2. 从左往右、从下往上遍历每一列。
3. 列出所有x和y的和为零的点，然后是x和y的和为1的点，以此类推。

希望这能帮到你！

- templatetypedef

---

那么如果我有这些点 (0,0) (1,99) (9,16) (16,9) (36,64) (64,36) (100,100) 呢？ - MyNameIsKhan

@AgainstASicilian- 哦，抱歉 - 我误解了你的问题。我以为你有一个 n x m 的网格，包含矩形中所有点，而不是需要考虑的所有点的显式列表。我建议你更新你的问题，让它更清晰 - “点阵”通常意味着一个完整的矩形。 - templatetypedef

Answer 2

因为这是一种传递关系（即如果您可以从a到b，b到c，那么您必须能够从a到c），所以您可以简单地对点进行排序以实现拓扑排序。

例如，此C代码将通过根据第一个坐标或者如果第一个坐标匹配则根据第二个坐标来排序点的数组来执行拓扑排序。

int C[1000][2];

int compar(const void*a,const void*b)
{
  int *a2=(int*)a;
  int *b2=(int*)b;
  int d=a2[0]-b2[0];
  if (d)
    return d;  // Sort on first coordinate
  return a2[1]-b2[1];  // Sort on second coordinate
}

...
qsort(C,1000,sizeof(int)*2,compar);
...

对于您的示例 (0,0) (1,99) (9,16) (16,9) (36,64) (64,36) (100,100)，这些点已经按照第一个坐标进行排序，因此这将是调用qsort的输出。

这种方法之所以有效，是因为如果您可以从a到b，则a必须具有较小的x（因此在列表中较早出现），或者具有相同的x和较小的y（并且再次出现在排序列表中较早的位置）。

- Peter de Rivaz

---

如果我从a到c的路上必须经过b，那么我就不能说我可以直接从a到c。 - MyNameIsKhan

你是对的。我误读了问题，认为需要x和y都大于或等于。然而，如果这不是正确的阅读方式，那么就不可能有拓扑排序，因为你可以从(9,16)到(16,9)(更大的x)，从(16,9)到(9,16)(更大的y)，所以图中包含循环。 - Peter de Rivaz