Поиск кратчайшего пути между двумя вершинами с помощью BFS

Рис. 1 - Граф

Для графа на рисунке 1 найдём кратчайший путь между вершинами A и F. Для достижения цели мы можем:

1. Найти все пути между данными вершинами и выбрать кратчайший
2. Выбрать кратчайший путь при достижении искомой вершины

Остановимся на 2-м варианте и применим BFS.

BSF использует очередь для обхода вершин

1. Добавим вершину А в очередь (рис. 2)

Рис. 2

2. Заберём первый элемент из очереди, в нашем случае А, и посмотрим на соседние с ним вершины (C, D, B). Состояние очереди на рисунке 3

Рис. 3

3. В очередь добавляем все соседние с А вершины (рисунок 4) и помечаем вершину А как посещённую (рисунок 5)

Рис. 4

Рис. 5

4. Из очереди забираем первый элемент - [A, C] и из него целевую вершину С.

5. Для вершины С - добавляем в очередь все соседние с ней вершины. Вершина А тоже является соседней для С но т.к. мы её уже посещали - не будем добавлять её в очередь. Состояние очереди на рисунке 6. Вершину С пометим как посещённую т.к. больше нет путей соединяющих её с другими вершинами (рисунок 7).

Рис. 6

Рис. 7

6. Далее забираем следующий элемент из очереди - [A, D] в качестве вершины выбираем последний элемент полученного списка - D.

7. В очередь добавляем все элементы соседствующие с D - A, E. Т.к. А в списке посещённых - пропускаем его. В очередь попадает элемент A, D, E. Состояние очереди на рисунке 8. D помечаем как посещённую вершину рисунок 9

Рис. 8

Рис. 9

8. Забираем из очереди следующий элемент - [A, B]. Все вершины соединённые с B (кроме А т.к. в списке посещённых) - добавляем в очередь (рис. 10). B помечаем посещённой вершиной

Рис. 10

Рис. 11

9. Забираем следующий элемент из очереди - [A, C, E]. В качестве вершины выбираем последний элемент из списка - E. Для E - добавляем всех не посещённых соседей в очередь (рис. 12) E помечаем посещённой вершиной (рис. 13)

Рис. 12

Рис. 13

10. Переходим к элементу A, D, E и его вершине E. Для неё снова добавляем путь в F (рис. 14)

Рис. 14

11. Переходим к элементу A, B, E и его вершине E. Для неё снова добавляем путь в F (рис. 15)

Рис. 15

12. Переходим к элементу A, B, F и его вершине F. F является искомой вершиной. Для неё снова пытаемся добавить в очередь соседей, но в данном случае все соседние вершины посещены, поэтому фиксируем найденный путь и переходим к следующему элементу в очереди рис. 16

Рис. 16

13. Элемент A, C, E, F также содержит искомую вершину F, соответственно записываем найденный маршрут и пытаемся добавить всех не посещённых соседей F в очередь рис 17

Рис. 17

14. Элементы A, D, E, F и A, B, E, F также зафиксируем как пути к вершине F и удалим их из очереди. После этих операций очередь опустеет, что будет означать, что мы посетили все вершины графа (рис. 18)

Рис. 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 в задаче поиска кратчайшего пути в графе.

Рис. 19

Рис. 20

Оценка сложности

Временная сложность - O(V + E) где V - количество вершин, E - количество рёбер. В худшем случае придётся обойти все рёбра и все вершины графа.

Пространственная сложность - O(V). В очереди будет храниться V рёбер в худшем случае. Также необходимо хранить V найденных путей в худшем случае.