当前位置:首页 > 开发 > Web前端 > 前端 > 正文

深度优先搜索学习五例之四(JAVA)

发表于: 2012-10-21   作者:128kj   来源:转载   浏览:
摘要:    先继续“深度优先搜索学习五例之三” http://128kj.iteye.com/admin/blogs/1702286中的迷宫,那里用栈实现了深搜,但只输出了一条路径,下面程序用递归实现深搜,输出所有到出口的路径和数目: import java.util.Stack; ///////////////////////////////////////////
   先继续“深度优先搜索学习五例之三” http://128kj.iteye.com/admin/blogs/1702286中的迷宫,那里用栈实现了深搜,但只输出了一条路径,下面程序用递归实现深搜,输出所有到出口的路径和数目:
import java.util.Stack;   
////////////////////////////////////////////////   
//深度优先搜索之迷宫问题:输出所有到出口的路径
public class MazeDsf{   
  private static final int M=9;   
  private static final int N=8;  
  private int total; 
     
 //迷宫矩阵,0为通道,1为障碍   
  //入口(0,0),出口(8,7)   
   private int[][] Matrix = {   
            { 0, 1, 1, 1, 1, 1, 1, 1 },   
            { 0, 0, 0, 0, 0, 0, 0, 0 },      
            { 0, 1, 1, 1, 1, 0, 1, 0 },       
            { 0, 0, 0, 0, 0, 0, 1, 0 },      
            { 0, 1, 0, 0, 0, 0, 1, 0 },       
            { 0, 1, 0, 1, 1, 0, 1, 0 },      
            { 0, 1, 0, 0, 0, 0, 1, 1 },       
            { 0, 1, 0, 0, 1, 0, 0, 0 },      
            { 0, 1, 1, 1, 1, 1, 0, 0 } };     
  
  
    public MazeDsf(){   
       total=0;
    }   
   
  
  //右下上左   
  private int x_off[] = {0,1,-1,0};   
  private int y_off[] = {1,0,0,-1};   
 
  
   //输出迷宫   
 private void PrintMatrix(){   
    System.out.println("入口(0,0),出口(8,7)的迷宫,2为通道,1为障碍:");   
   for(int i = 0; i < M; ++i){   
     for(int j = 0; j < N; ++j)   
       System.out.print(Matrix[i][j]);   
    System.out.println();   
  }   
}   
   //深度优先搜索所有可能的路径   
public void dfs(int x,int y)
{
      Matrix[x][y]=2;
      if(x == 8&& y == 7){   
        //输出找到的路径   
        total++;
        PrintMatrix();
             
      }   
     
    for(int i = 0; i<4; ++i){ //右下上左   
      int nx = x + x_off[i];   
      int ny = y + y_off[i];   
      if(nx >= 0 && nx < M && ny>=0 && ny< N && Matrix[nx][ny] == 0){    
            dfs(nx,ny);
        }
    }
     Matrix[x][y] =0;//这里就是回溯,很重要!!!
}

  public int getTotal(){
    return total;
  }
  
  
  //测试代码主函数   
  public static void main(String args[]) {    
     MazeDsf maze=new MazeDsf();   
     maze.PrintMatrix();   
     maze.dfs(0,0);
     System.out.print("共有"+maze.getTotal()+"条路径");  
   }   
} 


运行结果:
.........................................省略很多
入口(0,0),出口(8,7)的迷宫,2为通道,1为障碍:
21111111
20000000
21111010
22202210
01222210
01011210
01000211
01001222
01111102
入口(0,0),出口(8,7)的迷宫,2为通道,1为障碍:
21111111
20000000
21111010
22202210
01222210
01011210
01000211
01001220
01111122
.......................
共有72条路径

再看下面POJ1562:
题意:在一个n*m的地图上探索有多少块油田,'@'表示单位油田,相邻的(上下左右与对角线)单位油田为一个大油田,问有多少个大油田。

Sample Input

1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0
Sample Output

0
1
2
2

   就是求多少个连通分量,顺序扫描,每扫面到一个@,并且这个格子没有被深度遍历过,就进行一次深度优先遍历.

import java.util.Scanner;
public class Main{
  int m, n;  
  char map[][]; 
  int move[][] = { {-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1} };  
  
  public Main(int m,int n,char[][] map){
     this.m=m;
     this.n=n;
     this.map=map;
     
  }

  private void DFS(int si, int sj) {  
   
   
    for (int i = 0; i<8; ++i) {  
        int mi = si + move[i][0];  
        int mj = sj + move[i][1];  
        if (mi >= m|| mj >= n || mi < 0 ||mj < 0) continue ;  
        if (map[mi][mj] == '@') {  
            map[mi][mj] = '*';  
            DFS(mi, mj);  
        }  
    }  
    return ;  
  }  
  
  public static void main(String args[]){ 
     Scanner in=new Scanner(System.in);
     while(true){
	int a=in.nextInt();
	int b=in.nextInt();
	if(a==0&&b==0)break;
	int count=0;
	char[][] map=new char[a][b];
	for(int i=0;i<a;i++){
           String s=in.next();
           for(int j=0;j<b;j++)
              map[i][j]=s.charAt(j);
	}
        Main m=new Main(a,b,map);
        int answer=0;
        for (int i = 0; i<a; i++)  
            for (int j = 0; j<b; j++)  
                 if (map[i][j] == '@') {  
                    map[i][j] = '*';  
                   m.DFS(i, j);  
                    ++answer;  
                }  
  
  
        System.out.printf("%d\n", answer);  
    }  
}
}  


下载:

深度优先搜索学习五例之四(JAVA)

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
深度优先搜索DFS(Depth First Search) (一)深度优先搜索遍历类似于树的先根遍历,是树的先根遍历的
一、深度优先搜索框架一递归实现,流程如下: public void dfs(int v) { visited[v] = true; //访问起
再次强调: 图的广度优先搜索,要遵守以下规则: (0) 选取某一顶点作为开始搜索的起点(当前顶点),
有两种常用的方法可用来搜索图:即深度优先搜索和广度优先搜索。它们最终都会到达所有连通的顶点。
广度优先搜索是以某一节点为出发点,先拜访所有相邻的节点。 再依序拜访与刚才被拜访过的节点相邻但
遍历,直到图中所有顶点都被访问到为止。 import java.util.Stack; // 图的邻接矩阵实现及深度优先
图的遍历是指从图中的某一个顶点出发,按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅
深度优先搜索(DFS:Depth-First Search)是一种图搜索策略,其将搜索限制到 2 种操作: (a) 访问图
深度优先搜索简述 深度优先搜索(depth-first search,简称dfs)就是递归地进行一系列操作,直到找到
深度优先搜索(dfs) 这几天在看深度优先搜索,把自己理解的深度的内容给整理一下。 深度优先搜索,
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号