Изменения

'''Обход в ширину''' ('''Поиск в ширину''', 'англ. ''BFS''', '''Breadth-first search''') — один из простейших алгоритмов обхода графа, являющийся основой для многих важных алгоритмов для работы с графами.

В приведенном Предложенная ниже псевдокоде функция возвращает расстояние между вершинами <tex> G = (V, E) source </tex> - входной граф, и <tex> target </target>. <tex> s E</tex> - выделенная вершинасписок ребер, Q - очередь. Множество <tex> X </tex> не хранится, вместо него используются расстояния в дереве обхода в ширину; . ЗаметимЮ что расстояние от вершины <tex>ssource</tex> до вершины <tex>u</tex>, вычисляемое алгоритмом, хранится в поле <tex>d[u]</tex>.

'''int''' '''BFS'''(E: '''list'''<tex>G</tex'''int''', '''int'''>, source: '''int''', destination: '''int''') d.fill(<tex>s\infty </tex>) 1 d[ssource] <tex> \leftarrow </tex> = 0 2 Q = <tex> \leftarrow \emptyset varnothing </tex> 3 Q.push(ssource) 4 '''while''' Q <tex> \ne \emptyset varnothing </tex> 5 '''do''' u <tex> \leftarrow </tex> q = Q.pop() 6 '''for''' <q, v: uv <tex> \in </tex> E 7 '''doin''' E '''if''' d[v] == <tex> \infty </tex> 8 '''then''' d[v] <tex> \leftarrow </tex> = d[uq] + 1 9 Q.push(v) '''return''' d[destination]

== Ссылки Источники информации ==

* [http[wikipedia:en:Breadth-first_search| Wikipedia {{---}} Breadth-first search]]* [[wikipedia://ru.wikipedia.org/wiki/:Поиск_в_ширину | Wikipedia {{---}} Поиск в ширину в Википедии]]