Расчетно-графическая работа - Графы, Кодирование и декодирование Прюфера, Бинарное дерево поиска - файл n1.doc

приобрести
Расчетно-графическая работа - Графы, Кодирование и декодирование Прюфера, Бинарное дерево поиска
скачать (276.6 kb.)
Доступные файлы (3):
n1.doc171kb.04.12.2010 20:01скачать
n2.doc203kb.04.12.2010 20:10скачать
n3.doc170kb.22.12.2010 02:08скачать

n1.doc





МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

Брянский государственный технический университет





Кафедра «Динамика и прочность машин»

Расчетно-графические работы №1

По элементам дискретной математике
студент гр. 07-ДПМ

Родиков А. Н.
преподаватель

Башмаков А. Г.


Брянск 2010
////////////////////////////////////////////////////

//Найти путь минимального веса в нагруженном графе//

////////////////////////////////////////////////////

#include "stdafx.h"

#include "conio.h"

#define inf 10000

void _tmain()

{

int **WeightMatrix, *Node, *tmpNode, *Way, CurrentNode, length, n, a, b, i, j, k;

bool flag = false;

FILE *data;
fopen_s(&data, "data.txt", "r+t");

fscanf_s(data, "%d", &n);

Node = new int[n];

tmpNode = new int[n];

Way = new int[n];

WeightMatrix = new int*[n];
for(i = 0; i < n; i++)

{

WeightMatrix[i] = new int[n];

Node[i] = tmpNode[i] = inf;

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

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

fscanf_s(data, "%d", &WeightMatrix[i][j]);
fscanf_s(data, "%d %d", &a, &b);
fclose(data);
Node[a - 1] = tmpNode[a - 1] = 0;
do

{

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

{

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

{

if(WeightMatrix[i][j] && Node[i] != inf)

if(Node[j] > Node[i] + WeightMatrix[i][j])

Node[j] = Node[i] + WeightMatrix[i][j];

}

flag = false;

for(k = 0; k < n; k++)

{

if(tmpNode[k] > Node[k])

flag = true;

tmpNode[k] = Node[k];

}

}

}while(flag);
Way[0] = b;

CurrentNode = b - 1;

length = 0;
for(i = n - 2; i >=0; i--)

{

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

if(WeightMatrix[j][CurrentNode])

if(Node[j] == Node[CurrentNode] - WeightMatrix[j][CurrentNode])

{

length++;

Way[length] = j + 1;

CurrentNode = j;

break;

}

if(CurrentNode == a - 1)

break;

}

for(i = length; i >= 0; i--)

{

if(i != length)

printf_s("->");

printf_s("%2d", Way[i]);

}

}
Входные данные – число вершин графа, матрица весов пути (число на позиции характери­зует вес пути из вершины в вершину , если указан 0 – путь не существует), вершины, между кото­рыми нужно определить путь минимального веса. Входные данные находятся в файле data.txt

Выходные данные – вектор, содержащий маршрут в обратном порядке. Маршрут выводится на экран монитора в прямом порядке.

Пример:


граф

файл data.txt



12

0 1 0 1 4 0 0 0 0 0 0 0

1 0 2 0 3 2 0 0 0 0 0 0

0 2 0 0 0 3 0 0 0 0 0 0

1 0 0 0 2 0 3 0 0 0 0 0

4 3 0 2 0 1 4 6 0 0 0 0

0 2 3 0 1 0 0 1 2 0 0 0

0 0 0 3 4 0 0 3 0 2 1 0

0 0 0 0 6 1 3 0 5 0 3 7

0 0 0 0 0 2 0 5 0 0 0 4

0 0 0 0 0 0 2 0 0 0 1 0

0 0 0 0 0 0 1 3 0 1 0 2

0 0 0 0 0 0 0 7 4 0 2 0

1 12




результат работы программы:






Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации