python - 在图像上用 Python 实现 Kruskal 算法

Question

网格使用存储在两个数组中的边定义图像:

• h[x][y] 给出从 x,y 到 x+1,y
的边权重
• v[x][y] 给出从 x,y 到 x,y+1
的边权重

我正在尝试实现 Kruskal 算法。这相当简单——我可以找到 implementations online并复制它们。问题是处理边缘。具体来说;对它们进行排序很困惑。

有没有更好的方法来专门为这个镜头存储边缘？我希望它们从每个像素到相邻像素。我将图像存储为 i[x][y]，边缘权重只是图像值之间的差异。

Answer 1

您需要做的是创建所有边的列表，然后对它们进行排序。为此，您需要定义一个类 Edge:

class Edge:
    def x
    def y
    def direction
    def weight

然后，解析h 和v 矩阵并构建edges 列表。最后，它应该有 2 * N * M 元素。边的方向应该是 'h' 或 'v'，具体取决于您解析的矩阵。

如果您不将 h 和 v 矩阵用于任何其他目的，您可以完全放弃它们，因为您可以直接从计算边的权重i 矩阵。

最后，为了算法的目的，您需要使用权重作为标准对列表进行排序:

edges.sort(key=weight)