Остовные деревья минимального веса. Алгоритмы Прима и Крускала

Пусть G неориентированный связный граф. Любой связный подграф G* из множества (G* с G) содержащий все вершины графа и не имеющий циклов называется остовом G или остовным деревом.

Постановка задачи:

Имеется связный граф, каждому ребру которого поставлено в соответствие неотрицательное число, называемое весом ребра. Требуется найти остовное дерево минимального веса. Вес дерева равен сумме весов ребер, входящих в него.

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

1. Выбирается подграф G₁ из множества G, вершинами которого являются вершины графа, имеющего одно ребро, выбранное из ребер графа G имеющих минимальный вес. На каждом последующем шаге уже построенному графу добавляется одно ребро.

…

К. Если подграф G_к-1 из множества G уже построен, то граф G_к получается из G_к-1 добавлением ребра L обладающего свойствами:

1. L инцидентно какому-либо ребру G_к-1

2. При добавлении к L G_к-1 не образуется циклов.

3. L имеет минимальный вес среди ребер, удовлетворяющих условию 1 и 2.

Алгоритм Крускала

1. Выбирается подграф G₁ из множества G, вершинами которого являются вершины графа, имеющего одно ребро, выбранное из ребер графа G имеющих минимальный вес. На каждом последующем шаге уже построенному графу добавляется одно ребро.

К. Если подграф G_к-1 из множества G уже построен, то граф G_к получается из G_к-1 добавлением ребра L обладающего cвойствами:

1. При добавлении L G_к-1 не образуется циклов

2. L имеет минимальный вес среди ребер, удовлетворяющих условию 1.

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

Постановка задачи:

Пусть задан орграф G=(V,E) с заданными положительными длинами ребер. Найти длину кратчайшего пути (и сам путь), соединяющий 2 произвольные фиксированные вершины s (начало) и t (конец).

Алгоритм Дейкстры:

1. В начале алгоритма все вершины не окрашены. Каждой вершине V во время выполнения алгоритма ставиться в соответствие либо L(V) – длина кратчайшего пути включающего только окрашенные вершины, L'(V) – временная метка, которая становиться равной L(V) в момент когда V окрашивается.

Полагаем что L(S)=0, L’(V)=∞, S≠V. Окрашиваем вершину S.

2. Для каждой неокрашенной вершины и соседней с последней из окрашенных вершинV пересчитываем L(U)=min{L’(U), L(V)+L(V,U)}, где L(V,U) – длина дуги между V и U.

Если L'(U)=∞ для любой неокрашенной вершины U, то алгоритм следует закончить. Так как в исходной сети не существует пути из S в неокрашенные вершины, в том числе и в Е. в противном случае находим вершины R, для которой L'(R) =L’(U), после чего К окрашиваем и вносим в корневое дерево дугу (V,R). Вершина R становится последней из окрашенных вершин.

3. В момент, когда вершина T становится окрашенной, находим кратчайший путь, соединяющий S и T , состоящий из окрашенных дуг.

3

s

c

d

t

a

b

4 7

2

2

3 2

3

L(S)=0	L(C)=3(S->C)	L(A)=4 (S->A)	L(D)=6(S->C->D)	L’(b)=7(S->B)	L(T)=8 (S->C->D->T)
L’(A)=4 L’(B)=7 L’(C)=3	L’(D)=3+3=6	L’(B)=7 L’(D)=6	L’(T)=8	L’(T)=9