如何將複雜度較低的數組中的相似元素分組？

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（元素數），與讀取或寫入矩陣相同。