Поиск в ширину (BFS, Breadth-first search) — метод обхода и разметки вершин графа.
Поиск в ширину выполняется в следующем порядке: началу обхода s приписывается метка 0, смежным с ней вершинам — метка 1. Затем поочередно рассматривается окружение всех вершин с метками 1, и каждой из входящих в эти окружения вершин приписываем метку 2 и т. д.
Если исходный граф связный, то поиск в ширину пометит все его вершины. Дуги вида (i, i+1) порождают остовный бесконтурный орграф, содержащий в качестве своей части остовное ордерево, называемое поисковым деревом.
Легко увидеть, что с помощью поиска в ширину можно также занумеровать вершины, нумеруя вначале вершины с меткой 1, затем с меткой 2 и т. д.
Содержание [убрать]
1 Реализация
2 Практические применения
3 Ссылки
4 Литература
[править] Реализация
Поиск в ширину реализуется с помощью структуры очередь. Для этого занесем в очередь исходную вершину. Затем будем работать, пока очередь не опустеет, таким образом: выберем элемент из очереди и добавим все смежные ему элементы, которые еще не использованы. Пример реализации на Паскале для дерева:
push(start);
while not empty do
begin
tek:=pop;
for i:=1 to n do
if (not used[a[tek,i]]) and (a[tek, i]<>0) then
begin
used[a[tek,i]]:=true;
push(a[tek,i]);
end;
end;
Пример реализации на 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 = [] #quene
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)