//добавление  и удаление элемента из множества

void InsElem(int n);

void DelElem( int n);

        int IsMember(int n);

      int operator ==(TSet &s);

//операции  над множествами

      TSet & operator=(TSet &s);

      TSet operator+(int n);

      TSet operator-(int n);

      TSet operator+(TSet &s);

      TSet operator*(TSet &s);

      TSet operator~(void);

//дружественные  функции 

friend istream &operator>>(istream &istr,TSet &bf);

friend ostream &operator<<(ostream &ostr, TSet &bf);

}; 
 

Реализация  классов описывается в TBitFiield.сpp и TSet.cpp

    Описание  алгоритмов

    Описание  алгоритма Прима

    Пусть V = {1, 2, …, n} – множество вершин графа G = (V, E). Построим множество U, из которого будет вырастать остовное дерево. Сначала положим U = {1} (остов начинает строиться с первой вершины). На каждом шаге алгоритма находится ребро наименьшей стоимости (u, v) такое, что u принадлежит U и v принадлежит V \ U, после чего вершина v переносится из множества V \ U в U. Этот процесс продолжается до тех пор, пока множество U не станет равным V.

    Рассмотрим  реализацию алгоритма Прима. Массив a[i][j] содержит матрицу весов графа. Цикл по i продолжается n – 1 раз, на каждой его итерации ко множеству U добавляется одна вершина (p - ая). В цикле по j перебираются вершины из U,– из V \ U. Таким образом ищется реберо (i, j) наименьшей длины len. 

u.InsElem(1); // присваиваем множеству u первую вершину

for(i = 0; i < n; i++){

   len=200000000;

   for(j = 0; j < n; j++){

      if ( ( u.IsMember(j)) && ((u+(~v)).IsMember(i)))//проверяем начальную вершину на принадлежность к множеству (u+(~v)) , а конечную вершину к множеству u

      {if((i=j)||(a[i][j]=0)) continue;

//поиск  минимального ребра

      if(a[i][j]<len) len=a[i][j];}

      c.InsElem(a[i][j]); //заполняем множество ребер

      v.DelElem(j); //исключаем конечную вершину из множества v

      u.InsElem(j); }} //добавляем конечную вершину в множество u

//заводим  массив для новой матрицы смежности

b = new int *[n];

for(i=0;i<n;i++){

   b[i] = new int [n];

   for(j=0;j<n;j++){

      if(c.IsMember(a[i][j])){

         b[i][j]=a[i][j];}

      else b[i][j]=0;}} 
 
 

 

     Заключение

 

    В ходе проделанной работы была написана программа, реализующая алгоритм Прима.

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

    Пользователь задает граф вручную, с помощью таблицы смежности dataGridView. Программа визуально отображает граф и выделяет цветом вершины, входящие в полученное минимальное остовное дерево. 

 

    

    Литература

 

1. Робертс Сэджвик. Структурная фундаментальные алгоритмы на с++, 5-е изд.: Пер. с англ. — М.: Издательский дом «ДиаСофтЮп», 2002Johnson M. Superscalar
2. Либерти. С++ за 21 день. — СПб.: БХВ-Петербург, 2003. — 464 с.: ил.
3. Борис Пахомов. C/C++ и MS Visual C++ 2010 для начинающих, 2011 
   Издательство: БХВ-Петербург
4. Гергель В.П. — Методы программирования. ННГУ ВМК, 2002
5. Страуструп Б. – язык программирования с++.-Бином,20