Статья Автор: Лебедев Дмитрий

BFS: Способы реализации

При поиске в ширину (breadth-rst search – BFS) вершины графа посещаются в порядке возрастания расстояния от начальной вершины. Следовательно, используя поиск в ширину, мы сможем вычислить расстояния от начальной вершины до всех остальных. Однако реализовать поиск в ширину труднее, чем поиск в глубину. В процессе поиска в ширину мы обходим вершины уровень за уровнем.
Сначала посещаются вершины, отстоящие от начальной на расстояние 1, затем – на расстояние 2 и т. д. Процесс продолжается, пока не останется непосещенных вершин.
 

С помощью алгоритма BFS мы можем проверить многие свойства графа. 
BFS обычно применяют для проверки связности графа, построения компонент связности, поиск минимального пути между вершинами в графе, построения деревьев, поиска пути в лабиринте и других задачах.
При применении BFS  удобно использовать представление графа в виде компонент смежности или матрицы смежности.

 

Задача
В неориентированном графе найти компоненту связности заданной вершины. 
В графе могут быть петли и кратные ребра.
Входные данные: В первой строке записаны сначала два числа N, M и start, задающие соответственно количество вершин, количество ребер и стартовую вершину ( вершины нумеруются от 0 до N-1), а затем перечисляются ребра. Каждое ребро задается двумя номерами вершин, которые оно соединяет.
Выходные данные: Состав компоненты связности (в произвольном порядке)
Ниже приведено возможное решение (Программа BFS-01) этой задачи. Граф задан списком ребер, поэтому при решении используется словарь.
Использование словаря позволяет решать задачу для "нечисловых" графов и "сильно разряженных" графов.
Замечание: для  que можно использовать структуру Queue  (очередь) модуля queue (экономии памяти), Это будет сделано в следующем примере 
Проверьте это решение на следующием наборе данных.
8 7 1
1 2
2 3
3 4
4 1
5 6
6 7
0 7
 


В некоторых случаях алгоритм BFS необходимо применять "по шагам"  (например, для нахождения и обработки очередного "уровня").
Для этого на вход подпрограмме будет "подаваться" очередь вершин для обработки, а подпрограмма будет возвращать список найденных вершин (вершин уровня) 
Задача
В ориентированном графе требуется найти длину кратчайшего пути между двумя вершинами. 
Формат входных данных
В первой строке входных данных записано число M - число ребер в графе. В следующих M строках  идет описание ребер.
Каждое ребро задается двумя словами, которые она соединяет. В последней строке записаны описание двух вершин - начальной и конечной. 
Формат входных данных 
Выведите длину кратчайшего пути. Если пути не существует, выведите одно число -1.
В данной задаче граф задан списком ребер с "неизвестным" составом вершин, поэтому для описания компонент смежности будет использоваться словарь, а алгоритм BFS будет состоять из реализации отдельных шагов.
Проверьте работу программы на примере с 6 ребрами
6
коза коса 
коза кора 
коса коза 
коса роса 
роса коса 
кора коза 
роса кора 


Примеры показывают, что алгоритма BFS можно запускать сразу из нескольких стартовых вершин. 
Алгоритм BFS позволяет не только находить минимальный путь из вершину в вершину, но и определять количество таких путей.
 

Описание компонент связности графа может быть словесным или задаваться функцией (список вершин также может быть очень большим или неопределенным).
Задача "Конь Иосиф спешит в школу"
Известно, что на бесконечном шахматном поле, конь может перейти с любого поля на любое.
Как обычно, конь Иосиф опаздывает в школу и хочет попасть туда как можно быстрее.
Помогите Иосифу добраться до школы за минимальное число ходов (конь передвигается по правилам шахматного коня)
Входные данные
Четыре числа в строчку - координаты стартовой и финальной точки (координаты точек не совпадают)
Выходные данные 
Минимальное количество ходов для перехода из стартовой точки в финальную.

При решении задачи будем использовать словарь для хранения расстояний и структуру очередь.
Для получения компонент связности создадим подпрограмму next
 


Добавив в программу BFS-03 "пару операторов" можно оценить максимальный объём очереди (получить размер очереди можно через метод qsize() ). 
Для поиска "0 0 100 100"  минимальный путь будет равен 68, а максимальная очередь будет иметь размер равный  1869
Алгоритм BFS позволяет не только найти минимальный путь, но и определить количество минимальных путей
Модифицируем программу BFS-03 так, чтобы она находила и количество минимальных путей. 
Для этого в словарь расстояний будем добавлять количество путей. Также необходимо изменить "правило завершения" - необходимо закончить обработку всего уровня.


Ещё одна стандартная задача - нахождение "минимального пути". 
Для её решения достаточно добавлять в словарь расстояний номер вершины, из которой в неё пришли. 
После нахождения минимального расстояния, путь можно восстановить методом "обратного хода".
Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация
Печать