Випадок 4: збереження раніше сформованих фрагментів
У цьому випадку обидві кінцеві вершини перевірного ребра належать деякому раніше сформованому фрагменту. Перевірне ребро не включається до складу жодного з фрагментів.
Процес перевірки ребер закінчується, коли всі вершини графа увійдуть в один фрагмент, або коли загальна кількість ребер, що увійшла в зазначений фрагмент, дорівнює числу вершин графа, зменшеному на одиницю.
Алгоритм побудови графа з мінімальною сумарною вагою ребер наведений на рис. 2.2.
Алгоритм містить 10 блоків.
У блоці 1 провадиться введення в довільному порядку переліку ребер початкового графа з зазначенням їх ваг.
У блоці 2 здійснюється вибір чергового перевірного ребра мінімальної ваги згідно з будь-яким алгоритмом пошуку мінімального числа.
У блоці 3 з переліку ребер початкового графа виключається перевірне ребро для запобігання його повторного вибору.
У блоці 4 перевіряється умова формування нового фрагмента (випадок 1). В разі виконання умови – перехід до блоку 5, в разі невиконання – до блоку 6.
У блоці 5 провадиться формування нового фрагмента.
У блоці 6 перевіряється умова розширення існуючого фрагмента (випадок 2). В разі виконання умови – перехід до блоку 7, в разі невиконання – до блоку 8.
У блоці 7 провадиться формування розширеного фрагмента.
У блоці 8 перевіряється умова об’єднання двох існуючих фрагментів (випадок 3). В разі виконання умови – перехід до блоку 9, в разі невиконання – до блоку 10.
У блоці 9 провадиться формування об’єднаного фрагмента.
У блоці 10 перевіряється умова закінчення формування графа. В разі невиконання умови – повернення до блоку 2, в разі виконання – закінчення роботи алгоритму.
Зазначимо, що оскільки перевірка будь-якого ребра завжди призводить до одного з чотирьох зазначених випадків, достатньо перевірити умови виконання лише трьох з них, тому в наведеному алгоритмі умова виконання випадку 4 не перевіряється.
Початок
 |
1. Введення переліку
ребер початкового
графа
 | |||||
 | |||||
 | |||||
2.Вибір чергового перевірного
ребра мінімальної ваги
 |
3. Виключення перевірного
ребра з переліку ребер
початкового графа
 |
4.Жодна
з кінцевих вершин Так 5.Формування нового фрагмента з
перевірного ребра не належить перевірного ребра і двох його
жодному фрагменту кінцевих вершин
 | |||
 | |||
 |
Ні
6. Перша
кінцева вершина 7. Включення перевірного ребра
перевірного ребра належить Так і його другої кінцевої вершини
деякому фрагменту, а друга - не до фрагмента, якому належить
належить жодному перша кінцева вершина зазначе-
фрагменту ного ребра
Ні
8.Перша
кінцева вершина пере- 9.Формування об’єднаного
вірного ребра належить одному Так фрагмента з перевірного ребра
фрагменту, а друга - іншому і двох фрагментів, яким належать
фрагменту його кінцеві вершини
Ні
10.Всі
Ні вершини графа
увійшли в один фрагмент
 |
Так
Кінець
Рисунок 2.2. Алгоритм побудови графа з мінімальною сумарною вагою ребер
Наведемо приклад побудови найкоротшої мережі перевезень пошти. Граф початкової мережі зображений на рис. 2.3. Біля ребер графа зазначені їх ваги.
2 5
3
4 4 3
1 1 3 3 6 2 8
| | |||||||||
 | |||||||||
 | |||||||||
 | |||||||||
 | |||||||||
4 2 4 1 4
4 3 7
Рисунок 2.3. Граф початкової мережі
У табл. 2.1 наведений перелік ваг ребер початкового графа.
Таблиця 2.1. Перелік ваг ребер початкового графа
| Ребро | (1,2) | (1,3) | (1,4) | (2,5) | (2,6) | (3,4) | (3,6) | (4,6) | (4,7) | (5,8) | (6,7) | (6,8) | (7,8) |
| Вага |
У табл. 2.2 наведено послідовність кроків формування графа з мінімальною сумарною вагою ребер
Таблиця 2.2. Послідовність кроків формування графа з мінімальною сумарною вагою ребер
| Крок | Перевірне ребро | Вага перевірного ребра | Вершини | ||
| Фрагмент 1 | Фрагмент 2 | Фрагмент 3 | |||
| (1,3) | 1,3 | ||||
| (6,7) | 1,3 | 6,7 | |||
| (3,4) | 1,3,4 | 6,7 | |||
| (6,8) | 1,3,4 | 6,7,8 | |||
| (2,5) | 1,3,4 | 6,7,8 | 2,5 | ||
| (3,6) | 1,3,4,6,7,8 | 2,5 | |||
| (4,7) | 1,3,4,6,7,8 | 2,5 | |||
| (5,8) | 1,3,4,6,7,8,2,5 |
Усього для формування графа з мінімальною сумарною вагою ребер знадобилось 8 кроків, при чому крок 7 (перевірка ребра (4,7)) виявився зайвим.
На рис. 2.4 наведений граф, на якому жирними лініями виділене дерево з мінімальною сумарною вагою ребер.
2 5
3
4 4 3
1 1 3 3 6 2 8
 | |||||||
 | |||||||
 | |||||||
 | |||||||
4 2 4 1 4
4 3 7
Рисунок 2.4. Дерево з мінімальною сумарною вагою ребер.
В наведеному прикладі сумарна вага ребер початкового графа складає 38, а дерева з мінімальною сумарною вагою ребер – 15.
Зазначимо, що за іншим порядком перевірки ребер однакової ваги можна отримати інше дерево з мінімальною сумарною вагою ребер, але значення цієї сумарної ваги не зміниться.