Поиск в ширину

Порядок обхода дерева в ширину

Поиск в ширину (BFS, Breadth-first search) — метод обхода и разметки вершин графа.

Поиск в ширину выполняется в следующем порядке: началу обхода s приписывается метка 0, смежным с ней вершинам — метка 1. Затем поочередно рассматривается окружение всех вершин с метками 1, и каждой из входящих в эти окружения вершин приписываем метку 2 и т. д.

Если исходный граф связный, то поиск в ширину пометит все его вершины. Дуги вида (i, i+1) порождают остовный бесконтурный орграф, содержащий в качестве своей части остовное ордерево, называемое поисковым деревом.

Легко увидеть, что с помощью поиска в ширину можно также занумеровать вершины, нумеруя вначале вершины с меткой 1, затем с меткой 2 и т. д.

Реализация

Поиск в ширину реализуется с помощью структуры очередь. Для этого занесем в очередь исходную вершину. Затем будем работать, пока очередь не опустеет, таким образом: выберем элемент из очереди и добавим все смежные ему элементы, которые еще не использованы.

Пример реализации на Python для любого графа

Аргументами функции BFS(G, s) является граф G, представленный в виде [N,E], где N — количество узлов в графе, E — список ребер в виде [[a,b], [b, c]…], где не важно как обозначаются узлы — строками или числами, и s — название вершины из которой начинаем поиск. Функция возвращает кортеж из двух списков: p — содержит имена родительских элементов для узлов в дереве поиска в ширину, d — содержит расстояния от узла s.

def BFS(G, s):
        color, d, p = {}, {}, {}
        for u in [x for x in range(G[0]) if x != s]:
                color[u], d[u], p[u] = "white", "inf", None
        color[s], d[s], p[s] = "gray", 0, None
        Q = [] # queue
        Q.append(s)
        while Q != []:
                u = Q.pop(0)
                for v in [x[1] for x in G[1] if x[0] == u]:
                        if color[v] == "white":
                                color[v], d[v], p[v] = "gray", d[u] + 1, u
                                Q.append(v)
                color[u] = "black"
        return (p, d)

Алгоритмы поиска на графах
A* B* Алгоритм Беллмана — Форда Двунаправленный поиск Алгоритм Дейкстры Алгоритм Джонсона Поиск в ширину Поиск в глубину Поиск с ограничением глубины Поиск по первому наилучшему совпадению Алгоритм Флойда — Уоршелла

Практические применения

• Волновой алгоритм в трассировке печатных плат;
• Поиск увеличивающего пути в алгоритме Форда-Фалкерсона (алгоритм Эдмондса-Карпа)

Ссылки

• http://pco.iis.nsk.su/grapp/WIN/sl_p.html
• Реализация поиска в ширину и различные задачи, решаемые с его помощью (сайт e-maxx.ru)

Литература

• Ананий В. Левитин Глава 5. Метод уменьшения размера задачи: Поиск в ширину // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 215-218. — ISBN 0-201-74395-7
• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1