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

幅優先探索を四方に対してかけていくアルゴリズムを実装してみます。

サーチクラス

import java.util.Queue;
import java.util.LinkedList;
import java.util.Random;
public class Search {
    Queue<int[]> queue = new LinkedList<>();
    int[][] array;
    ...
}

コンストラクタ

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

setter + toString()

public void setArray(int i, int j){
        array[i][j] = 1; 
    }
    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 + "|";
    }

幅優先探索アルゴリズム

開始地点から四方にスキャンしていき、もしターゲットと一致するものがあればその座標をqueueに放り込んで次ループでqueueの中身がなくなるまで処理を繰り返します。この時、次の次の座標にターゲットと一致するものがあれば、再度queueにその座標を放り込みます。

public void bfs(int[][] array,int i, int j){

        int[] initPos = {i,j};
        queue.add(initPos);
    
        while(queue.size() > 0){

            int[] tmp = queue.remove();

            array[tmp[0]][tmp[1]]  = 2;

            int[] right = {tmp[0]-1,tmp[1]};
            int[] left = {tmp[0]+1,tmp[1]};
            int[] up = {tmp[0],tmp[1]-1};
            int[] down = {tmp[0],tmp[1]+1};

            if (tmp[0]-1 >= 0 ){
                if (array[right[0]][right[1]] == 1) {queue.add(right);}
            }
            if ( tmp[0]+1 < array.length ){
                if (array[left[0]][left[1]] == 1){queue.add(left);}
            }
            if (tmp[1]-1 >= 0  ){
                if ( array[up[0]][up[1]] == 1){queue.add(up);}
            }
            if (tmp[1]+1< array[0].length){
                if (array[down[0]][down[1]] == 1) {queue.add(down);} 
            }

        }
    }

main()

実行してみます。

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));
        }
        search.setArray(10, 10);
        search.bfs(search.array, 10,10);
        System.out.println(search);
    }

実行結果

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

隣接するターゲット座標をきちんと辿れていることがわかります。

全方位探索

探索範囲を８方向に拡張してみます。

public void bfs(int[][] array,int i, int j){

        int[] initPos = {i,j};
        queue.add(initPos);
    
        while(queue.size() > 0){

            int[] tmp = queue.remove();

            array[tmp[0]][tmp[1]]  = 2;

            int[] right = {tmp[0]-1,tmp[1]};
            int[] left = {tmp[0]+1,tmp[1]};
            int[] up = {tmp[0],tmp[1]-1};
            int[] down = {tmp[0],tmp[1]+1};

            int[] lower_right = {tmp[0]-1,tmp[1]+1};
            int[] lower_left = {tmp[0]+1,tmp[1]+1};
            int[] upper_right = {tmp[0]-1,tmp[1]-1};
            int[] upper_left = {tmp[0]+1,tmp[1]-1};

            if (tmp[0]-1 >= 0 ){
                if (array[right[0]][right[1]] == 1) {queue.add(right);}
            }
            if ( tmp[0]+1 < array.length ){
                if (array[left[0]][left[1]] == 1){queue.add(left);}
            }
            if (tmp[1]-1 >= 0 ){
                if ( array[up[0]][up[1]] == 1){queue.add(up);}
            }
            if (tmp[1]+1< array[0].length){
                if (array[down[0]][down[1]] == 1) {queue.add(down);} 
            }

            if (tmp[0]-1 >= 0 &&tmp[1]+1< array[0].length && tmp[0]+1 < array.length && tmp[1]-1 >= 0 ){
                if (array[upper_right[0]][upper_right[1]] == 1){queue.add(upper_right);}
                if (array[upper_left[0]][upper_left[1]] == 1){queue.add(upper_left);}
                if (array[lower_left[0]][lower_left[1]] == 1){queue.add(lower_left);}
                if ((array[lower_right[0]][lower_right[1]] == 1)){queue.add(lower_right);}
            }
        }
    }

条件分岐がめんどくさかったので、一括で判定できるようにしました。

実行結果

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

斜め方向にも適用できているのがわかります。

サーチクラス

コンストラクタ

setter + toString()

幅優先探索アルゴリズム

main()

実行結果

全方位探索

実行結果

コメントを残す コメントをキャンセル

コメントを残すコメントをキャンセル