Первый поиск по ширине и первый поиск по глубине

Question

Кто-нибудь может дать ссылку для простого объяснения BFS и DFS с его реализацией?

Answer 1

BFS и DFS применимы ко всем видам графиков. Я объясняю это только для двоичного дерева. BFS посещают каждый узел сверху вниз, слева направо. Например для этого:

       1
      / \
     7   9
     \  / \
      8 2 3

BFS дает нам: 1 7 9 8 2 3. DFS сначала посещает глубину каждой ветви. Затем он возвращается к своим родителям. Вы можете следовать этому неформальному правилу. Сначала левый потом, потом правый потом потом родитель. Но вы должны начать с глубины каждой ветви. Например, здесь вы начинаете с 8, так как для 7. нет левого потомка. Затем вы посещаете родитель 7. Затем будет посещен 1 родитель из 7. Затем вы идете к правой ветви. Но на этот раз есть 2, как самый левый ребенок. Итак, вы посещаете 2 (слева ребенка), затем, справа ребенка 3, а затем, 9 их родителей. Итак, DFS дает нам 8 7 1 2 9 3. Это реализация:

import java.util.ArrayList;
import java.util.List;

public class TreeTraverse {

    static class Node{
        Node(int data){
            this.data = data;
            this.left = null;
            this.right = null;
            this.visited = false;
        }
        int data;
        Node left;
        Node right;
        boolean visited;
    }

    public static void main(String[] args) {
        //The tree:
        //   1
        //  / \
        // 7   9
        // \  / \
        //  8 2 3

        Node node1 = new Node(1);
        Node node7 = new Node(7);
        Node node9 = new Node(9);
        Node node8 = new Node(8);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        node1.left = node7;
        node1.right = node9;
        node7.right = node8;
        node9.right = node3;
        node9.left = node2;
        System.out.println("DFS: ");
        depthFirstSearch(node1);
        System.out.println("\nBFS: ");
        breadthFirstSearch(node1);

    }

    private static void depthFirstSearch(Node node){
        if(node.left == null && node.right == null){
            System.out.print(node.data+" ");
            node.visited = true;
        }else if(node.left == null || node.left.visited){
            depthFirstSearch(node.right);
            System.out.print(node.data+" ");
            node.visited = true;
        }else{
            depthFirstSearch(node.left);
            node.visited = true;
            System.out.print(node.data+" ");
            depthFirstSearch(node.right);

        }
    }

    private static void breadthFirstSearch(Node node){
        List<Node> al = new ArrayList<>();
        al.add(node);
        while(!al.isEmpty()){
            node = al.get(0);
            if(node.left != null){
                int index = al.size();
                al.add(index,node.left);
            }
            if(node.right != null){
                int index = al.size();
                al.add(index,node.right);
            }
            System.out.print(al.get(0).data+" ");
            al.remove(0);


        }
    }

}

Надеюсь, это поможет. Если вы хотите клонировать проект, пожалуйста, посетите: https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TreeTraverse.java. Надеюсь, это поможет.