Алгоритм Прима определение минимального остовного дерева(случай многоуровнего графа)

По заданному графу заполняется матрица весов W(N,N). Веса несуществующих ребер предполагаются сколь угодно большими. Образуется массив P(N) меток вершин графа (столбцов матрицы весов). Алгоритм решения задачи заключается в последовательном заполнении массива меток столбцов и состоит из следующих этапов.

Предварительный этап. Обнуляется массив P(N) меток столбцов таблицы. Произвольно выбранному столбцу присваивается значение метки, равное его номеру.

Общий этап. В строках, номера которых равны номерам помеченных столбцов, находится минимальный элемент среди элементов непомеченных столбцов. Столбец, в котором находится минимальный элемент, помечается меткой, номер которой равен номеру его строки, а элементу с ”транспонированными” индексами присваивают значение ∞ (он симметричен относительно главной диагонали).

Заключительный этап. Ребра дерева определяются по меткам столбцов, вес дерева определяется суммой весов ребер.

Матрица весов, полученная после предварительного этапа алгоритма, представлена в табл.5, где в качестве начальной выбрана вершина 0.

0 Таблица 5

i									tp
tп

Задачей общего этапа является помечивание всех столбцов таблицы. В 0-й строке находится минимальный элемент w₀₁=70. 1-й столбец, содержащий минимальный элемент, помечается номером строки, где этот элемент находится, т.е. номером 0. Элементу w₁₀ присваивается сколь угодно большое значение.

Затем в непомеченных столбцах 1-й строки находится минимальный элемент w₁₂=120, тогда 2-й столбец помечается номером 1, а элементу w₂₁ присваивается значение ∞.

Во 2-й строке минимальный элемент w₂₃=60, 3-й столбец, содержащий w₂₃=60, помечается номером 2, w₃₂=∞.

В 3-й строке w₃₄=40, 4-й столбец помечается номером 3, а элемент w₄₃=∞.

В 4-й строке w₄₅=20, 5-й столбец помечается номером 4, а элемент w₅₄=∞.

В 5-й строке w₅₆=30, 6-й столбец помечается номером 5, а элемент w₆₅=∞.

В 6-й строке w₆₇=15, 7-й столбец помечается номером 6, а элемент w₇₆=∞.

Т.к. в 7-й строке все элементы равны бесконечности, то на этом общий этап закончен. В результате таблица примет вид, представленный в табл. 6.

Таблица 6

0 0 1 2 3 4 5 6

i									tp
	∞
		∞
			∞
				∞
					∞
						∞
							∞
tп

На заключительном этапе выписывается последовательность вершин, ребра между которыми включаются в минимальное остовное дерево. Это ребра, соединяющие вершины 0-1, 1-2, 2-3, 3-4, 4-5, 5-6, 6-7. Вес остовного дерева равен 70+120+60+40+20+30+15=355. Полученное остовное дерево имеет вид:

x₂ x₄ x₆

x₀

70 120 60 40 20 30 15

x₁ x₃ x₅ x₇

Дата добавления: 2015-08-21