2015-04-01
984
1. Просматривают рёбра графа в порядке возрастания их весов и производят «окрашивание» если:
- обе концевые вершины рассматриваются впервые, тогда ребро причисляют к новому «букету»;
- одна концевая вершина рассматривается впервые, а другая повторно, тогда ребро причисляют к тому же «букету», в котором уже находится рассмотренная повторно вершина;
- если обе концевые вершины рассматриваются повторно, но причислены к разным «букетам», тогда эти букеты объединяются в один;
не производят «окрашивание», если обе концевые вершины рассматриваются повторно, но причислены к одному «букету».
2. Остановка происходит, когда все вершины вошли в один букет. Алгоритм конечен, т.к. конечно количество рёбер графа.
3. Окрашенные рёбра составляют искомое покрывающее дерево.
Пример. Соединить шесть жилых массивов дорогами, общая стоимость постройки которых минимальна. Стоимости строительства известны:
Решение.
| ребро | цвет | Букет1 | Букет2 |
| a;c b;d d;e b;e e;f d;f a;f | окрашено окрашено окрашено не окрашено окрашено не окрашено окрашено | a;c a;c;b;d;e;f | b;d b;d;e b;d;e b;d;e;f b;d;e;f |
Искомый план строительства дорог:
