Пошук у ширину
Матеріал з Вікіпедії — вільної енциклопедії.
По́шук у ширину́ — алгоритм пошуку на графі.[1]
Якщо задано граф G = (V, E) та початкову вершину s, алгоритм пошуку в ширину систематично обходить всі досяжні із s вершини. Алгоритм має назву пошуку в ширину, оскільки «фронт» пошуку (між пройденими та непройденими вершинами) одноманітно розширюється вздовж всієї своєї ширини. Тобто, алгоритм проходить всі вершини на відстані k перед тим як пройти вершини на відстані k+1.[1]
[ред.] Джерела інформації
- ↑ а б Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. «22.2», Introduction to Algorithms, вид. 2-ге (2001) (англ. ), 531, MIT Press. ISBN 0-262-03293-7.
