JAVA实现DFS、BFS

1. 前言

在计算机科学中，遍历是一种重要的算法策略，用于探索或搜索树或图的数据结构，遍历主要有两种类型：深度优先遍历（DFS）和广度优先遍历（BFS），这两种策略在处理复杂数据结构时非常有用，特别是在处理树和图结构的时候。

2. 深度优先遍历（DFS）

深度优先遍历是一种用于遍历或搜索树或图的算法。这个算法会尽可能深的搜索树的分支，当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止,如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。
以下是一个使用Java实现深度优先遍历二叉树的示例代码:

import java.util.*;  
  
class Node {  
    int data;  
    Node left, right;  
  
    public Node(int item) {  
        data = item;  
        left = right = null;  
    }  
}  
  
class BinaryTree {  
    Node root;  
  
    void dfs(Node node) {  
        if (node == null) {  
            return;  
        }  
        System.out.print(node.data + " "); //访问节点  
        dfs(node.left); //递归左子树  
        dfs(node.right); //递归右子树  
    }  
}

在这个例子中，我们首先创建一个节点类（Node），每个节点都有一个数据元素和两个指向其子节点的指针，然后我们创建了一个二叉树类（BinaryTree），其中包含一个根节点和一个dfs方法，该方法用于执行深度优先遍历，如果节点为空，我们直接返回，否则，我们首先访问该节点，然后递归地遍历其左子树和右子树。

3. 广度优先遍历（BFS）

广度优先遍历是一种图遍历算法，它从图的根（对于无向图来说是任意节点）开始并探索邻近的节点，然后逐步向外扩展，广度优先搜索使用队列数据结构来保存待访问的节点。访问顺序是：先访问根，然后是根的所有未被访问过的邻居，然后是这些邻居的所有未被访问过的邻居，依此类推。因此，广度优先遍历也被称为层次遍历。
以下是一个使用Java实现广度优先遍历二叉树的示例代码：

import java.util.*;  
  
class Node {  
    int data;  
    Node left, right;  
  
    public Node(int item) {  
        data = item;  
        left = right = null;  
    }  
}  
  
class BinaryTree {  
    Node root;  
    Queue<Node> queue = new LinkedList<Node>();   
    
    void bfs(Node node) {   
        if (node == null)   
            return;   
       queue.add(node);   
   }   
   while (!queue.isEmpty()) {   
       Node tempNode = queue.poll();   
       System.out.print(tempNode.data + " "); //访问节点   
       if (tempNode.left != null)   
           queue.add(tempNode.left);   
       if (tempNode.right != null)   
           queue.add(tempNode.right);   
   }   
}

在这个例子中，我们首先创建一个与深度优先遍历相同的节点类（Node），然后我们创建了一个二叉树类（BinaryTree），其中包含一个根节点、一个队列和一个bfs方法，该方法用于执行广度优先遍历。在bfs方法中，我们首先将根节点添加到队列中。然后，只要队列不为空，我们就从队列中取出一个节点，访问它，并将其子节点添加到队列中。这样就可以确保我们首先访问根节点的所有邻居，然后再访问这些邻居的邻居，依此类推。