已知數的2D陣列，找到簇

Question

鑑於2D陣列，例如：

集羣

0 0 0 0 0 
0 2 3 0 1 
0 8 5 0 7 
7 0 0 0 4 

輸出應該是基團：

羣集1：<2,3,8,5,7>

羣集2：<1,7,4>

Answer 1

一種方法是使用圖形。以某種順序遍歷矩陣（我從左到右，從上到下）。當遇到非零元素時，將其添加到圖形中。然後檢查它的所有鄰居（看起來你想要8個連接的鄰居），並且對於每個非零的節點，將其節點添加到圖中，並將其連接到當前元素。圖表中的元素可能需要跟蹤其座標，以便您可以查看是否添加了重複。當你遍歷矩陣時，你有一個包含一組聚類的圖。集羣應該是連接元素的子圖。

Answer 2

你的問題似乎是找到連接的組件。您應該使用遍歷方法（BFS或DFS將完成這項工作）。遍歷所有元素，爲每個非零元素開始遍歷並記錄在該遍歷中看到的所有元素，並將每個訪問元素都變爲零。像下面的代碼：

void DFS(int x, int y) 
{ 
    printf("%d ", g[x][y]); 
    g[x][y] = 0; 
    // iterate over neighbours 
    for(dx=-1; dx<=1; dx++) 
    for(dy=-1; dy<=1; dy++) 
     if (g[x+dx][y+dy]) DFS(x+dx, y+dy); 
} 

for(i=0; i<n; i++) 
    for(j=0; j<n; j++) 
    if (g[i][j]) 
    { 
     DFS(i, j); 
     printf("\n"); 
    } 

Answer 3

如果您知道組的數量或希望您的數據代入組的靜態數量，你可以做K-均值。

http://en.wikipedia.org/wiki/K-means_clustering

Answer 4

你想要做Connected Component Labeling。這通常被認爲是一種圖像處理算法，但它與您所描述的相符。

您也將獲得的K-手段的建議，因爲你說的數字的二維數組，這是很容易理解，作爲陣列2D數字的。 K-means在平面中查找點集羣，而不是像您請求的那樣在二維數組中連接組。

Answer 5

代碼示例：

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace Practice 
{ 
    class Program 
    { 
     static void Main() 
     { 
      var matrix = new[] { new StringBuilder("00000"), new StringBuilder("02301"), new StringBuilder("08507"), new StringBuilder("70004") }; 
      var clusters = 0; 
      for (var i = 0; i < matrix.Length; i++) 
       for (var j = 0; j < (matrix.Any() ? matrix[i].Length : 0); j++) 
        if (matrix[i][j] != '0') 
        { 
         Console.Write("Cluster {0}: <", ++clusters); 
         var cluster = new List<char>(); 
         Traverse(matrix, i, j, ref cluster); 
         Console.WriteLine("{0}>", string.Join(",", cluster)); 
        } 
      Console.ReadKey(); 
     } 

     private static void Traverse(StringBuilder[] matrix, int row, int col, ref List<char> cluster) 
     { 
      cluster.Add(matrix[row][col]); 
      matrix[row][col] = '0'; 
      for (var i = -1; i <= 1 && row + i >= 0 && row + i < matrix.Length; i++) 
       for (var j = -1; j <= 1 && col + j >= 0 && col + j < (matrix.Any() ? matrix[row + i].Length : 0); j++) 
        if(matrix[row + i][col + j] != '0') 
         Traverse(matrix, row + i, col + j, ref cluster); 
     } 
    } 
} 

算法的解釋：

• 對於每一行：
  • 對於該行中的每一列：
    • 如果該項目是一個未訪問過的非零：
      1. 保存找到的集羣成員;
      2. 將[row，column]的位置標記爲visited;而留在界矩陣的
      3. 檢查任何未訪問的非零鄰居：
         • [行 - 1，列 - 1];
         • [row - 1，column];
         • [row - 1，column + 1];
         • [row，column - 1];
         • [row，column + 1];
         • [row + 1，column - 1];
         • [row + 1，column];
         • [row + 1，column + 1]。
      4. 如果任何鄰居是未訪問的非零重複步驟1-4遞歸直到所有鄰居被訪問零（已找到所有集羣成員）。