Для графа на рисунке 1 найдём кратчайший путь между вершинами A и F. Для достижения цели мы можем:
1. Найти все пути между данными вершинами и выбрать кратчайший
2. Выбрать кратчайший путь при достижении искомой вершины
Остановимся на 2-м варианте и применим BFS.
BSF использует очередь для обхода вершин
1. Добавим вершину А в очередь (рис. 2)
2. Заберём первый элемент из очереди, в нашем случае А, и посмотрим на соседние с ним вершины (C, D, B). Состояние очереди на рисунке 3
3. В очередь добавляем все соседние с А вершины (рисунок 4) и помечаем вершину А как посещённую (рисунок 5)
4. Из очереди забираем первый элемент - [A, C] и из него целевую вершину С.
5. Для вершины С - добавляем в очередь все соседние с ней вершины. Вершина А тоже является соседней для С но т.к. мы её уже посещали - не будем добавлять её в очередь. Состояние очереди на рисунке 6. Вершину С пометим как посещённую т.к. больше нет путей соединяющих её с другими вершинами (рисунок 7).
6. Далее забираем следующий элемент из очереди - [A, D] в качестве вершины выбираем последний элемент полученного списка - D.
7. В очередь добавляем все элементы соседствующие с D - A, E. Т.к. А в списке посещённых - пропускаем его. В очередь попадает элемент A, D, E. Состояние очереди на рисунке 8. D помечаем как посещённую вершину рисунок 9
8. Забираем из очереди следующий элемент - [A, B]. Все вершины соединённые с B (кроме А т.к. в списке посещённых) - добавляем в очередь (рис. 10). B помечаем посещённой вершиной
9. Забираем следующий элемент из очереди - [A, C, E]. В качестве вершины выбираем последний элемент из списка - E. Для E - добавляем всех не посещённых соседей в очередь (рис. 12) E помечаем посещённой вершиной (рис. 13)
10. Переходим к элементу A, D, E и его вершине E. Для неё снова добавляем путь в F (рис. 14)
11. Переходим к элементу A, B, E и его вершине E. Для неё снова добавляем путь в F (рис. 15)
12. Переходим к элементу A, B, F и его вершине F. F является искомой вершиной. Для неё снова пытаемся добавить в очередь соседей, но в данном случае все соседние вершины посещены, поэтому фиксируем найденный путь и переходим к следующему элементу в очереди рис. 16
13. Элемент A, C, E, F также содержит искомую вершину F, соответственно записываем найденный маршрут и пытаемся добавить всех не посещённых соседей F в очередь рис 17
14. Элементы A, D, E, F и A, B, E, F также зафиксируем как пути к вершине F и удалим их из очереди. После этих операций очередь опустеет, что будет означать, что мы посетили все вершины графа (рис. 18)
Итоговый список вершин помеченных как посещённые - A, C, D, B, E, F (рис. 19) Итоговый список найденных путей - [A, B, F], [A, C, E, F], [A, D, E, F], [A, B, E, F]. Минимальным, очевидно, является путь A, B, F.
Путь, который мы нашли первым был именно A, B, F. Это везение или нет?
Ответ - нет. Используя BFS мы можем быть уверены в том, что первый найденный нами путь между двух вершин - является кратчайшим.
Почему?
Мы обходим граф слоями:
- Первый слой - вершина А
- Второй - вершины C, D, B
- Третий - E
Для вершины B - третий слой - это вершины E, F и это первый раз когда мы встречаем вершину F. Все последующие обходы слоёв только удлиняют путь к вершине. Поэтому используя BFS - когда мы находим первый путь к искомой вершине, этот путь и является кратчайшим и нам не нужно продолжать выполнение. По этой причине BFS эффективнее DFS в задаче поиска кратчайшего пути в графе.
Оценка сложности
Временная сложность - O(V + E) где V - количество вершин, E - количество рёбер. В худшем случае придётся обойти все рёбра и все вершины графа.
Пространственная сложность - O(V). В очереди будет храниться V рёбер в худшем случае. Также необходимо хранить V найденных путей в худшем случае.