Пошук у ширину: відмінності між версіями
[неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
м Робот додав: ca:Cerca en amplada |
Немає опису редагування |
||
Рядок 11:
|isbn=0-262-03293-7}} </ref>
Якщо задано граф ''G'' = (''V'', ''E'') та початкову вершину ''s'', алгоритм пошуку в ширину систематично обходить всі досяжні із ''s'' вершини. На першому кроці вершина ''s'' позначається, як пройдена, а в список додаються всі вершини, досяжні з ''s'' без відвідування проміжних вершин. На кожному наступному кроці всі поточні вершини списку
Алгоритм має назву пошуку в ширину, оскільки «фронт» пошуку (між пройденими та непройденими вершинами) одноманітно розширюється вздовж всієї своєї ширини. Тобто, алгоритм проходить всі вершини на відстані ''k'' перед тим як пройти вершини на відстані ''k''+1.<ref name="mit" />
|