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