広さ優先検索学習5例の1つ

図を検索するには、深さ優先検索と広さ優先検索の2つの一般的な方法があります.最終的には、すべての接続された頂点に達します.深度優先探索はスタックまたは再帰によって実現され、広さ優先探索はキューによって実現される.
広さ優先検索:
最初に、開始頂点のすべての隣接点にアクセスしてから、遠い領域にアクセスします.キューで実現されます.
次の図の数字は、広さ優先探索頂点がアクセスされる順序を示している.
[img]http://dl.iteye.com/upload/attachment/0074/9856/9a8c98be-360d-34e7-8021-5d5601c5deda.jpg[/img]
図の広さ優先検索は、次のルールに従います.
(0)検索開始の開始点(現在の頂点)として頂点を選択し、アクセス済みとしてマークします.
(1)現在の頂点の次の非アクセスの隣接点にアクセスします.この点は、現在の頂点の隣接点であり、マークし、キューに挿入する必要があります.
(2)アクセスされていない隣接点がないためルール1を実行できない場合は,キューヘッダから頂点を1つ取り,現在の頂点とする.
(3)キューが空でルール2が実行できない場合は検索を終了する.

  ：           
 private static void BFS(File file) throws IOException{  
     System.out.println(file.getCanonicalPath());//     
     Queue< File> queue = new LinkedList< File>();  
     queue.offer(file);  //    
     File fileInQueue = null;
     while (queue.size() > 0) {  
       fileInQueue = queue.poll();  //       
       File[] files =fileInQueue.listFiles(); //            
       for (File eachFile : files) {//              
         if (eachFile.isFile()) {//          ,          
            System.out.println("file:" + eachFile.getCanonicalPath());
         } else {//          ,       
             System.out.println("dir--:" + eachFile.getCanonicalPath());
             queue.offer(eachFile);
          }
       }//             
     }//      
  }  

例二:迷宮問題
2 D配列を定義します.
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
それは1つの迷路を表して、その中の1は壁を表して、0は歩くことができる道を表して、横に歩くか縦に歩くしかなくて、斜めに歩くことができなくて、プログラムに左上の角から右下の角までの最短のルートを探し出すように要求します.
Input
1つ5× 5の2次元配列で、迷路を表します.データは一意の解を保証します.
Output
左上隅から右下隅までの最短パスで、サンプルのようにフォーマットされています.
Sample Input
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
Sample Output
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

import java.util.*;
public class Main{

 private Point cur,next;//          
 private Point record[][];//      
 private int dir[][]={{0,1},{1,0},{0,-1},{-1,0}};//     , , , ,  
 private int mark[][]; //    

 public Main(int mark[][]){//    
     this.mark=mark;
     record=new Point[5][5];
     for(int i=0;i< 5;i++)
       for(int j=0;j< 5;j++)
        record[i][j]=new Point();
     cur=new Point();
     next=new Point();
 }

 public void bfs(){ //        

    int i; 
    Queue qu=new LinkedList(); 
    cur.x=0; 
    cur.y=0; 
    qu.offer(cur); //    
    mark[0][0]=1; //      
    while(!qu.isEmpty()) { //    
      cur=qu.poll(); //       ,      
     //            ,     ,     , , , ,  
     for(i=0;i<4;i++){
        next.x=cur.x+dir[i][0]; 
        next.y=cur.y+dir[i][1]; 
        if(next.x==4&&next.y==4){//      

          record[next.x][next.y].x=cur.x; //             
          record[next.x][next.y].y=cur.y;
          return; 
        } 
        if(next.x>=0&&next.x<5&&next.y>=0&&next.y<5&&mark[next.x][next.y]==0){ //      
          //             
          record[next.x][next.y].x=cur.x; //             
          record[next.x][next.y].y=cur.y;
          mark[next.x][next.y]=1; //         
          qu.offer(new Point(next.x,next.y)); //  
       } 
     }//              
   } //    

} 

 public void print(){
   Point point[]=new Point[50];
   int i=4;int j=4;int k=0; int m=0;int n=0;
   while(i!=0||j!=0)/////      record[][]    
   { 
     m=i;n=j; 
     point[k]=record[m][n]; 
     i=record[m][n].x; 
     j=record[m][n].y;            
      k++; 
   } 
      for(i=k-1;i>=0;i--)/////////////     
     System.out.printf("(%d, %d)
",point[i].x,point[i].y); 
     System.out.printf("(4, 4)
");////      ，       

 }


 public static void main(String[] args) {
  Scanner in=new Scanner(System.in);
  int[][] mark=new int[5][5];
  for(int i=0;i< 5;i++)
   for(int j=0;j< 5;j++)
     mark[i][j]=in.nextInt();

    Main m=new Main(mark);
    m.bfs();
   m.print();
 }
}

class Point { 

  int x = 0;
  int y = 0;

  public Point() {
   this(0, 0);
  }

  public Point(int x, int y) {
   this.x = x;
   this.y = y;
  }

  public boolean equals(Point p) {
   return (x == p.x) && (y == p.y);
  }

  @Override
  public String toString() {
   return "(" + x + ", " + y + ")";
  }

  }

ソースのダウンロード