查找矩阵中连通集总数的算法

Question

我想知道我应该在这里应用哪种算法.将一个DFS吗？

给定一个二维矩阵.查找该矩阵中已连接集的总数.

连接集可以被定义为其上具有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条目的数量

Answer 2

扫描矩阵1s。当你找到一个时，调用一个递归函数，如果它尚未被识别为在一个中，则将其标记为连接的组件。使用递归来查找连接的组件。快速查找某处，告诉您给定节点是否已被识别为位于连接组件中，以避免识别连接组件 2x，并避免在遍历连接组件时出现无限循环。