使用 DFS（深度优先），找到密度超过 %X 的块的密度

Question

在我的工作（一些矩阵计算）中，我遇到了如下问题：

matrix (NxN):   
          xxxx------------------
          xxxx------------------
          ----xxx-x-------------
          ----xx--x-------------
          ---------x--x---------
          ---------xxxx---------
                   xxxx---------
            ......................

我有一个 2D adj 矩阵，其模式为块状对角线（如上所示）。每个块可以是密集的 (100%) 或稀疏的 (0.01-5%)。使用这些 adj 矩阵并使用图形搜索 (DFS)，我如何找到块大小 (begin_row、being_col、end_row、end_col) 及其相应的密度 ( mod(E)/mod(V))？

我确信有一种简单的方法可以找到方块和密度。我正在寻找任何想法或伪代码，非常感谢您抽出时间。

Answer 1

您可以横向绘制对角线以绘制每个块的开始和结束位置。
横向可以通过 dfs 或简单的循环来完成。
然后关键是检测块结束。使用 "full" 块非常简单，如 isCorner 方法所示。必须修改此方法以解决漏洞。

    //test data
    public static int[][] intArray = {
        {1,  1,  0,  0,  0,  0,  0,  0,  0},
        {1,  1,  0,  0,  0,  0,  0,  0,  0},
        {0,  0,  1,  1,  1,  1,  0,  0,  0},
        {0,  0,  1,  1,  1,  1,  0,  0,  0},
        {0,  0,  1,  1,  1,  1,  0,  0,  0},
        {0,  0,  1,  1,  1,  1,  0,  0,  0},
        {0,  0,  0,  0,  0,  0,  1,  1,  1},
        {0,  0,  0,  0,  0,  0,  1,  1,  1},
        {0,  0,  0,  0,  0,  0,  1,  1,  1}
    };

    public static void main(String[] args) {

        mapBlock();
    }

    //traverse diagonal to find block start and block end
    private static void mapBlock() {
        //todo check that matrix is nxn

        int[] origin = {0,0}; //dfs start point
        //traverse diagonal
        for(int rowIndex =0; rowIndex < intArray.length ; rowIndex ++) {
            if(isCorner(rowIndex, rowIndex)) { //diagonal row and col index are equal
                int[] target = {rowIndex, rowIndex}; //dfs target
                block(origin, target);
                origin = new int[]{rowIndex+1, rowIndex+1};
            }
        }
    }

    //is intArray[row Index][column Index] a corner 
    private static boolean isCorner(int rowIndex, int colIndex) {

        //corner must be on diagonal
        if(rowIndex != colIndex ) {
            return false;
        }

        //if last row and col it is a corner
        if(((rowIndex+1) == intArray.length) && ((colIndex+1) == intArray.length))  {
            return true;
        }

        //if left and bottom neighbors are empty - it is a corner
        //todo if you blocks have holes this criteria needs to change
        if((intArray[rowIndex+1][colIndex] == 0) && (intArray[rowIndex][colIndex+1] == 0) ) {
            return true;
        }

        return false;
    }

    private static void block(int[] origin, int[] target) {

        System.out.println("block from " +Arrays.toString(origin)+
                " to "+Arrays.toString(target));
        //todo store sub array 
    }

输出：

block from [0, 0] to [1, 1]
block from [2, 2] to [5, 5]
block from [6, 6] to [8, 8]

（测试一下 online ）

使用 DFS（深度优先），找到密度超过 %X 的块的密度

Using DFS (depth first), find the density of blocks which density is over %X

depth-first-search

adjacency-matrix