Изменения

Перейти к: навигация, поиск

Обход в ширину

846 байт убрано, 18:19, 6 ноября 2018
м
Переформатировано описание
Пусть задан невзвешенный ориентированный граф <tex> G = (V, E) </tex>, в котором выделена исходная вершина <tex>s</tex>. Требуется найти длину кратчайшего пути (если таковой имеется) от одной заданной вершины до другой. Частным случаем указанного графа является невзвешенный неориентированный граф, т.е. граф, в котором для каждого ребра найдется обратное, соединяющее те же вершины в другом направлении.
Для алгоритма нам потребуются [[Очередь|очередь]], которая сначала содержит только <tex> s </tex>, и множество посещенных вершин <tex> X was </tex>, которое которые изначально тоже содержит только содержат одну вершину <tex> s </tex>. На каждом шаге шагу алгоритм вынимает берет из начала очереди вершину, рассматривает все исходящие из нее ребра <tex> v </tex> и добавляет все связанные непосещенные смежные с ней непосещенные <tex> v </tex> вершины в <tex> X was </tex> и в конец очереди. Если очередь пуста, то алгоритм завершает работу.
Поиск в ширину также может построить [[Дерево, эквивалентные определения|дерево]] поиска в ширину. Изначально оно состоит из одного корня <tex> s </tex>. Когда мы добавляем непосещенную вершину в очередь, то добавляем ее и ребро, по которому мы до нее дошли, в дерево. Поскольку каждая вершина может быть посещена не более одного раза, она имеет не более одного родителя. После окончания работы алгоритма для каждой достижимой из <tex> s </tex> вершины <tex> t </tex> путь в дереве поиска в ширину соответствует кратчайшему пути от <tex> s </tex> до <tex> t </tex> в <tex> G </tex>.
 
Также можно для каждой вершины <tex> t \in V </tex> считать длину этого пути, равную <tex> d[t] </tex>. Можно считать, что для непосещенных вершин эта длина бесконечно велика. Тогда на каждом шаге длина пути до <tex> t </tex> равна <tex> \rho(s, t) </tex>, если <tex> t </tex> посещена и <tex> \infty </tex> в противном случае. Отсюда следует, что если на каждом шаге обновлять длины путей, то информация о множестве <tex> X </tex> является избыточной, и его можно не хранить.
== Анализ времени работы ==
Расстояние до <tex> u </tex> найдено некорректно, поэтому <tex> \rho(s, u) < d[u] </tex>. Подставляя сюда два последних равенства, получаем <tex> d[w] + 1 < d[v] + 1 </tex>, то есть, <tex> d[w] < d[v] </tex>. Из ранее доказанной леммы следует, что в этом случае вершина <tex> w </tex> попала в очередь и была обработана раньше, чем <tex> v </tex>. Но она соединена с <tex> u </tex>, значит, <tex> v </tex> не может быть предком <tex> u </tex> в дереве обхода в ширину, мы пришли к противоречию, следовательно, найденные расстояния до всех вершин являются кратчайшими.
}}
 
== Дерево обхода в ширину ==
 
Поиск в ширину также может построить [[Дерево, эквивалентные определения|дерево]] поиска в ширину. Изначально оно состоит из одного корня <tex> s </tex>. Когда мы добавляем непосещенную вершину в очередь, то добавляем ее и ребро, по которому мы до нее дошли, в дерево. Поскольку каждая вершина может быть посещена не более одного раза, она имеет не более одного родителя. После окончания работы алгоритма для каждой достижимой из <tex> s </tex> вершины <tex> t </tex> путь в дереве поиска в ширину соответствует кратчайшему пути от <tex> s </tex> до <tex> t </tex> в <tex> G </tex>.
== Реализация ==
54
правки

Навигация