algorithm - 任意点网格的拓扑排序？

Question

我有一个点 x,y 网格，只要新点具有更大的 x、y 或两者，您就可以从一个点移动到立即可见的点。我将如何对它进行拓扑排序？

Answer 1

这个网格有大量的拓扑排序。但是，其中一些非常容易计算，没有任何空间开销：

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

希望这可以帮助！

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（并且再次出现在排序列表中的前面）。