Основы построения телекоммуникационных системРефераты >> Коммуникации и связь >> Основы построения телекоммуникационных систем
Выбираем в этой строке минимальный элемент 
. Далее вычеркиваем соответствующий ему 7-й столбец матрицы 
и, двигаясь по 7-й строке, сравнивается значение приведенных в ней элементов с их значениями в первой строке без первого и 7-го столбцов. Если значение элемента 7- й строки в соответствующем столбце оказывается меньше значения, указанного в первой строке, то эти значения меняются местами. Если наименьшим будет значение в первой строке, то замена не производится. Таким образом формируется следующая строка:
| 2 | 3 | 4 | 5 | 6 | 8 | 9 | 10 |
|
79 |
51 (7) |
71 |
57 |
60 (7) |
35 (7) |
87 (7) |
120 |
При этом цифрой 7 в скобках обозначены те значения длин, которые взяты из седьмой строки.
Вновь выбираем минимальный элемент строки 
. Действуя аналогично предыдущему, получаем новую строку:
| 2 | 3 | 4 | 5 | 6 | 9 | 10 |
|
79 |
51 (7) |
71 |
57 |
60 (7) |
87 (7) |
120 |
Выбираем минимальный элемент строки 
. Ниже показан дальнейший процесс поиска:
| 2 | 4 | 5 | 6 | 9 | 10 |
|
43 (3) |
71 |
57 |
60 (7) |
87 (7) |
58 (3) |
| 4 | 5 | 6 | 9 | 10 |
|
64 (2) |
57 |
60 (7) |
87 (7) |
58 (3) |
| 4 | 6 | 9 | 10 |
|
51 (5) |
60 (7) |
87 (7) |
58 (3) |
| 6 | 9 | 10 |
|
60 (7) |
87 (7) |
58 (3) |
| 6 | 9 |
|
60 (7) |
87 (7) |
| 9 |
|
48 (6) |
В соответствии с алгоритмом Прима рассчитаем кратчайшее связное дерево (КСД). Оно будет содержать ребра: L1,7, L7,8, L7,3, L3,2, L1,5, L5,4, L3,10, L7,6, L6,9, общей длиной 442 единицы.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
| 1 | 0 | 0 | 0 | 0 | 57 | 0 | 39 | 0 | 0 | 0 |
| 2 | 0 | 0 | 43 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 3 | 0 | 43 | 0 | 0 | 0 | 0 | 51 | 0 | 0 | 58 |
| 4 | 0 | 0 | 0 | 0 | 51 | 0 | 0 | 0 | 0 | 0 |
| 5 | 57 | 0 | 0 | 51 | 0 | 0 | 0 | 0 | 0 | 0 |
| 6 | 0 | 0 | 0 | 0 | 0 | 0 | 60 | 0 | 48 | 0 |
| 7 | 39 | 0 | 51 | 0 | 0 | 60 | 0 | 35 | 0 | 0 |
| 8 | 0 | 0 | 0 | 0 | 0 | 0 | 35 | 0 | 0 | 0 |
| 9 | 0 | 0 | 0 | 0 | 0 | 48 | 0 | 0 | 0 | 0 |
| 10 | 0 | 0 | 58 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Скачать реферат
