Федеральное агентство по образованию Российской Федерации

Государственное образовательное учреждение

высшего профессионального образования

Нижегородский государственный университет им. Н.И. Лобачевского 

Факультет вычислительной математики и кибернетики 
 
 
 
 
 
 
 
 
 

Отчёт по лабораторной работе 

Реализация  алгоритма Прима

c использованием множеств 
 
 
 
 
 
 
 
 

Выполнил:

  студентка ф-та ВМК гр. 82-11 

Цветкова  Н.Ю. 
 
 
 

Проверил:

  ассистент каф. МО ЭВМ, ВМК 

Козинов Е.А. 
 
 
 
 
 
 
 

Нижний  Новгород

2011 г. 

    Содержание 

 

    

    Введение

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

      В теории графов такая задача  может решается путем построения минимального остовного дерева неориентированного графа. Данная задача имеет несколько методов решения. Один из них – алгоритм Прима.

      Суть этого метода заключается  в последовательном добавлении  к остову минимального, «безопасного»  ребра (ребра, которое не образует  цикла). В данной работе представлена программа, реализующая алгоритм Прима, которая вычисляет минимальное остовное дерево неориентированного графа и делает визуализацию графа. 

 

    

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

 

1. Необходимо  выполнить реализацию алгоритма Прима

Задача  поиска минимального остовного дерева с помощью алгоритма Прима состоит в нахождении для заданого графа остовного дерева наименьшей стоимости. 

2. Необходимо  использовать в реализации битовые поля и множества

 

Использовать  в реализации алгоритма два класса:

• Класс TBitField – битовые поля
• Класс TSet – множества(реализация через битовые поля)

Завести 3 множества: множество начальных вершин графа, множество конечных вершин графа, множество  ребер; 

3. Реализовать алгоритм в используя windows form c++

 

Необходимо  использовать инструменты windows form:

• textBox – для ввода количества вершин графа
• dataGridView – для ввода матрицы смежности и для вывода полученной матрицы
• button – кнопки для использования остальных элементов формы
• panel – для рисования исходного графа и вывода полученного остовного дерева

 
 

В результате лабораторной работы должны получить программу в Microsoft visual studio, которая выполняет алгоритм Прима и в результате своей работы выводит на экран минимальное остовное дерево исходного графа.

 

    Руководство пользователя

1. Запустите файл программы поиска минимального остовного дерева методом Прима.

 

2. На экране вы видите окно windows form1(рис.1)

    Рисунок 1

3. Нужно ввести количество вершин исходного графа (рис.2)

    Рисунок 2

4. Затем вводите матрицу смежности (рис.3)

    Рисунок 3

5. Нажимайте на кнопку «Ввод матрицы» и на панели рисования появляется нарисованный исходный граф (рис.4)

    Рисунок 4

6. Затем нажимайте «Алгоритм прима» и в результате на экране form1 появляется новая матрица смежности, полученная в результате алгоритма Прима
7. Нажимайте на «Нарисовать остовное дерево», получайте требуемый результат – рисуется минимальное остовное дерево.
8. Закрывает программу

 

     Руководство программиста

    Описание  структуры программы

1. Ввод  данных
1. Ввод числа вершин исходного графа.

Реализуется с помощью объекта windows form - TextBox

n=Convert::ToInt32(this->textBox1->Text);

2. Ввод матрицы смежности 

Реализуется с помощью объекта windows form - dataGridView

this->dataGridView1->RowCount = n;

this->dataGridView1->ColumnCount = n;

2. Изображение графа

Для изображения графа  на экране используем объект windows form – panel.

А так же для вывода графа на экран  кнопку button 

int x = 133, y = 121, r = 100;

Graphics ^g = e->Graphics;

g->DrawEllipse(GrayPen, x-r, y-r, 2*r, 2*r );

int i, j;

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

   g->DrawEllipse(BlackPen1, x+r*cos(6.28*i/n),y+r*sin(6.28*i/n),2,2);

      for (j=i+1; j<n; j++)

      if (a[i][j]>0) g->DrawLine(BlackPen2,

         int(x+r*cos(6.28*i/n)),int(y+r*sin(6.28*i/n))

         int(x+r*cos(6.28*j/n)),int(y+r*sin(6.28*j/n)));}}

3. Получение данных из таблицы смежности

//получаем  размер матрицы смежности

n=Convert::ToInt32(this->textBox1->Text);

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

   a[i] = new int [n];

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

//заводим  матрицу смежности, используя  данные, введенные пользователем

      a[i][j] = Convert::ToInt32(dataGridView1->Rows[i]->Cells[j]->Value->ToString());} 

4. Ввод  данных в таблицу  смежности остовного  графа из массива

 

//задаем  размер таблицы

this->dataGridView2->RowCount = n;

this->dataGridView2->ColumnCount = n;

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

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

//заполняем  элементы таблицы полученными  данными

        dataGridView2->Rows[i]->Cells[j]->Value =b[i][j].ToString();

        dataGridView2->Rows[i]->Cells[j]->Value = b[j][i].ToString();

         }}

    Описание структур данных

1. Глобальные переменные:

    var.h 

#pragma once

extern int n,**a,**b;

    var.cpp 

#include "stdafx.h"

#include "Var.h"

int n;//кол-во вершин в графе

int **a = new int *[n];//массив матрицы смежности

int **b = new int *[n];//массив матрицы смежности остовного дерева 

2. Структура классов

 

1. Класс битовых  полей

 
 

class TBitFiield

{private:

int BitLen;

TELEM *pMem;

int MemLen;

int GetMemIndex( int n);

TELEM GetMemMask(int n);

public:

TBitFiield(int len);

TBitFiield(TBitFiield &bf);

~TBitFiield();

//доступ к битам

int GetLength(void);

void SetBit(int n);

void ClrBit(int n);

int GetBit(int n);}; 
 

2. Класс -  множества

 
 

#include "TBitFiield.h"

class TSet

{

private:

int MaxPower;

TBitFiield BitFiield;

public:

TSet(int mp);

TSet(TSet &s);

TSet(TBitFiield &bf);

operator TBitFiield();

int GetMaxPower(void);