292
правки
Изменения
→Поиск остовного дерева
== Поиск остовного дерева ==
Такая задача возникает, например, в internet of things: набросали с вертолёта на поле размером 3км*3км много хрупких устройств со слабыми антеннами, которым надо соединиться в единую сеть. При этом топология связи там неполная и половина устройств подохла.
А мы хотим построить дерево, чтобы узлы могли друг с другом общаться (а не каждый каждому передавать, потому что тогда надо бороться с циклами).
Решение начинается с инициатора (например, узел, которому надо что-нибудь узнать про всех остальных), которому это дерево нужно.
Каждый узел поддерживает у себя $d$ (расстояние до корня) и $p$ (узел-предок в дереве).
Корень всегда ставит у себя $d=0$ и $p=-1$, а остальные узлы в постоянном режиме делают:
* Найти соседа $j$ с минимальным $d_j$
* Установить его в качестве своего родителя и $d_i=d_j+1$
Тогда корень стабилизируется сразу, узлы, которым корень виден, стабилизируются через одну итерацию, их соседи — через две, и так далее.
Если какой-нибудь узел выпадает, то его дети найдут себе кого-нибудь ещё и снова встроятся в дерево.
Единственная проблема — если умирает корень, но тогда узнавший об этом узел может инициировать перестроение дерева (если у нас цель — связь).
