Практикум по курсу "Алгоритмизация и программирование". Часть 2. Андрианова А.А - 125 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

. Практикум по курсу «Алгоритмизация и программирование». Часть 2
Параметрами функции являются исходный граф, и две ссылки на пере-
менные, в которые будут помещены номера двух вершин (расстояние между
этими вершинами является максимальным в графе).
Решить эту задачу можно, используя алгоритм Флойда. Полученная с по-
мощью этого алгоритма матрица T является матрицей расстояний. Находим
максимальный элемент матрицы, значение которого и будет являться диамет-
ром графа.
// определение функции поиска диаметра графа
int Diametr(Graph2 g, int &s, int &t)
{
int ** T;
int ** H;
int i,j;
// получение матрицы расстояний между вершинами графа
Floyd(g,H,T);
// поиск максимального расстояния
int max=-MAX_INT;
for(i=0;i<g.n;i++)
for(j=0;j<g.n;j++)
if(T[i][j]!=MAX_INT && i!=j && T[i][j]>max)
{
max=T[i][j];
s=i+1;
t=j+1;
}
return max;
}
Задача 7. Дан взвешенный граф в виде матрицы смежности. Построить
для него каркас минимального веса.
Для построения каркаса имеется несколько алгоритмов. Мы будем ис-
пользовать алгоритм Прима (1957 г.).
Сформированный каркас будет храниться в массиве ребер. Каждому ре-
бру соответствуют номера начальной и конечной вершин и длина. Для этого
создадим структуру Edge:
struct Edge
{
// номера начальной и конечной вершин ребра
int begin, end;
125
            .       Практикум по курсу «Алгоритмизация и программирование». Часть 2
    Параметрами функции являются исходный граф, и две ссылки на пере-
менные, в которые будут помещены номера двух вершин (расстояние между
этими вершинами является максимальным в графе).
    Решить эту задачу можно, используя алгоритм Флойда. Полученная с по-
мощью этого алгоритма матрица T является матрицей расстояний. Находим
максимальный элемент матрицы, значение которого и будет являться диамет-
ром графа.

   // определение функции поиска диаметра графа
   int Diametr(Graph2 g, int &s, int &t)
   {
         int ** T;
         int ** H;
         int i,j;

          // получение матрицы расстояний между вершинами графа
          Floyd(g,H,T);

          // поиск максимального расстояния
          int max=-MAX_INT;
          for(i=0;imax)
                    {
                         max=T[i][j];
                         s=i+1;
                         t=j+1;
                    }
          return max;
   }

    Задача 7. Дан взвешенный граф в виде матрицы смежности. Построить
для него каркас минимального веса.
    Для построения каркаса имеется несколько алгоритмов. Мы будем ис-
пользовать алгоритм Прима (1957 г.).
    Сформированный каркас будет храниться в массиве ребер. Каждому ре-
бру соответствуют номера начальной и конечной вершин и длина. Для этого
создадим структуру Edge:

        struct Edge
        {
              // номера начальной и конечной вершин ребра
              int begin, end;

                                     125

Страницы