４方向の深さ優先探索アルゴリズム

授業で何回か深さ優先探索を実装する場面があったので、それを４方向に拡張して実装してみます。

再帰的に探索すれば結構簡単な実装になると思います。

探索クラス

サーチクラスを作っていきます。

public class Search {
    
    public int[][] array;
...
}

コンストラクタ

ここで二次元配列を初期化しておきます。

public Search(int arraysize){
        array = new int[arraysize][arraysize];
    }

toString()

わかりやすいように二次元配列を視覚化します。

public String toString(){
        String result = "";
        for (int i = 0;i<array.length;i++){
            if (i !=0){
                result += "|\n|";
            }else{
                result += "\n|";
            }
            for (int j = 0;j<array[0].length;j++){
                if (j != array[0].length-1){
                    result += array[i][j] + " ";
                }else{
                    result += array[i][j];
                }
                
            }
           
        }
        return result + "|";
    }

メインクラス

いったんどんな風になったか確認してみます。

public static void main(String[] args) {

        int arraysize = 20;
        Search search = new Search(arraysize);
        Random rand = new Random();
        for (int i = 0;i<arraysize*arraysize/2;i++){
            search.setArray(rand.nextInt(arraysize), rand.nextInt(arraysize));
        }
        System.out.println(search);
    }

出力結果

|1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 1|
|0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0|
|1 1 1 0 0 0 1 0 1 1 0 0 0 1 0 1 1 0 0 1|
|1 0 1 1 0 1 1 0 1 0 0 0 0 0 1 0 1 0 1 0|
|0 1 1 1 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1 1|
|0 1 0 0 0 1 1 0 1 1 0 1 0 0 1 0 0 1 1 0|
|0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 1 0 1 1 0|
|0 0 0 0 0 0 0 1 0 0 1 1 1 1 0 0 1 1 0 0|
|0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1|
|0 0 1 1 1 1 0 1 0 1 0 0 0 0 0 1 0 0 0 0|
|0 1 1 1 0 1 0 1 0 0 1 1 1 0 1 0 1 0 1 0|
|0 1 0 0 0 1 1 1 1 0 0 0 0 1 0 1 1 1 0 0|
|0 1 0 1 1 1 0 1 1 0 0 0 0 0 0 1 0 1 0 0|
|0 0 0 0 1 1 1 0 0 1 0 1 1 0 1 0 1 0 0 0|
|0 0 1 0 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0|
|1 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 0 0 1 1|
|0 1 0 0 0 0 1 0 1 0 0 0 1 0 0 1 1 0 1 0|
|1 1 1 0 0 1 1 0 1 1 0 1 1 0 1 0 0 0 1 0|
|0 0 1 0 1 0 1 0 1 1 0 0 0 0 1 1 1 0 0 1|
|0 0 1 0 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 0|

DFSアルゴリズム

探索開始地点を1として、隣接する四方の数が１であったら次に進むというアルゴリズムを再帰的に書いていきます。ついでに開始地点を設定するメソッドも書いておきます。

public void setArray(int i, int j){
        array[i][j] = 1; 
    }
    
    public void dfs(int[][] array, int i, int j){
        if (j < 0 || i < 0 || j  >= array.length || i >= array[1].length || array[i][j] != 1){
            return;
        }else{
            array[i][j] = 2;
            dfs(array, i+1, j);
            dfs(array, i-1, j);
            dfs(array, i, j-1);
            dfs(array, i, j+1);
        }
    }

実行結果

|1 1 1 1 0 0 1 1 1 1 0 1 1 0 0 0 0 0 1 0|
|0 1 0 1 1 0 0 1 1 1 0 1 0 1 1 0 0 1 0 0|
|0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 1 1 0 1 0|
|0 1 1 0 1 0 0 0 0 1 1 0 1 1 1 0 0 0 0 0|
|1 1 0 1 0 1 1 0 0 0 0 1 0 1 0 0 0 0 0 1|
|0 0 1 0 1 1 1 0 1 1 0 0 0 0 1 0 0 0 0 0|
|1 0 1 1 0 1 0 0 1 1 0 0 0 0 0 0 1 0 0 0|
|1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 0 1 0|
|0 1 0 1 1 0 0 1 0 0 1 0 1 0 1 0 0 0 0 0|
|1 1 1 1 1 0 0 0 0 2 0 0 1 0 0 1 0 0 0 0|
|0 0 1 0 0 1 0 0 0 2 2 0 0 0 0 0 1 0 1 1|
|0 1 0 1 1 0 0 0 1 0 2 2 0 1 1 1 1 1 0 0|
|0 0 1 1 0 0 0 0 0 2 2 0 0 0 0 0 0 1 1 1|
|0 0 0 1 0 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0|
|1 1 0 0 1 1 0 0 0 0 1 1 1 0 1 0 1 1 0 1|
|1 0 1 0 0 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0|
|1 0 0 0 1 1 0 1 1 0 1 1 0 0 1 0 1 0 0 0|
|0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1|
|0 0 0 1 0 1 0 0 0 0 1 0 0 0 1 0 1 1 0 1|
|1 0 0 1 0 0 1 1 0 1 0 0 1 0 1 0 0 0 1 0|

繋がった部分だけ2に置き換えられているのがわかります。

全方位探索

2D配列の場合は８方向に変えるだけで全方向に探索することができます。

public void dfs(int[][] array, int i, int j){
        if (j < 0 || i < 0 || j  >= array.length || i >= array[1].length || array[i][j] != 1){
            return;
        }else{
            array[i][j] = 2;
            dfs(array, i+1, j);
            dfs(array, i+1, j+1);
            dfs(array, i-1, j);
            dfs(array, i-1, j-1);
            dfs(array, i, j-1);
            dfs(array, i+1, j-1);
            dfs(array, i, j+1);
            dfs(array, i-1, j+1);
        }
    }