Изменения

Перейти к: навигация, поиск
Image formatting fixed
=== Проблема поиска в ширину ===
[[Файл:Bfs_problem_on_random_graph.png|300px|thumb|centerleft|Проблема поиска в ширину на случайном графе]]
<br>
На данном изображении представлены результаты работы поиска в ширину , начавшемся в вершине <tex>1</tex> на двух графах: в первом у всех ребер <tex>p = 1</tex>, во втором же факт существования ребра определялся по ходу работы алгоритма {{---}} ребра, отмеченные пунктиром, не существуют. Проблема возникает, когда алгоритм просто не доходит до каких-то ребер, не выясняя, существуют они или нет: находясь в вершине <tex>2</tex>, алгоритм не делал запрос о ребре <tex>(2, 3)</tex>, так как у этому моменту вершина <tex>3</tex> уже была исследована. Ребра, которые потенциально могли быть не изученными, помечены на рисунке точечным пунктиром.
436
правок

Навигация