在Python中实现Kruskal算法处理图像

Question

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

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

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

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

- eha

---

将数组存储为原样有什么问题吗？您能解释一下您遇到的缺点，以便我们可以尝试找到解决方案来解决它吗？ - templatetypedef

考虑使用networkx。http://networkx.lanl.gov/_modules/networkx/algorithms/mst.html。但是，对于您的问题，您可以将容器实现为元组（源，目标，成本）或类、字典、命名元组... 然后按成本对这些列表进行排序，并添加到您的并查集数据结构中（确保使用路径压缩和按秩合并），一旦源和目标没有相同的代表即可。 - jassinm

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)

- Spatarel