Анализ структуры системы на основе топологических описаний в виде взвешенных графов. Алгоритм построения наименьшего остового дерева

Наименьшее остовое дерево — это вариант остового дерева имеющий наименьший суммарный вес дуг. При анализе структуры системы решение задачи поиска нахождения наименьшего остового дерева позволяет выбирать вариант соединения вершин системы с наименьшей затратой некоторого ресурса.

Алгоритм построения наименьшего остового дерева:

1.Создаем матрицу столбец R, в которую будут заноситься кратчайшие расстояния от вершин графа до остового дерева. В качестве начальных значений заносится ∞, элементы матрицы соответствуют вершинам графа. Создаем матрицу столбец В. В неё будут заноситься вершины остового дерева, ближайшие к соответствующим вершинам графа. В качестве начальных  значений вводятся пробелы.

2.Взять любую вершину графа, и поместить ее в остовое дерево, т.е. принять в качестве вершины Vk. Вычеркнуть вершину Vk из вершин графа.

3.Пересчитать расстояния от вершин графа до остового дерева, т.е. значения элементов матрицы R. Если расстояние до остового дерева для какой либо вершины Vj больше чем вес дуги между данной вершиной и вершиной Vk , т.е. вершиной включенной в остовое дерево, то в качестве значения расстояния до остового дерева от этой вершины принимается данный вес дуги между вершиной Vj и Vk.

В качестве вершины остового дерева у которой найдено расстояние, т.е. вершины остового дерева ближайшей вершины Vk – принимается вершина Vk.

4.В качестве вершины Vk, т.е. вершины включенной в остовое дерево принимается вершина с наименьшим значением матрицы R, т.е. вершины ближайшей к остовому дереву. Вершина Vk вычеркивается из множества вершин.

5.Если не все вершины графа вычеркнуты, то переход к этапу 3.

Ссылка на основную публикацию
Adblock detector