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。

4

11 回答 11

7

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

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

扫描1：

从头开始

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

    1 0 0 2

  2. 转到下一行，每行中的每个 1 检查您左边的邻居是否为非 0
    • 如果非 0 取左边的值
    • if 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 条目的数量

于 2012-06-28T21:49:46.780 回答
3

连接组件标记算法旨在标记连接的元素组（用于 4 连接和 8 连接）

于 2012-06-29T11:35:58.873 回答
2

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

# 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)
于 2015-10-19T11:52:29.987 回答
1

有 3 个连接的集合。彼此相邻的所有 1 都被视为一个集合。所有 1 在a[1,4],a[2,3]和形成一组，一个在a[3,3]形成一组，一个在形成一组。a[4,4]a[1,1]a[4,1]

于 2012-09-10T05:29:32.310 回答
1

您想使用不相交的集合数据结构和算法。这将为每个连接的组件选择一个唯一的代表，您可以在最后计算。

为了有效地评估哪些元素是邻居，您可以逐行扫描矩阵，维护1前一行的（连续的）段列表，同时确定当前行上的哪些段与它们相邻。

于 2012-06-28T21:40:23.467 回答
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;
    }

从那里，您知道您在网格中的每个位置上找到了多少次配对。这可以帮助您跟踪您的连接。

二维数组中的计数adjCount会为您记录这一点。

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

在这种情况下：

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

希望有帮助！干杯!

于 2012-06-28T22:27:50.850 回答
0

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

于 2012-06-28T21:28:33.010 回答
0

对于值为 1 的每个节点，只需在东、东南、南和西南方向一次递归搜索。如果访问函数的调用是新调用而不是来自递归，则增加连接的组件。

import java.util.Scanner;

public class Solution {

    public static void visit(int[][] ar, boolean[][] v,int i, int j){
        int size = ar.length;
        if(ar[i][j] == 1){
            v[i][j] = true;
            if(j>0 && i<size-1){
                visit(ar,v,i+1,j-1); // SouthWest
            }
            if(i<size-1){
                visit(ar,v,i+1,j); // South
                if(j < size-1)
                    visit(ar,v,i+1,j+1); // SouthEast
            }
            if(j<size-1)
                visit(ar,v,i,j+1); // East
        }
    }

    public static void main(String[] args) {
        int[][] ar;
        int count = 0;
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ar = new int[n][n];
        boolean[][] v = new boolean[n][n];
        for(int i=0; i<n ; i++) {
            for(int j=0; j<n; j++){
                ar[i][j] = sc.nextInt();
                v[i][j] = false;
            }
        }

        for(int i=0; i<n ; i++) {
            for(int j=0; j<n; j++){                
                if(ar[i][j] == 1 && !v[i][j]){
                    count++;
                    visit(ar,v,i,j);
                }
            }
        }
        System.out.println(count);
    }
}
于 2015-02-27T13:19:14.977 回答
0

如果你只想通过你的矩阵来做（没有额外的内存），请按以下方式进行：

将扫描仪位置设置为 [0,0]

  1. 将计数器设置为零。
  2. 从当前扫描仪位置逐行（和逐个单元格）扫描矩阵并找到一个1并将扫描仪位置设置为在此之后的下一个元素1，如果没有任何1转到步骤 6。
  3. 将相关的一个设置为counter+2并递归地找到它的所有1邻居并将它们设置为count + 2。
  4. count = count + 1
  5. 转到第 2 步。
  6. 输出count。

PS：很清楚扫描仪位置是否大于您的算法将完成的矩阵大小（我没有写这个以防止混淆）。

于 2012-06-28T22:21:24.863 回答
0

我有一门课可以帮助你找到二维数组中连接组件的总数。我的课不仅给你总数，还给你集群并为你可视化它们。您可以注释掉不需要的部分。请在（java）中查看此类：https ://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/ConnectedComponetns.java

于 2016-08-06T20:10:51.637 回答
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
于 2016-10-19T12:58:10.040 回答