`
128kj
  • 浏览: 600347 次
  • 来自: ...
社区版块
存档分类
最新评论

广度优先搜索学习五例之一

阅读更多
   有两种常用的方法可用来搜索图:即深度优先搜索和广度优先搜索。它们最终都会到达所有连通的顶点。深度优先搜索通过栈或递归来实现,而广度优先搜索通过队列来实现。 

广度优先搜索:
    它首先访问起始顶点的所有邻接点,然后再访问较远的区域。它是用队列来实现的。
下面图中的数字显示了广度优先搜索顶点被访问的顺序。



图的广度优先搜索,要遵守以下规则:
(0) 选取某一顶点作为开始搜索的起点(当前顶点)入队列,标记为已访问。
(1) 访问当前顶点的下一个未被访问的邻接点,这个点必须是当前顶点的邻接点,标记它,并把它插入到队列中。
(2) 如果因为已经没有未访问的邻接点而不能执行规则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);
          }
       }//当前顶点所有邻接点访问完毕
     }//队列为空退出
  }  


例二:迷宫问题
定义一个二维数组:

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表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。
Input
一个5 × 5的二维数组,表示一个迷宫。数据保证有唯一解。
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<Point> qu=new LinkedList<Point>(); 
    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)\n",point[i].x,point[i].y); 
     System.out.printf("(4, 4)\n");////最后要打印的,之前没记录它 

 }


 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 + ")";
  }
  
  }
  

下载源码
  • 大小: 10.3 KB
分享到:
评论

相关推荐

    广度优先搜索学习五例之四

    【标题】:“广度优先搜索学习五例之四” 在计算机科学中,广度优先搜索(Breadth-First Search,简称BFS)是一种用于遍历或搜索树或图的算法。它按照从根节点开始,逐层进行探索的方式进行。在本案例中,我们可能...

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

    【标题】:“广度优先搜索学习五例之二(JAVA)” 在计算机科学中,图算法是解决问题的关键工具之一,而广度优先搜索(Breadth-First Search, BFS)是一种用于遍历或搜索树或图的算法。本篇文章将重点讲解如何在...

    广度优先搜索学习五例之三

    【标题】"广度优先搜索学习五例之三"涉及的是图论算法中的一个重要概念——广度优先搜索(Breadth-First Search, BFS)。在计算机科学中,BFS是一种用于遍历或搜索树或图的算法,尤其适用于查找最短路径问题。此标题...

    广度优先搜索学习五例之五

    在给定的"广度优先搜索学习五例之五"中,我们可能探讨的是一个具体的应用场景或者变体,但描述中并未提供详细信息。通常,BFS 的实现涉及以下几个关键元素: 1. **队列(Queue)**:BFS 使用队列作为主要的数据结构...

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

    在这个主题"深度优先搜索学习五例之一(JAVA)"中,我们可以期待看到至少五个不同的应用实例,这些实例将用Java语言实现,可能包括但不限于以下场景: 1. **图的遍历**:DFS可以用于遍历无向图或有向图,通过访问每...

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

    在这个“深度优先搜索学习五例之四”的主题中,我们将重点关注使用Java实现DFS解决具体问题的情况。这篇博客文章可能通过一个具体的实例,如迷宫求解,来演示如何利用DFS进行递归或栈操作。 首先,我们来看"MazeDsf...

    人工智能原理学习教案.pptx

    盲目搜索如宽度优先搜索(BFS)和深度优先搜索(DFS),在未知环境中探索所有可能的解决方案路径,虽然简单但效率较低。启发式搜索则依据某种评估函数来指导搜索方向,如A*搜索,通过结合路径代价和预计到达目标的...

    《人工智能导论-》- 03 搜索.ppt

    总结来说,搜索是人工智能问题求解的关键技术之一,包括但不限于盲目搜索(如宽度优先搜索)和启发式搜索。这些方法在游戏策略、知识表示、规划等领域有广泛应用。理解并掌握搜索策略对于深入学习人工智能至关重要。

    第一章人工智能当中的搜索.ppt

    盲目搜索遵循预设的控制策略,不利用中间信息来改进策略,例如深度优先搜索和广度优先搜索。而启发式搜索则引入了与问题相关的启发式信息,如评估函数,以引导搜索向最有可能导致解的方向发展,如A*搜索算法。启发式...

    算法参考资料国际大学生程序设计竞赛例题解1数论,计算几何,搜索算法专集

    - 广度优先搜索(BFS):一种用于遍历或搜索树或图的算法。它先访问起始点的邻接节点,然后是邻接节点的邻接节点,依此类推。 - 启发式搜索:利用特定问题领域的知识来引导搜索过程,如A*搜索算法。 - 双向搜索:...

    信息学奥赛一本第五版通教学课

    搜索算法如二分查找、广度优先搜索(BFS)和深度优先搜索(DFS),在解决图论问题和树形结构问题时非常关键。动态规划是一种强大的问题解决方法,通过构建状态转移方程,可以解决很多复杂的问题,如斐波那契数列、...

    C语言教程及经典程序100例

    在C语言中实现这样的算法,通常会用到深度优先搜索(DFS)或广度优先搜索(BFS)等图遍历策略,也可能涉及动态规划等复杂算法。 通过这个文件,学习者可以了解到如何在C语言中表示图,如何遍历图以及如何设计和实现...

    【完整版】清华大学精品AI人工智能课程 第3章 智能搜索 含习题 共91页.pptx

    盲目搜索是一种不考虑问题特性的简单搜索方法,例如宽度优先搜索(BFS)和深度优先搜索(DFS)。而启发式搜索则引入了估计代价或接近目标程度的函数,如A*搜索算法,它结合了盲目搜索和启发式信息,能够在有限计算...

    C经典编程900例

    例如,快速排序、归并排序、二分查找、哈希表、贪心算法、深度优先搜索和广度优先搜索等。这些都是ACM竞赛中常见的问题类型,学习这些算法不仅可以提升你的编程能力,也能训练你的逻辑思维和问题解决技巧。 C语言的...

    头歌数据结构图的邻接矩阵存储及遍历操作

    图的遍历算法是图论中的基础概念之一,深度优先遍历和广度优先遍历各有优缺点,具体选择哪种遍历方法取决于实际应用场景的需求。例如,在搜索最短路径问题中,广度优先遍历更合适;而在搜索所有可能路径的问题中,...

    19最小生成树PPT学习教案.pptx

    最小生成树是图论中的一个重要概念,特别是在...通过深度优先搜索和广度优先搜索,我们可以找到图中的路径和最短路径,进而构造出最小生成树。这些算法在解决实际问题如网络设计、运输调度等场景中具有广泛的应用价值。

    C语言实战105例源码

    5. **算法实现**:C语言是实现算法的理想工具,实例可能涵盖了排序(如冒泡排序、快速排序)、查找(如线性查找、二分查找)、图算法(如深度优先搜索、广度优先搜索)等经典算法。 6. **游戏编程**:例如“俄罗斯...

    C语言经典算法100例

    8. **图形算法**:如深度优先搜索(DFS)和广度优先搜索(BFS),以及Dijkstra算法和Floyd算法用于找到图中两点间的最短路径。 9. **数学算法**:如大整数运算、矩阵运算、素数检测、组合数学等,这些算法在密码学...

    算法实例50例

    迭代则在很多情况下提供更高效的解决方案,如深度优先搜索、广度优先搜索等。 10. **字符串处理**:KMP算法、Rabin-Karp模式匹配算法、Z算法等,这些算法在文本处理、搜索引擎等领域有着广泛的应用。 通过《经典...

Global site tag (gtag.js) - Google Analytics