当前位置:首页 > 开发 > 编程语言 > 搜索 > 正文

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

发表于: 2012-10-22   作者:128kj   来源:转载   浏览:
摘要: 一、深度优先搜索遍历磁盘文件目录 import java.io.File; import java.io.IOException; import java.util.Stack; import java.util.Queue; import java.util.LinkedList; public class ListFile{ public static voi
一、深度优先搜索遍历磁盘文件目录
import java.io.File;
import java.io.IOException;
import java.util.Stack;
import java.util.Queue;
import java.util.LinkedList;
public class ListFile{
        public static void main(String[] args) throws IOException {
              File file = new File("c:/java");
               DFS1(file);
               System.out.println("--------------------------------------");
               System.out.println("--------------------------------------");
                DFS2(file);
              
        }
        // 文件深度优先遍历,栈实现
        private static void DFS1(File file) throws IOException {
               Stack< File> stack = new Stack< File>();
               stack.push(file);//当前目录进栈
               File fileInStack = null;
             while (!stack.isEmpty()) {
              fileInStack = stack.pop();
              System.out.println("dir:" + fileInStack.getCanonicalPath());//访问当前目录
              File[] files = fileInStack.listFiles();//当前目录的所有邻接点
                 for (File eachFile : files) {
                    if (eachFile.isFile()) {
                        System.out.println("file:" + eachFile.getCanonicalPath());
                    } else {
                         stack.push(eachFile);//邻接点进栈
                    }
                  }
                }
        }

        // 文件深度递归遍历
        private static void DFS2(File file) throws IOException {
             System.out.println("dir:" + file.getCanonicalPath());
             File[] files = file.listFiles();
             for (File eachFile : files) {
               if (eachFile.isFile()) {
                   System.out.println("file:" + eachFile.getCanonicalPath());
               } else {
                   DFS2(eachFile);
                 
             }
          }
     }
     
}




二、POJ 1501
题意:给出一个字符矩阵和多行单词,然后看字符矩阵中是否有和这些单词匹配的单词,只能按照直线(横、竖、斜)进行匹配,如果匹配成功则输出首字母和末字母匹配成功的位置,没有则输出Not found。样例如下:

Sample Input

5
EDEEE
DISKE
ESEEE
ECEEE
EEEEE
DISC
DISK
DISP
0
Sample Output

1,2 4,2
2,1 2,4
Not found


思路:遍历字符矩阵中的每一个字符,看其是否与所给单词的第一字符相同,如果相同则DSF继续搜索下一个字母。

import java.util.Arrays;
import java.util.Scanner;
public class Main{
 private char c[][];  //字符矩阵
 private int n;  //字符矩阵的大小n*n
 private String s;//在字符中要找的单词
 private boolean flag;//匹配成功的标志
 private boolean vis[][];  //状态数组
 private int sx,sy,ex,ey;//匹配成功后,首字母和末字母匹配成功的位置

 private int dir[][]={{0,-1},{0,1},{-1,0},{1,0},{-1,-1},{-1,1},{1,-1},{1,1}};  

   public Main(int n,String s,char[][] c){
      this.n=n;
      this.s=s;
      this.c=c;
      flag=false;
      vis=new boolean[n][n];
   }


  private void dfs(int i,int j,int m,int k) {  
    int x,y;  
    if(flag) return;  
     //深搜结束条件,必须加个m==s.length()因为给出的字符串可能有重复字母   

      if((c[i][j]==s.charAt(s.length()-1))&&m==s.length()) {  
      ex=i;ey=j;  //记录匹配成功末字符位置
      flag=true;   
      return;  
     }  
    x=i+dir[k][0];  
    y=j+dir[k][1];  
    if(x>=0&&x<n&&y>=0&&y<n&&c[x][y]==s.charAt(m)&&!vis[x][y])  
    {  
      vis[x][y]=true;  
      dfs(x,y,m+1,k);  //同一方向,搜索下一个字符
      vis[x][y]=false;  
    }  
  }  
  
   public static void main(String args[]){ 
     Scanner in=new Scanner(System.in);
     String s="";
     int n=in.nextInt();  
     char[][] c=new char[n][n];
 
     for(int i=0;i<n;i++){
      s=in.next();
       for(int j=0;j<n;j++)
          c[i][j]=s.charAt(j);
      }

     
     while(true)  { 
      s=in.next();
      if(s.equals("0")) break;  
       Main main=new Main(n,s,c);
       main.go();
     }
   }

 private void go(){
  
     for(int i=0;i<n;i++)
       for(int j=0;j<n;j++)  
         if(c[i][j]==s.charAt(0)){//找到第一个字母后,按同一个方向搜索   
           for(int k=0;k<8;k++){  
             dfs(i,j,1,k);  
             if(flag)   
             {   
               sx=i;sy=j;   
               System.out.printf("%d,%d %d,%d\n",sx+1,sy+1,ex+1,ey+1); 
               return;
             }  
           }  
         }  
      
       if(!flag) System.out.printf("Not found\n");  
   }  
  
}  

深度优先搜索学习五例之五(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号