На этом шаге мы рассмотрим алгоритм построения остова наименьшей стоимости.
Пусть G=(V,E) - связный неориентированный граф, для которого задана функция стоимости, отображающая ребра в вещественные (целые) числа. Напомним, что остовным деревом для данного графа называется неориентированное дерево, содержащее все вершины графа. Стоимость остовного дерева определяется как сумма стоимостей его ребер.
Наша цель - найти для G остовное дерево наименьшей стоимости.
Эта задача возникает при проектировании линий электропередачи, трубопроводов, дорог и т.п., когда требуется заданные центры соединить некоторой системой каналов связи так, чтобы любые два центра были связаны либо непосредственно соединяющим их каналом, либо через другие центры и каналы, и чтобы общая длина (или, например, стоимость) каналов связи была минимальной. В этой ситуации заданные центры можно считать вершинами графа с весами ребер, равными длинам (стоимости) соединяющих эти центры каналов. Тогда искомая сеть будет остовным деревом наименьшей длины (стоимости). Поскольку граф с n вершинами содержит nn-2 различных остовных дерева, то решение этой задачи "слепым" перебором" вариантов потребовало бы чрезвычайно больших вычислений даже при относительно малых n. Однако для ее решения имеются эффективные алгоритмы.
Первый алгоритм нахождения такого дерева - алгоритм Дж.Краскала, опубликованный в 1956 г. Развитием этого алгоритма является алгоритм Р.Прима (1957 г.) (см. Прим Р.К. Кратчайшие связывающие сети и их обощения. - Киберн.сб., вып.2 (ст.серия), 1961, с.95-107).
Приведем теорему, позволяющую получить алгоритм Краскала.
- Теорема [1, с.69].
- Пусть G - связный граф с n вершинами, и пусть каждому его ребру
приписано неотрицательное действительное число m(e), называемое его мерой.
Тогда следующая процедура приводит к решению задачи о минимальном остовном графе:
- выберем ребро e1, обладающее в G наименьшей мерой;
- определим по индукции последовательность ребер e2,e3, ...,en-1, выбирая на каждом шаге ребро (отличное от предыдущих) с наименьшей мерой, обладающее тем свойством, что оно не образует циклов с предыдущими ребрами ei. Полученный подграф T графа G, ребрами которого являются e2,e3, ...,en-1 и есть требуемое остовное дерево.
Алгоритм Краскала [2, с.199] работает с набором VS непересекающихся множеств узлов. Каждое множество W из VS представляет связное множество узлов, образующее остовное дерево в остовном лесу, представленном набором VS.
Ребра выбираются из E в порядке возрастания стоимости. Ребра (v,w) рассматриваются по очереди. Если v и w принадлежат одному и тому же множеству из VS, то ребро (v,w) исключается из рассмотрения. Если v и w принадлежат разным множествам W1 и W2 (это означает, что W1 и W2 еще не соединены), то сливаем их в одно множество и добавляем (v,w) к множеству ребер, входящих в окончательное остовное дерево.
В [2, с.199] приведено описание алгоритма Краскала на псевдокоде:
T <- пустое множкство;
VS <- пустое множество;
Построить очередь с приоритетами Q, содержащую все ребра из E;
for (v принадлежащего V) Добавить {v} к VS
while |VS|>1
{
Выбрать в Q ребро (v,w) наименьшей стоимости;
Удалить (v,w) из Q;
if v и w принадлежат различным множествам W1 и W2 из VS
{
Заменить W1 и W2 на объединение W1 и W2 в VS;
Добавить (v,w) к T;
}
}
Реализуем алгоритм на языке C++. Для хранения ребер и их стоимостей воспользуемся бинарным деревом поиска, описание которого имеет вид:
typedef unsigned int SubInt; typedef struct Uzel *Ref; typedef struct Uzel { SubInt X; //Начало дуги. SubInt Y; //Конец дуги int Pay; //Стоимость дуги. Ref Left; //Указатель на левого сына. Ref Right;//Указатель на правого сына. };
Ясно, что в "самой левой" вершине дерева будет храниться дуга, обладающая наименьшей стоимостью, и поиск этой вершины может выглядеть, например, так:
UkUzel = Root; //Установили текущий указатель на корень дерева. while (UkUzel->Left != NULL) UkUzel = UkUzel->Left; T1 = UkUzel->X; T2 = UkUzel->Y; //Получили ребро!
Множество VS будем хранить в линейном однонаправленном списке с заглавным звеном, описание которого выглядит так:
typedef struct zveno *svqz; typedef struct zveno { unsigned int Element[256]; // Множество из VS. svqz Sled; // Указатель на узел. zveno(); // Конструктор. }; zveno::zveno() //Обнуление элементов. { for(int k=0;k<256;Element[k++]=0); }
Тогда, например, фрагмент алгоритма:
if v и w принадлежат различным множествам W1 и W2 из VS
{
Заменить W1 и W2 на объединение W1 и W2 в VS;
Добавить (v,w) к T;
}
Res1 = Res2 = NULL; Poisk (UkStr,T1,&Res1); Poisk (UkStr,T2,&Res2); if ( Res1!=Res2 ) { for (int k=0;k<256;k++) if ( Res1->Element[k]==1 || Res2->Element[k]==1 ) Res1->Element[k]=1; Udalenie (&Res2,UkStr); cout << "(" << T1 << " " << T2 << ") "; }
Пример. Построение остовного дерева наименьшей стоимости (алгоритм Краскала).
#include <iostream.h> #define TRUE 1 #define FALSE 0 typedef int Boolean; typedef unsigned int SubInt; typedef struct Uzel *Ref; typedef struct Uzel { SubInt X; //Начало дуги. SubInt Y; //Конец дуги int Pay; //Стоимость дуги. Ref Left; //Указатель на левого сына. Ref Right;//Указатель на правого сына. }; typedef struct zveno *svqz; typedef struct zveno { unsigned int Element[256]; svqz Sled; zveno(); }; zveno::zveno() { for(int k=0;k<256;Element[k++]=0); } class Spisok { private: Ref Root; void Search (int, int, int, Ref *); void Poisk (svqz, SubInt, svqz *); void Postroenie (svqz *); void Udalenie (svqz *, svqz); public: Spisok() { Root = NULL;} //Вначале дерево пусто. void Reshenie(); void Postr(); }; void Spisok::Search (int A, int B, int C, Ref *p) //Добавление вершины, содержащей поля A,B,C, в дерево *p. { if ( (*p) == NULL ) { (*p) = new (Uzel); (**p).X = A; (**p).Y = B; (**p).Pay = C; (**p).Left = (**p).Right = NULL; } else if ( C<=(**p).Pay ) Search (A,B,C,&((**p).Left)); else if ( C>(**p).Pay ) Search (A,B,C,&((**p).Right)); } void Spisok::Postroenie (svqz *UkStr) //Постpоение линейного однонапpавленного списка //с заглавным звеном, содержащего вершины графа. { svqz UkZv; int el; (*UkStr) = new (zveno); UkZv = (*UkStr); UkZv->Sled = NULL; cout << "Вводите вершины графа: \n"; cin >> el; while ( el!=0 ) { UkZv->Sled = new (zveno); UkZv = UkZv->Sled; UkZv->Element[el] = 1; UkZv->Sled = NULL; cin >> el; } } void Spisok::Postr() //Постpоение деpева, содержащего все ребра графа. { int A,B,C; cout << "Для каждого ребра вводите начальную, затем конечную\n"; cout << "вершины и стоимость ребра, их соединяющего:\n"; cin >> A >> B >> C; while ( A!=0 ) { Search (A,B,C,&Root); cin >> A >> B >> C; } } void Spisok::Poisk (svqz st, SubInt MENT, svqz *Res) { svqz q; (*Res) = NULL; q = st->Sled; while ( q != NULL && (*Res) == NULL ) { if ( q->Element[MENT]==1 ) (*Res) = q; else q = q->Sled; } } void Spisok::Udalenie (svqz *zv, svqz UkStr) //Удаление из однонапpавленного списка с заглавным звеном //элемента, на который указывает указатель zv. { svqz Z; //"Стаpый" указатель. svqz UkZv1; //"Hовый" указатель. if ( (*zv)->Sled != NULL ) (**zv) = *((**zv).Sled); else { Z = UkStr; UkZv1 = UkStr->Sled; while (UkZv1 != (*zv)) { Z = UkZv1; UkZv1 = UkZv1->Sled; } Z->Sled = NULL; delete UkZv1; } } void Spisok::Reshenie() { svqz UkStr; //Указатель на список. Ref UkUzel; //Рабочий указатель на узел дерева. Ref UkUzel1; //Рабочий указатель на узел дерева. SubInt T1,T2; svqz Res1,Res2; //Построение первоначальных множеств вершин графа. Postroenie (&UkStr); cout <<"Ребра остовного дерева наименьшей стоимости: "; while ( UkStr->Sled->Sled != NULL ) { UkUzel1 = Root; //"Отстающий" указатель. UkUzel = Root->Left; //"Опережающий" указатель. if ( UkUzel== NULL ) { //Выбор в дереве ребра наименьшей стоимости и ... T1 = Root->X; T2 = Root->Y; //... удаление этого ребра из дерева. Root = Root->Right; delete UkUzel1; } else { //Выбор в дереве ребра наименьшей стоимости и ... while ( UkUzel->Left != NULL ) { UkUzel1 = UkUzel1->Left; UkUzel = UkUzel->Left; } T1 = UkUzel->X; T2 = UkUzel->Y; //... удаление этого ребра из дерева. UkUzel1->Left = UkUzel->Right; delete UkUzel; } //Если v и w принадлежат различным //множествам W1 и W2 из VS ... Res1 = Res2 = NULL; Poisk (UkStr,T1,&Res1); Poisk (UkStr,T2,&Res2); if ( Res1!=Res2 ) { for (int k=0;k<256;k++) if ( Res1->Element[k]==1 || Res2->Element[k]==1 ) Res1->Element[k]=1; Udalenie (&Res2,UkStr); cout << "(" << T1 << " " << T2 << ") "; } } } void main () { Spisok Tree; Tree.Postr(); Tree.Reshenie(); }
Тестовые примеры:
пример (A) заимствован из [2, с.200-201];
пример (B) заимствован из [3, с.198];
пример (C) заимствован из [4, с.341].
Для каждого ребра вводите начальную, затем конечную
вершины и стоимость ребра, их соединяющего:
(A) 1 7 1 (B) 1 2 9 (C) 1 3 2
3 4 3 2 3 10 2 4 4
2 7 4 2 7 8 2 5 8
3 7 9 1 3 6 1 2 1
2 3 15 1 7 1 3 4 9
4 7 16 1 6 4 3 6 7
4 5 17 6 4 5 8 10 5
1 2 20 7 4 7 4 8 6
1 6 23 3 4 2 5 8 4
5 7 25 4 5 11 4 7 3
5 6 28 7 6 3 1 4 6
6 7 36 0 0 0 6 7 7
0 0 0 6 9 2
7 9 8
7 10 9
9 10 3
0 0 0
Вводите вершины графа:
(A) 1 2 3 4 5 6 7 0
(B) 1 2 3 4 5 6 7 0
(С) 1 2 3 4 5 6 7 8 9 10 0
Ребра остовного дерева наименьшей стоимости:
(A) (1 7) (3 4) (2 7) (3 7) (4 5) (1 6)
(B) (1 7) (3 4) (7 6) (6 4) (2 7) (4 5)
(C) (1 2) (6 9) (1 3) (9 10) (4 7) (5 8) (2 4) (8 10) (4 8)
Замечания.
- В монографии [2, с.201-202] показано, что остовное дерево наименьшей стоимости для графа с |E| ребрами можно найти за время
O( |E|*log |E|) в общем случае и O(|E|), если |E| достаточно велико по сравнению с числом узлов.
- В некоторых ситуациях требуется построить остов не минимального, а максимального веса. К этой задаче также применим алгоритм Краскала.
Следует только всюду минимальный вес заменить максимальным.
- [5, с.424]. Напомним Вам, что под стягиванием ребра мы подразумеваем операцию
удаления ребра e и отождествление его концевых вершин.
Алгоритм Прима для определения минимального взвешенного остова в связном взвешенном графе G=(V,E) формулируется так: выбрать произвольную вершину v в графе G. Среди всех ребер, входящих в v, выбрать ребро e1 с минимальным весом. Стянем e1, и пусть G' - полученный граф. Повторить эти действия для G' и продолжить до тех пор, пока не будет определено ребро en-1. Ребра e1, e2, ..., en-1 образуют минимальный взвешенный остов графа G.
- С задачей об остове минимального веса тесно связана задача Штейнера [4, с.62-63]. Мы отметим лишь, что какие-либо эффективные алгоритмы, решающие задачу Штейнера неизвестны!
(1) Уилсон Р. Введение в теорию графов. - М.: Мир, 1977. - 207 с.
(2) Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. - М.: Мир, 1979. - 536 с.
(3) Липский В. Комбинаторика для программистов: Пер. с польск. - М.: Мир, 1988. - 213 с.
(4) Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. - М.: Наука, 1990. - 384 с.
(5) Свами М., Тхуласираман К. Графы, сети и алгоритмы. - М.: Мир, 1984. - 454 с.
На следующем шаге мы рассмотрим алгоритм построения фундаментального множества циклов.
