Наконец после долгого вступления (1, 2) добрались и до самих алгоритмов. Первый на очереди – алгоритм обхода в ширину.
Описание:
Алгоритм обхода в ширину (Breadth first search, BFS) применяется для поиска кратчайшего пути в НЕВЗВЕШЕННЫХ графах. При этом кратчайшим путем он считает путь с наименьшим числом ребер.
Суть алгоритма в последовательном осмотре всех вершин начиная со «стартовой». Происходит это следующим образом: Сначала осматриваем соседей стартовой вершины, затем в качестве стартовой принимаем первого соседа и так до тех пор, пока не осмотрим все вершины.
В данной реализации мы просто посетим все вершины в ДАННОЙ компоненте связности и можем посчитать их количество: print(len(visited)).
Как теперь найти путь?
Используем алгоритм обратного восстановления пути:
В нем все строиться на идее запоминания вершин из которых мы пришли в текущую и обратного движения от текущей в стартовую. Несмотря на простоту описания смысл доходит не сразу (это я про себя).
Модифицируем принцип действия, описанный выше, заодно дополним счетчиком расстояний:
Программная реализация
Для закрепления "как искался путь":
Алгоритмическая сложность
В описанной выше реализации мы полностью исследуем граф, т.е. проходимся по всем вершинам и всем ребрам отсюда временная сложность алгоритма
О(|V|+|E|), где |V|— число вершин, |E|— число рёбер.
Но при этом мы имеем уже полностью просчитанный граф для исходной вершины и можем восстановить путь из нее для любой другой.
Данный случай стоит воспринимать как худший – полный обход графа
Соответственно для ускорения работы алгоритма можно добавить условие остановки алгоритма при достижении искомой вершины:
По памяти нам так же требуется О(|V|+|E|)
Что дает данный алгоритм?
1. Кратчайший путь – кратчайший по количеству ребер
2. Поиск компонент связности (если забыл что это тебе сюда).
Для проверки числа КС нам требуется создать не пустой лист visited со значениями False ( их должно быть ровно |V|) и при работе алгоритма менять соответствующее по номеру вершины значение на True. Если после работы алгоритма в списке будут значения False, то просто ещё раз запускаем от этих вершин алгоритм. Т.о. количество запусков алгоритма = количеству компонент связности.
3. Остовное дерево(об этом буду говорить в следующих статьях)
P.S.
Немного поиграв с библиотекой pygame, получилось сделать такую анимацию работы алгоритма:
