Материал: курсовой проект алгоритм прима

Список используемых источников.

1. ГОСТ 7.32–2001. Отчёт о научно-исследовательской работе. Структура и правила оформления [Текст]. – Взамен ГОСТ 7.32–91 ;введ. 2001–07–01. – Минск :Межгос. совет по стандартизации, метрологии и сертификации ; М. : Изд-во стандартов, 2001. – 16 с. – (Система стандартов по информации, библиотечному и издательскому делу).

2. ГОСТ 7.1–2003. Библиографическая запись. Библиографическое описание. Общие требования и правила составления [Текст]. – Взамен ГОСТ 7.1–84, ГОСТ 7.16–79, ГОСТ 7.18–79, ГОСТ 7.34–81, ГОСТ 7.40–82 ;введ. 2004–07–01. – М. : Изд-во стандартов, 2004. – 116 с. – (Система стандартов по информации, библиотечному и издательскому делу).

3. Кормен Т. Х. / Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ, 2-е изд. — М.: Вильямс, 2007. — 1296 с.

4. Роберт Серджвик. Фундаментальные алгоритмы на С++. [Текст]: в 5 ч. / Роберт Серджвик. – СПб, ООО «ДиаСлфтЮП», 2002.

Ч. 5: Алгоритмы на графах: Перевод с англ. – 2002 – 486с. ISBN 5-93772-054-7.

5. Степанов, В.Н. Дискретная математика: графы и алгоритмы на графах: учеб.пособие / В.Н. Степанов. – Омск, Изд-во ОмГТУ, 2010 – 120с. ISBN 978-5-8149-0913-8

6. Форум программистов и сисадминов CyberForum.ru [Электронный ресурс]. –Форум начинающих и профессиональных программистов, системных администраторов, администраторов баз данных, компьютерный форум. – Режим доступа: . http://www.cyberforum.ru/ –Загл. с экрана.

7. Википедия – свободная энциклопедия [Электронный ресурс]. – Википедия – свободная энциклопедия, которую может редактировать каждый. Режим доступа: . http://ru.wikipedia.org –Загл. с экрана.

Приложение А.

(Обязательное)

Текст основной программы.

#include<stdio.h>

#include<stdlib.h>

#include<iostream>

#include<conio.h>

#include<time.h>

using namespace std;

int a,b,u,v,n,i,j,N=1;

int visited[101]={0},_min,_mincost=0,cost[101][101];

void main()

{

setlocale(LC_ALL, "Russian");

srand(time(NULL));

printf("\n Введите кол-во вершин :");

scanf("%d",&n);

printf("\n Элементы матрицы %i*%i:\n",n,n);

float t=clock()/100;

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

{

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

{

//scanf("%d",&cost[i][j]);

if (i==j) cost[i][j]=0; else cost[i][j]=0+rand()%15;

cout<<cost[i][j]<<"\t";

if(cost[i][j]==0)

cost[i][j]=999;

}

printf("\n");

}

visited[1]=1;

printf("\n");

while(N<n) // N - номер вершины

{

for(i=1,_min=999;i<=n;i++)

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

if(cost[i][j]<_min)

if(visited[i]!=0)

{

_min=cost[i][j];

a=u=i;

b=v=j;

}

if(visited[u]==0 || visited[v]==0)

{

printf("\n Ребро %d:(%d %d) вес:%d",N++,a,b,_min);

_mincost+=_min;

visited[b]=1;

}

cost[a][b]=cost[b][a]=999;

}

float tt=clock()/100-t;

printf("\n Время выполнения алгоритма: %f",tt);

printf("\n Вес минимального остовного дерева=%d",_mincost);

getch();

}