Практикум по курсу "Алгоритмизация и программирование". Часть 2. Андрианова А.А - 126 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

А.А. Андрианова, Л.Н. Исмагилов, Т.М. Мухтарова .
// длина ребра
int len;
};
В алгоритме Прима каркас формируется посредством последовательного
добавления вершин. Для определения добавляемой на каждой итерации вер-
шины используются два вспомогательных массива. Элемент массива al-
pha[i] – это ближайшая к i-ой вершина, уже включенная в каркас,
beta[i] – это длина ребра, соединяющего i-тую вершину с вершиной al-
pha[i], nodes – это массив номеров вершин, включенных в каркас.
В nodes включается начальная вершина. Просматривая все смежные с
ней вершины (переменная v), запоминаем для них в массиве alpha началь-
ную вершину, а в массиве beta – длину соответствующего ребра. Для не-
смежных вершин, соответственно, alpha[v]=-1 и beta[v]=∝.
До тех пор, пока в каркас не будут включены все вершины, выполняем
следующие действия:
1) среди вершин, не включенных в каркас, находим ближайшую к нему.
Обозначим найденную вершину через w;
2) добавляем вершину w в каркас:
а) в массив nodes заносим вершину w;
б) в массив ребер заносим ребро (alpha[w],w);
3) пересчитываем те элементы массивов alpha и beta, которые соответ-
ствуют не включенным в каркас вершинам. Для них вершина w может стать
ближайшей из каркаса.
Рассмотрим процесс решения задачи построения каркаса минимального
веса алгоритмом Прима для графа, изображенного на рис. 7.6 (таблица 4).
Таблица 4. Построение каркаса минимального веса алгоритмом Прима.
126
А.А. Андрианова, Л.Н. Исмагилов, Т.М. Мухтарова                        .
                   // длина ребра
                   int len;
           };

    В алгоритме Прима каркас формируется посредством последовательного
добавления вершин. Для определения добавляемой на каждой итерации вер-
шины используются два вспомогательных массива. Элемент массива al-
pha[i] – это ближайшая к i-ой вершина, уже включенная в каркас,
beta[i] – это длина ребра, соединяющего i-тую вершину с вершиной al-
pha[i], nodes – это массив номеров вершин, включенных в каркас.
    В nodes включается начальная вершина. Просматривая все смежные с
ней вершины (переменная v), запоминаем для них в массиве alpha началь-
ную вершину, а в массиве beta – длину соответствующего ребра. Для не-
смежных вершин, соответственно, alpha[v]=-1 и beta[v]=∝.
    До тех пор, пока в каркас не будут включены все вершины, выполняем
следующие действия:
    1) среди вершин, не включенных в каркас, находим ближайшую к нему.
Обозначим найденную вершину через w;
    2) добавляем вершину w в каркас:
    а) в массив nodes заносим вершину w;
    б) в массив ребер заносим ребро (alpha[w],w);
    3) пересчитываем те элементы массивов alpha и beta, которые соответ-
ствуют не включенным в каркас вершинам. Для них вершина w может стать
ближайшей из каркаса.
    Рассмотрим процесс решения задачи построения каркаса минимального
веса алгоритмом Прима для графа, изображенного на рис. 7.6 (таблица 4).




             Таблица 4. Построение каркаса минимального веса алгоритмом Прима.


                                           126

Страницы