Алгоритм Прима

Алгоритм Прима - алгоритм построения КПД на взвешенном по ребрам графе.

Алгоритм основан на разрастании поддеревьев.

Дерево T'=(X',U') является поддеревом T=(X,U), если Х'єХ, U'єU, причем поддерево Т' может состоять из одной вершины X'єХ.

Поддерево Т' последовательно разрастается за счет прибавления ребер (Xi,Xj), (XiєT, XjєT').

Каждое добавляемое ребро должно иметь наименьший вес. Процесс продолжается пока число ребер Т' не станет равным (n-1).

Пример работы алгоритма Прима

Пусть есть пять выводов на микросхеме, которые необходимо соединить кратчайшим путем, причем расстояния между выводами различные, то есть каждая связь имеет свой вес.

Цель работы: определить оптимальную конфигурацию цепи, объединяющую заданные пять точек.

Целевая функция: минимизация суммарной длины проводников, соединяющих пять выводов.

Из всех покрывающих основных деревьев нам необходимо найти минимальное основное дерево (МОД), у которого сумма весов всех ребер этого дерева минимальна. МОД содержит (n-1) ребро, где n - количество вершин. Также необходимо найти цепь, проходящую по всем вершинам графа один раз. Такую цепь называют гамильтоновой.

5

3

25 20 19

22 9

26

7 15

Рис. 8.10

РЕШЕНИЕ ЗАДАЧИ

1. Пронумеруем вершины и построим исходный граф (полный) и обозначим веса.

2. Выбираем вершину X1 и считаем ее поддеревом T'=(X',U') Х'={ (X1) } U'= 0

3. Строим упорядоченный список ребер, инцидентных вершине X1. Упорядочение проводится по возрастанию весов ребер (в зависимости от поставленной задачи - в нашем случае минимизация суммарной длины).

Из списка выбираем ребро с минимальным весом (1,2) и производится разрастание дерева Т'.

T'=(X',U') Х'= { XI, Х2 } U'={ (1,2) } T'

5

4. В список L вносятся ребра, инцидентные вершине Х2. Список примет следующий вид:

Выбирается ребро (2,3) с минимальным весом, равным 3 и добавляется к поддереву Т', если оно не образует цикла с ребрами Т'.

T'=(X',U') X'={ X1,X2,X3 } U'={ (1,2),(2,3) } 5

В списке L удаляются ребра, объединяющие вершины

между собой, т.е. удаляют ребро (1,3).

5. Проверяем условие | Х'| = | X | ≠ 5 и | n'| =| n| ≠ 4

Если условия выполняются, то по алгоритму переходим к следующему шагу 6.

6. Рассматриваем следующую вершину и вносим в список L ребра, инцидентные рассматриваемой вершине.

Аналогично п.4 выбираем ребро (2,4), если оно не образует цикла с ребрами Т.

T'=(X',U') X'={ X1,X2,X3,X4 } U'={ (1,2),(2,3),(2,4) } 5

В списке L удаляются ребра, образующие циклы 9 3

с ранее выбранными ребрами Т', т.е. (3,4), (1,4) .

7. Такой же как и п..5.

8. Рассматривается вершина Х4.

Упорядоченный список примет, следующий вид:

Выбираем ребро с минимальным весом (4,5)

Проверяем условие | X' | = | X | =5

| n' | = | n | = 4

5

9 3

Если оно выполняется, то переходим к пункту 9."Конец работы алгоритма".

9. Конец работы алгоритма.