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

Question

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

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

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

有没有更好的方法来专门存储这个拍摄的边缘？我希望它们从每个像素到相邻像素。我将图像存储为 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)