436
правок
Изменения
м
Нет описания правки
Чтобы вычислить размер компоненты связности, пройдемся с помощью [[Обход в ширину|БФС]] по ней, стартуя из произвольной вершины и переходя к очередной неисследованной вершине, только если ребро между ними существует (данный факт необходимо установить независимо от других ребер, с вероятностью <tex>p = \frac{d}{n}</tex>). Если ребро существует, пометим следующую вершину как "открытую". Алгоритм закончит свою работу (обойдет всю компоненту связности), когда множество неисследованных "открытых" вершин станет пустым.
<br>
=== Проблема БФС поиска в ширину ===
[[Файл:Bfs_problem_on_random_graph.png|300px|center|Проблема БФС]]
<br>
На данном изображении представлены результаты работы БФСпоиска в ширину , начавшемся в вершине <tex>1</tex> на двух графах: в первом у всех ребер <tex>p = 1</tex>, во втором же факт существования ребра определялся по ходу работы алгоритма {{---}} ребра, отмеченные пунктиром, не существуют. Возникающая проблема состоит в том, что, к примеру, Проблема возникает, когда алгоритм просто не доходит до каких-то ребер, не выясняя, существуют они или нет: находясь в вершине <tex>2</tex>, алгоритм не делал запрос о ребре <tex>(2, 3)</tex>, так как у этому моменту вершина <tex>3</tex> уже была исследована. Ребра, которые потенциально могли быть не изученными, помечены на рисунке точечным пунктиром.
=== Неоткрытые вершины ===
