如何将复杂度较低的数组中的相似元素分组？

Question

假设我们有一个矩形阵列，其整数值是这样的：

A = [[1,1,2,2,2], 
    [1,2,2,2,1], 
    [1,3,3,3,1]] 

如何基团，其彼此连接到不同群集相同的整数值？簇大小为未知。

所需的输出（其彼此连接相同的整数的不同的簇）：

Group 1 : A[0,0],A[0,1],A[1,0],A[2,0] 
Group 2 : A[0,2],A[0,3],A[0,4],A[1,1],A[1,2],A[1,3] 
Group 3 : A[1,4],A[2,4] 
Group 4 : A[2,1],A[2,2],A[2,3] 

哪个做同样的最适合的算法。 这个问题可以使用机器学习吗？

Answer 1

任何图搜索算法（BFS或DFS）都可以。

图的顶点是矩阵的元素，并且相邻元素之间存在边，所以每个顶点都有2到4个邻居。

创建一个相同大小的辅助矩阵，该矩阵将存储每个元素的聚类数量，以及某些其他值（例如-1），用于尚未处于任何聚类中的元素。 现在，要获得聚类，请遍历矩阵的所有元素。 当您找到一个尚未存在于任何集群中的元素时，从其中运行BFS或DFS以查找其等值连接的组件，并用辅助矩阵中的所有这些值标记新集群的编号。

复杂度为O（元素数），与读取或写入矩阵相同。