求矩阵中连通集总数的算法

Question

我想知道我应该在这里应用哪种算法。会 DFS做什么？

给定一个二维矩阵。找出该矩阵中连通集的总数。

连通集可以定义为一组单元格，其中提到了 1 个单元格，并且在该集合中至少有一个其他单元格与它们共享邻居关系。一个单元格中有 1 并且周围没有邻居有 1 可以被认为是一个集合中有一个单元格。邻居可以定义为在 8 个可能方向(即 N、W、E、S、NE、NW、SE、SW 方向)上与给定单元格相邻的所有单元格。一个细胞不是它自己的邻居。

例如:

1 0 0 1

0 0 1 0

0 0 1 0

1 0 0 1

连通集数为3

0 0 1 0 0 1 0 0

1 0 0 0 0 0 0 1

0 0 1 0 0 1 0 1

0 1 0 0 0 1 0 0

1 0 0 0 0 0 0 0

0 0 1 1 0 1 1 0

1 0 1 1 0 1 1 0

0 0 0 0 0 0 0 0

连通集数为9。

Answer 1

我认为您不需要将其视为一般图形问题并应用任何算法，例如 BFS或 DFS .

您需要对矩阵进行三次扫描。

扫描 1:

从头开始

1. 给每个数字 1 和 1..n，在你的例子中，第一行在该步骤之后看起来像

   1 0 0 2

2. 转到下一行，对行中的每一个 1 检查您左边的邻居是否为非 0
   • 如果非0取左边的值
   • 如果 0 检查上一行中的非 0 邻居并取最左边的值
   • 如果所有这些都是 0，则只需将 1 加到目前给定的最大数上
3. 重复 2 直到处理完最后一行

你的例子应该如下所示

1 0 0 2
0 0 2 0
0 0 2 0
3 0 0 2

扫描 2:

从底部开始检查每个邻居是否与最左边的邻居具有相同的编号以及与其下方行中的邻居具有相同的编号

基本上如果你有这样的矩阵

1 0 2

1 0 2

0 1 0

检查确保一组确实有相同的数字

扫描 3:

计算矩阵中唯一非0条目的数量