在Python中对图像实现Kruskal算法

Question

一个网格用两个数组来定义一幅图像的边：

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

我正在尝试实现克鲁斯卡尔算法。这其实比较简单——我可以在网上找到现成的实现代码并复制过来。不过，处理边的部分让我感到困惑，特别是排序这一步。

有没有更好的方法来存储这些边，特别是针对这个问题？我希望能从每个像素到相邻的像素。我的图像是存储在 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)