logo标签列表

在一个矩阵中查找连接集合的总数的算法

algorithmgraphgraph-theory
10

我想知道在这里应该使用哪种算法。使用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。

11个回答
7

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

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

扫描1：

从顶部开始

  1. 使用1..n为每个数字分配1，例如，在您的示例中，第一行在此步骤后将如下所示：

    1 0 0 2

  2. 进入下一行，对于行中的每个1，检查左侧的邻居是否为非零
    • 如果是非零，则采用左侧的值
    • 如果是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：

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

有人可以解释一下Scan 1的第二步吗？ - user2979190
3
相比其他答案，我发现这篇文章易于阅读和实现。谢谢！ - PolyMesh
2

Python实现，更易理解的代码：

# sea is 2 D array of 0 and 1s we have to find 1's group surrounded by 0's
def dfs(sea, i, j, b, h, visited):
    surround = ((-1, -1), (0, -1), (1, -1),
                (-1, 0), (1, 0),
                (-1, 1), (0, 1), (1, 1)
                )
    if can_visit(sea, i, j, b, h, visited):
        for s in surround:
            visited[(i, j)] = 1
            dfs(sea, i + s[0], j + s[1], b, h, visited)


def can_visit(sea, i, j, b, h, visited):
    if i >= 0 and j >= 0 and i < b and j < h:
        if (i, j) not in visited and sea[i][j] == 1:
            return True


def find_island(sea):
    visited = {}
    h = len(sea)
    count = 0
    for i, row in enumerate(sea):
        b = len(row)
        for j, item in enumerate(row):
            if can_visit(sea, i, j, b, h, visited):
                count += 1
                dfs(sea, i, j, b, h, visited)
    return count


sea = [[1, 1, 0, 0, 0],
       [0, 1, 0, 0, 1],
       [1, 0, 0, 1, 1],
       [0, 0, 0, 0, 0],
       [1, 0, 1, 0, 1]
       ]

print find_island(sea)
我认为这是这里最好的答案！ - aerin
1
你想要使用不相交集合数据结构和算法。这将为每个连通分量选择唯一的代表，最后可以对其进行计数。
为了高效地评估哪些元素是邻居，您可以逐行扫描矩阵，保持前一行的连续1段的列表，同时确定当前行上哪些段与它们相邻。
我看不出你如何将代表元素分配给特定集合，以便集合中的所有其他元素都是该元素的后代。 - Saeed Amiri
经典的不相交集合操作简述：每个不相交集合都表示为一个反转的树，只有“父”链接。要找到集合的代表元素，请跟随“父”链接以找到树的根。要连接两棵树，请找到每个树的根，并使其中一个成为另一个的父节点。 - comingstorm
我知道什么是不相交集合，其中最重要的方法之一是“查找”方法（请参见维基百科）。实际上，我问你如何实现“查找”方法？（通过这个问题陈述。） - Saeed Amiri
树的根是代表元素。维基百科链接描述了这一点，以及实现摊销O（inverseAckermann（N））性能所需的优化。 - comingstorm
1

这里有3个相连的集合。所有彼此相邻的1被视为一个单独的集合。在a [1,4] ，a [2,3] ，a [3,3] 和a [4,4] 位置上的所有1构成一个集合；在a [1,1] 位置上的1形成一个集合；在a [4,1] 位置上的1形成一个集合。

0

这并不像看起来的那么难。实际上，这感觉非常像一位教授会在计算机科学一年级课程作业中布置的任务。因此，如果这是作业，你应该标记它。

然而，解决方案相当容易。

for (int y = 0; y < arr.height(); y++)
{
   for (int x = 0; x < arr.width(); x++)
   {
      if (arr[x][y] == 1)
      {
         if (CheckIfConnected(x, y, arr))
         {
            connectedPositionsX.Add(x);
            connectedPositionsY.Add(y);
         }
      }
   }
}

其中 connectedPositions 将是一个链表或您想要存储集合的任何数据结构。

arr 是一个包含您上面指定类型的矩阵的二维数组。

CheckIfConnected 也可以相对简单地实现。

bool CheckIfConnected(int x, int y, int[][]arr)
    {
       if (arr.width() >= 2) || (arr.height() >= 2)
       {
          if ((x < arr.width()) && (x >= 0) && (y < arr.height()) && (y >= 0))
          {
            if ((x-1) >= 0) //West
            {
                if (arr[x-1][y] == 1)
                {
                    adjCount[x-1][y] += 1;
                    return true;
                }
            }
            if (((x-1) >= 0) && ((y-1) >= 0)) //Northwest
            {
                if (arr[x-1][y-1] == 1)
                {
                    adjCount[x-1][y-1] += 1;
                    return true;
                }
            }
            if ((y-1) >= 0) //North
            {
                if (arr[x][y-1] == 1)
                {
                    adjCount[x][y-1] += 1;
                    return true;
                }
            }
            if (((x+1) < arr.width()) && ((y-1) >= 0)) //Northeast
            {
                if (arr[x+1][y-1] == 1)
                {
                    adjCount[x+1][y-1] += 1;
                    return true;
                }
            }
            if ((x+1) < arr.width()) //East
            {
                if (arr[x+1][y] == 1)
                {
                    adjCount[x+1][y] += 1;
                    return true;
                }
            }

            //I'll let you implement Southeast to Southwest on your own,
            //the pattern is clear now.
          }
       }
       return false;
    }

从那里开始，您就知道在网格中每个位置上找到了多少次配对。这有助于您跟踪连接。

2D数组adjCount中的计数为您跟踪此信息。

您还可以通过修改Dijkstra算法以递归方式执行它。由于您提到了DFS（深度优先搜索），我假设您的教授或老师希望您以这种方式解决它。

在这种情况下：

以下是Dijkstra算法的伪代码：http://en.wikipedia.org/wiki/Dijkstra's_algorithm

希望这有所帮助！干杯！

0

扫描矩阵中的1。当您找到一个时，调用递归函数标记其连接组件（如果尚未标识为其中之一）。使用递归查找连接组件。在某个地方进行快速查找，以告诉您是否已将给定节点标识为连接组件，以避免标识2次连接组件，并避免在遍历连接组件时出现无限循环。

0
如果您想仅使用矩阵（不需要额外的内存）来完成此操作，请按以下步骤进行：
将扫描器位置设置为[0,0]
1. 将计数器设置为零。 2. 从当前扫描器位置逐行（以及单元格）扫描矩阵，并查找一个1，然后将扫描器位置设置为此1之后的下一个元素。如果没有1，则转到步骤6。 3. 将相关的1设置为“counter + 2”，并递归地查找其所有“1”邻居，并将它们也设置为“count + 2”。 4. “count = count + 1” 5. 转到步骤2。 6. 输出“count”。
PS：如果扫描器位置大于矩阵大小，则算法将结束（我没有写这个是为了避免混淆）。
0
0
如果你使用Python，可以在scipy中找到一个函数来查找这个数字。
from scipy.ndimage import label

data = [[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]]

connection_structure = [[1,1,1],
                        [1,0,1],
                        [1,1,1]]

_, N = label(data, connection_structure)
    
print(N) 
>>> 9
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接