Автор: Пользователь скрыл имя, 26 Октября 2011 в 21:14, реферат
Граф – это некоторое конечное множество точек, называемых вершинами, и конечный набор линий, называемых ребрами, соединяющих некоторые пары точек и .
Пример 1: схема автомобильных дорог, связывающих города некоторой области, является характерным примером графа.
Графы. Основные определения с примерами…………………………………..2
Алгоритм Флойда — Уоршелла…………………………………………………..4
Листинг программы………………………………………………………………..5
Примеры выполнения программы……………………………………………..12
Литература…………………………………………………………………………17
Writeln
End;
Readln; {Задержка экрана}
{Вывод полученной матрицы длин путей}
Clrscr; {Очистка экрана}
Writeln('Матрица длин путей');
Writeln;
Write(' ');
TextColor(Green); {Задание цвета текста}
For I:=1 To N Do
Write(' ',Chr(64+I),' ');
Writeln;
For I:=1 To N Do
Begin
TextColor(Green); {Задание цвета текста}
Write(' ',Chr(64+I),' ');
TextColor(White); {Задание цвета текста}
For J:=1 To N Do
Write(T[I,J]:3,' '); {Вывод текущего элемента матрицы}
Writeln
End;
Readln; {Задержка экрана}
Clrscr; {Очистка экрана}
GotoXY(10,10);
Write('Введите номер начальной вершины пути: '); Readln(Nac);
GotoXY(10,12);
Write('Введите номер конечной вершины пути: '); Readln(Kon);
Writeln;
Write('Длина пути из вершины ',Chr(64+Nac),' в вершину ',Chr(64+Kon),' равна: ',T[Nac,Kon]);
Readln {Задержка экрана}
End;
{----------------------------
Procedure Koordinata;
{---------------------------
{Процедура вывода найденных значений}
{---------------------------
Var
Q,W: Real;
K: Char;
X1,X2,Y1,Y2,
X: Integer;
Begin
Open_Graph; {Подключение графического режима}
Q:=2*Pi/N; {Установка значения угла между границами сектора}
{Задание координат вершин графа}
For I:=1 To N Do
Begin
W:=I*Q; {Установка текущего угла}
{Установка координат}
X1:=300+Trunc(R*cos(W)); Y1:=235+Trunc(R*sin(W));
X2:=300+Trunc((R+25)*cos(W)); Y2:=235+Trunc((R+25)*sin(W));
{-------------------}
K:=Chr(64+I); {Задание текущего названия вершины}
SetColor(White); {Задание цвета названий вершин}
OutTextXY(X2,Y2,K); {Вывод названия вершины}
SetColor(Green); {Задание цвета вершины}
For J:=1 To 7 Do
Circle(X1,Y1,J) {Вывод концентрических окружностей для задания вершины на экране}
End;
{Вывод кратчайшего пути}
X:=Nac;
W:=Q*Nac; {Установка текущего угла}
{Установка координат}
X1:=300+Trunc(R*cos(W)); Y1:=235+Trunc(R*sin(W));
{-------------------}
SetColor(Red);
PutPixel(X1,Y1,Red);
Repeat
X:=H[X,Kon]; {Переход на следующую вершину в пути}
W:=Q*X; {Установка текущего угла}
{Установка координат}
X2:=300+Trunc(R*cos(W)); Y2:=235+Trunc(R*sin(W));
{-------------------}
Line(X1,Y1,X2,Y2);
X1:=X2;
Y1:=Y2
Until X=Kon;
SetColor(White);
OutTextXY(3,450,'Press any key, please...');
Readln; {Задержка экрана}
Close_Graph; {Отключение графического режима}
Clrscr
End;
{----------------------------
{========================
Begin
{-----------------------}
{Основной блок программы}
{-----------------------}
ClrScr; {Очистка экрана}
TextBackGround(Black); {Задание цвета фона}
TextColor(White); {Задание цвета текста}
Clrscr;
Dlina; {Задание длин дуг}
Floid; {Поиск кратчайшего пути и его длины}
Koordinata {Вывод найденных значений}
End.
Рис.7. Пример построения графа.
Получение матрицы длин дуг:
Рис. 8. Матрица длин дуг, количество вершин-5.
Рис. 9. Матрица путей, количество вершин-5.
Рис. 10. Матрица длин путей, количество вершин-5.
Рис. 11. Ввод начальной и конечной вершины, количество вершин-5.
Рис. 12. Построение пути между вершинами графа, количество вершин-5.
2. Количество вершин 10.
Рис. 13. Матрица длин дуг, количество вершин-10.
Рис. 14. Матрица путей, количество вершин-10.
Рис. 15. Матрица длин путей, количество вершин-10.
Рис. 16. Ввод начальной и конечной вершины, количество вершин-10.
Рис. 17. Построение пути между вершинами графа, количество вершин-10.
Рис. 18. Матрица длин дуг, количество вершин-19.
Рис. 19. Матрица путей, количество вершин-19.
Рис. 20. Матрица длин путей, количество вершин-19.
Рис. 21. Ввод начальной и конечной вершины, количество вершин-19.
Рис. 22. Построение пути между вершинами графа, количество вершин-19.
5. Литература: