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

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

阅读更多
一、深度优先搜索框架一递归实现,流程如下:  
    public  void dfs(int v) {   
      visited[v] = true;  //访问起点v 
      System.out.print(v+"  ");   
      for (int i = 0; i < k; i++) {   
        //递归调用搜索没有被访问过的当前节点的下一个节点(邻接点)   
    if (G[v][i] == 1 && !visited[i])//G[v][i]是图的邻接矩阵   
          dfs(i);//递归调用   
      }   
    }   

 
例:八皇后问题是一个古老而著名的问题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。

    高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。
 
  public class Queen{
   private int n = 8;
   private int a[]; //皇后放在 ( i, a[i] )
   private boolean visited[]; //如果visited[i]为true,表示第i列已经被占了.
   int total = 0; //方案总数

   public Queen(){
    a=new int[8];
    visited =new boolean[8];
   }


   public static void main(String args[]){
     Queen m=new Queen();
     m.dfs(0);
     System.out.println(m.getTotal());
    }


    private boolean can(int d){ //判断第d行的Queen可否放在第a[d]列
      if( visited[a[d]] )
       return false; //已经被占,则返回false
    for(int i=0; i<d; i++)
     if( Math.abs(a[d]-a[i])== Math.abs(i-d) )//如果第i行和第d行的Queen在同一对角线上,则返回false
          return false;
     return true;
    }

   private void output(){
     int i;
     total++;
     System.out.print("No" +total +":  ");
     for(i=0; i<n; i++)
        System.out.print(a[i]+1 +" ");
     System.out.println();
    }

    public int getTotal(){
     return total;
   }

   private void dfs(int d){
     if( d>=n ){ //找到一个解并输出
        output();
        return;
     }
     for(int i=0; i<n; i++){ //每一行均有n种放法
        a[d] = i; //第d行的Queen放在第i列
        if(can(d)){
          visited[i] = true;
          dfs(d+1); //如果第d行的方法可行,就放下一行
          visited[i] = false;//恢复现场
        }
      }
   }
}

 


运行:
D:\java>java   Queen
No1:  1 5 8 6 3 7 2 4
No2:  1 6 8 3 7 4 2 5
No3:  1 7 4 6 8 2 5 3
No4:  1 7 5 8 2 4 6 3
No5:  2 4 6 8 3 1 7 5
No6:  2 5 7 1 3 8 6 4
No7:  2 5 7 4 1 8 6 3
..........................
92

二、深度优先搜索框架二(栈实现)流程如下:


例:深度优先搜索之迷宫问题

import java.util.Stack;
////////////////////////////////////////////////
//深度优先搜索之迷宫问题
public class MazeDsf{
  private static final int M=9;
  private static final int N=8;
  
 //迷宫矩阵,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 } };  


    //标记数组,初始化为false
    boolean visited[][];

    public MazeDsf(){
       visited=new boolean[M][N];
       
    }

   //节点
   class  Node{
     int x;
     int y;
     Node(int i,int j){
       x = i;
       y = j;
    }
  }


/*坐标系统
0
----------------->y
|
|
|
|
|
V
x
*/


  //右下上左
  private int x_off[] = {0,1,-1,0};
  private int y_off[] = {1,0,0,-1};

 //输出状态
 private void PrintVisited(){
   
   for(int i = 0; i < M; ++i){
     for(int j = 0; j < N; ++j)
       System.out.print(visited[i][j]+"     ");
    System.out.println();
  }
}

   //输出迷宫
 private void PrintMatrix(){
    System.out.println("入口(0,0),出口(8,7)的迷宫,0为通道,1为障碍:");
   for(int i = 0; i < M; ++i){
     for(int j = 0; j < N; ++j)
       System.out.print(Matrix[i][j]);
    System.out.println();
  }
}
  //输出一条路径
  //由于入栈路径是正序,要倒过来输出才是从入口到出口的路劲
  private void PrintPath(Stack<Node> s){
    System.out.println("一条迷宫路径:");
    Stack<Node> t=new Stack<Node>();
    while(!s.empty()){
      t.push(s.pop());
      
    }
    while(!t.empty()){
     System.out.print("("+t.peek().x+","+t.peek().y+")->");
     t.pop();
    }
    
    System.out.println();
}

 //深度优先搜索一条可能的路径
  private void DFS(){

  //1.初始化栈
  Stack<Node> s=new Stack<Node>();
  Node start=new Node(0,0);
  s.push(start);
  visited[0][0] = true;
  while(!s.empty()){
    
   //2.取得栈顶元素(注意不从栈内删除)
   Node top = s.peek();
   //3.遍历栈顶元素的邻节点
  
   int i=0;
   for(i = 0; i<4; ++i){ //右下上左
      int nx = top.x + x_off[i];
      int ny = top.y + y_off[i];
      if(nx >= 0 && nx < M && ny>=0 && ny< N &&!visited[nx][ny] && Matrix[nx][ny] == 0){
  
         //4.把满足条件的元素标记为已处理,并压入栈内
         Node newNode=new Node(nx,ny);
         visited[nx][ny] = true;
         s.push(newNode);
         //找到出口,终止搜索
         if(nx == 8 && ny == 7){
           //输出找到的路径
           PrintPath(s); 
           return;
        }
        break;
      }
   }
   //5.当前节点没有满足条件的邻节点,把当前栈顶元素删除
   if(i == 4){
     s.pop();
   }
 }
}



  //测试代码主函数
  public static void main(String args[]) { 
     MazeDsf maze=new MazeDsf();
     maze.PrintMatrix();
     maze.DFS();
   }
}

运行:
D:\java>java   MazeDsf
入口(0,0),出口(8,7)的迷宫,0为通道,1为障碍:
01111111
00000000
01111010
00000010
01000010
01011010
01000011
01001000
01111100
一条迷宫路径:
(0,0)->(1,0)->(1,1)->(1,2)->(1,3)->(1,4)->(1,5)->(2,5)->(3,5)->(4,5)->(5,5)->(6,
5)->(7,5)->(7,6)->(7,7)->(8,7)
  • 大小: 27.7 KB
分享到:
评论

相关推荐

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

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

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

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

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

    这篇博文“深度优先搜索学习五例之五(JAVA)”可能介绍了DFS在解决实际问题中的应用,尽管描述中没有给出具体细节,但我们可以从一般的角度来探讨DFS以及其在Java中的实现。 DFS的基本思想是从根节点开始,沿着某...

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

    通常,这样的教程会包括代码实现、步骤解析以及为什么选择BFS而不是深度优先搜索(Depth-First Search, DFS)的原因。 【标签】:“源码”、“工具” “源码”标签表明文章会包含实际的Java代码示例,读者可以参考...

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

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

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

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

    JAVA算法100例

    - **深度优先搜索(DFS)**:递归地探索节点的邻接节点,用于遍历或搜索图。 - **广度优先搜索(BFS)**:使用队列数据结构,按照距离从起点到终点的顺序访问节点。 4. **动态规划(DP)**: - **斐波那契数列**:使用...

    JAVA算法100例,全源码.zip

    2. **搜索算法**:如线性搜索、二分查找、深度优先搜索(DFS)、广度优先搜索(BFS)等,这些是解决查找问题的基础,对于理解数据结构至关重要。 3. **图论算法**:例如Dijkstra最短路径算法、Floyd-Warshall所有对...

    华为机考100例java.rar

    9. **DFS(深度优先搜索)算法**:DFS是一种用于遍历或搜索树或图的算法,沿着树的深度遍历树的节点,尽可能深地搜索树的分支。在Java中,DFS可以借助于递归或栈来实现。 这些知识点涵盖了计算机科学基础和算法设计...

    java经典算法40例+答案

    2. **搜索算法**:二分查找、线性查找、深度优先搜索(DFS)和广度优先搜索(BFS),这些算法在处理数据集合时非常实用。 3. **图论算法**:Dijkstra最短路径算法、Floyd-Warshall所有对最短路径算法,它们在网络...

    [java软件技术文档doc]java经典算法40例

    2. **搜索算法**:二分查找、深度优先搜索、广度优先搜索等,探讨如何在数据结构中高效地查找目标元素。 3. **数据结构**:栈、队列、链表、树、图等,如何利用它们来实现各种算法。 4. **动态规划**:如斐波那契...

    数据结构与算法分析Java语言描述第三版书中例题源代码(Mark·Allen·Weiss著)

    这些代码可能包括简单的排序算法(冒泡、选择、插入、快速、归并等)、查找算法(顺序、二分、哈希等)、图算法(深度优先搜索、广度优先搜索、最小生成树、最短路径等)以及其他复杂的数据结构实现。 5. **学习...

    java实现的求迷宫最短路径算法

    这个类可能实现了A*算法、Dijkstra算法或者深度优先搜索(DFS)等常见的寻找最短路径的算法。这些算法的核心目标是找到从起点到终点的最短路径,同时尽量避免无效的探索。 以A*算法为例,它结合了Dijkstra算法的...

    java 对文件夹目录进行深度遍历实例代码

    深度遍历(又称深度优先遍历)是指沿着树的深度遍历树的节点,尽可能深地搜索树的分支,当节点v的所有出边都已被探寻过,搜索将回溯到发现节点v的那条边的起始节点。在目录结构中,这意味着如果当前遍历到的文件是...

    java2课程设计源代码大全

    在实现这个项目时,我们可能需要学习图算法,如深度优先搜索(DFS)或广度优先搜索(BFS),用于寻找从起点到终点的最短路径。数据结构如栈或队列会在这里发挥重要作用。同时,我们需要理解如何将迷宫表示为二维数组...

    [电子书][Java类]JAVA经典算法42例

    2. **搜索算法**:二分查找、深度优先搜索(DFS)、广度优先搜索(BFS)等,这些算法在处理数据查找和遍历树形结构时非常有效。 3. **图论算法**:最短路径问题(Dijkstra算法、Floyd算法),最小生成树(Prim算法...

    轮廓问题的java实现

    这可能需要使用图遍历算法,如深度优先搜索(DFS)或广度优先搜索(BFS)。 3. **文件输入与输出**: - 输入通常包含每个建筑物的长、宽、高和位置信息,可能以CSV、JSON或其他格式存储。Java的`Scanner`类可用于...

    JAVA经典算法收集整理 以及Java算法大全(近100种算法打包).rar

    2. **搜索算法**:如二分查找、深度优先搜索(DFS)、广度优先搜索(BFS)。这些算法在处理大量数据时具有重要作用,如在树和图结构中寻找特定元素或路径。 3. **图论算法**:如Dijkstra最短路径算法、Floyd-...

    Java经典算法(包你们划算)

    3. **图论算法**:如深度优先搜索(DFS)和广度优先搜索(BFS),以及Dijkstra最短路径算法、Floyd-Warshall所有对最短路径算法等。 4. **动态规划**:解决许多复杂问题的有效方法,如背包问题、最长公共子序列、...

Global site tag (gtag.js) - Google Analytics