Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
6.8.2. Алгоритм ближайшего соседа построения остовного дереваДанный метод построения минимального остовного дерева не требует ни сортировки, ни проверки на цикличность на каждом шаге. 1. Построение остовного дерева 2. Затем среди ребер, инцидентных х выбираем ребро 3. Повторяя процесс, выполняем поиск наименьшего по весу ребра, соединяющего вершины 4. Процесс включения ребер продолжаем до тех пор, пока все вершины исходного графа • Сложность алгоритма ближайшего соседа. Сложность алгоритма определяется двумя вложенными циклами по числу вершин. В каждом из циклов выполняется константное число операций. Следовательно, сложность составляет Алгоритм 6.9. Алгоритм ближайшего соседа для остовного дерева (см. скан) (см. скан) Программная реализация алгоритма ближайшего соседа представлена в алгоритме 6.10, который близко соответствует множественному описанию соответствующего алгоритма 6.9. Алгоритм 6.10. Программа алгоритма ближайшего соседа (см. скан) (см. скан) (см. скан) (см. скан) Рассмотрим пример расчета по программе алгоритма 6.10 построения минимального остовного дерева графа, изображенного на рис. 6.20. Исходные данные графа представляются матрицей весов его ребер в текстовом файле • в первой строке содержится количество вершин в графе; • в следующих
Результаты расчетов сохраняются в выходном файле
Обозначения данных в файле
|
1 |
Оглавление
|