Грокаем алгоритмы. Графы и поиск в ширину. Часть 9

Заметки:

1. Breadth-First-Search (BFS) — алгоритм, работающий с графами.
2. Поиск в ширину позволяет найти кратчайшее расстояние между двумя объектами.
3. Граф моделирует набор связей. Он состоит из узлов и ребер. Узел может быть напрямую соединен с несколькими другими узлами. Эти узлы называются соседями.
4. Поиск в ширину помогает ответить на вопросы "Существует ли путь от точки А к точке В?" и "Как выглядит кратчайший путь от точки А к точке В?"
5. Сначала проверяем связи первого уровня (ближайшие кружочки), а потом второго уровня (через один кружочек).
6. Проверяем всё в порядке добавления (очередь).
7. Графы реализуем через хеш-таблицу: узел — ключ и все его значения.
8. Добавлять ключи можно в любом порядке. Направленный граф — отношения действуют только в одну сторону.

Как написать алгоритм с графами:

1) Создаем очередь с проверяемыми (двусторонняя) элементами.

1) Создаем очередь с проверенными элементами (двусторонняя).

3) Проверяем, подходит ли элемент.

4) Если нет, добавляем в очередь всех его соседей.

5) Если да, завершаем.

6) Цикл.

7) Также следует проверять, что элемента нет в списке проверенных.

Теперь про интересное — время выполнения.

• Добавление в очередь выполняется за О(1).
• Выполнение для одного элемента потребует О(количество элементов).
• Поиск в ширину выполняется за О(V + E), где V — количество вершин, а E — количество ребер.

Генеалогическое древо — это тоже граф. Если у графа нет ребер, указывающих в обратном направлении, то это дерево.

Любое дерево является графом, но не наоборот.

Дубль статей в телеграмме — https://t.me/android_junior

Аналог твиттера в телеграмме — https://t.me/android_junior_notes