В моем предыдущем посте я рассмотрел поиск в глубину (DFS) для поиска на графике. Здесь я хотел бы рассказать о поиске в ширину (BFS) и показать разницу. Обратите внимание, мой код и примеры будут на Java.

Поиск в глубину максимально углубляется в дерево или граф при переборе. Примером может служить следующее дерево:

    4
   / \
  2   5
 / \   \
0   1   8
   /   / 
  7   10

Алгоритм DFS сначала пройдет весь путь до узла 7 в дереве, прежде чем перебирать остальные узлы. DFS переходит к самой глубокой части дерева на каждой итерации.

Алгоритм BFS сначала просматривает дочерние узлы узла дерева или смежные узлы в графе. Затем, после просмотра, они углубляются в дерево или график, на следующий уровень и т. д. Это особенно полезно, когда вы рассматриваете алгоритмы для сайтов социальных сетей. Много раз на сайтах социальных сетей люди хотят видеть, есть ли кто-то в друзьях их друга. Подход DFS будет проходить через все дружеские отношения один за другим, и это потенциально может занять очень много времени. Подход BFS будет проходить по списку друзей и, просмотрев каждого друга, переходить на следующий уровень вниз. Как правило, социальные группы и т. д. хорошо связаны между собой, поэтому есть вероятность, что ваши друзья или друзья друзей находятся всего в одной или двух группах.

Так как это работает?

Обычно алгоритм BFS использует очередь. Он проходит по дереву или графу, начиная с корневого узла. Затем он просматривает дочерние или смежные узлы с этим корнем, затем просматривает их дочерние или смежные узлы и т. д. и т. д.

Чтобы показать этот процесс, вы обычно начинаете с реализации класса Node. Код здесь предполагает древовидную структуру, но вы могли бы так же легко сохранить список смежности, если бы вы искали граф.

public class Node {
    int value;
    Node left;
    Node right;

    public Node(int v) {
        value = v;
    }
}

Затем вы будете строить соединения либо через дочерние, либо через соседние узлы. Поскольку я использую древовидную структуру, я собираюсь создать дочерние узлы (это соответствует дереву, которое я показал выше):

// create nodes
Node root = new Node(4);
Node child2 = new Node(2);
Node child5 = new Node(5);
Node child0 = new Node(0);
Node child1 = new Node(1);
Node child8 = new Node(8);
Node child7 = new Node(7);
Node child10 = new Node(10);

// establish relationships
root.left = child2;
root.right = child5;
child2.left = child0;
child2.right = child1;
child5.right = child8;
child1.left = child7;
child8.left = child10;

Теперь, если вы хотите выполнить поиск в этом дереве с помощью DFS, вы должны сделать что-то вроде следующего:

public static void printDFS(Node root) {
        if(root == null) {
            return;
        }

        System.out.println(root.value);
        if(root.left != null) {
            printDFS(root.left);
        }
        if(root.right != null) {
            printDFS(root.right);
        }
    }

вывод выполнения этого на дереве, которое я создал, выглядит следующим образом:

4
2
0
1
7
5
8
10

Если вы заметили, узел 7 был напечатан перед узлом 10, потому что алгоритм проходил весь путь вниз по дереву при каждом запуске. Следует также отметить, что этот подход может быть реализован итеративно, а не рекурсивно. Я использую рекурсивную реализацию, потому что считаю ее более простой и элегантной.

Так что теперь, если вы возьмете то же самое дерево, но захотите найти его с помощью BFS, вы должны сделать что-то вроде следующего:

public static void printBFS(Node root) {
        LinkedList<Node> queue = new LinkedList<Node>();
        queue.add(root);

        while(queue.size() > 0) {
            Node node = queue.remove();
            System.out.println(node.value);
            if(node.left != null) {
                queue.add(node.left);
            }
            if(node.right != null) {
                queue.add(node.right);
            }
        }
    }

Результат запуска этого метода будет выглядеть следующим образом:

4
2
5
0
1
8
7
10

Если вы заметили, узлы 7 и 10 теперь отображаются в конце. Дети каждого уровня печатаются первыми, прежде чем идти вниз по дереву.

Еще один трюк, который вы могли бы сделать, — распечатать эти значения на месте. По существу печать на каждом уровне. Это довольно легко сделать, вам просто нужно отслеживать размер очереди каждый раз, когда вы добавляете дочерние элементы, как показано ниже:

public static void printBFSTreeLevel(Node root) {
        LinkedList<Node> queue = new LinkedList<Node>();
        queue.add(root);

        while(queue.size() > 0) {
            int queueSize = queue.size();
            for(int i = queueSize; i > 0; i--) {
                Node node = queue.remove();
                System.out.print(node.value + " ");
                if(node.left != null) {
                    queue.add(node.left);
                }
                if(node.right != null) {
                    queue.add(node.right);
                }
            }
            System.out.println();
        }
    }

Вывод этого метода будет выглядеть следующим образом:

4 
2 5 
0 1 8 
7 10

Если вы заметили, здесь узлы дерева печатаются на каждом уровне.

Итак, я надеюсь, что этот пост показал вам основы BFS и DFS. Я надеюсь, что это также показало вам, как BFS может быть полезен в некоторых случаях в зависимости от ваших данных и варианта использования.

Первоначально опубликовано на https://rhythmandbinary.com 23 апреля 2019 г.