Разработка алгоритмического и программного обеспечения для решения графовых задач (стр. 5 из 5)
Эти примеры демонстрируют, насколько широк диапазон приложений, для которых граф служит подходящей абстракцией, и, соответственно, диапазон вычислительных задач, с которыми доведется столкнуться при работе с графами.
Модели графов, в которых с каждым ребром связывают веса или стоимости, используются во многих приложениях. В картах авиалиний, в которых ребрами отмечены авиарейсы, такие веса означают расстояния или стоимость проезда. В электронных схемах, где ребра представляют электрические соединения, веса могут означать длину соединения, его стоимость или время, необходимое для распространения по ней сигнала. В задачах календарного планирования веса могут представлять время или расходы, затрачиваемые на выполнение задач, либо время ожидания завершения соответствующей задачи. Естественно, в таких ситуациях возникают вопросы, касающиеся различных аспектов минимизации стоимости. Наиболее изучены алгоритмы решения двух задач такого рода:
1) Определение пути с наименьшей стоимостью, соединяющего все точки;
2) Отыскание пути наименьшей стоимости, соединяющего две заданных точки.
Первый тип алгоритма применяется для решения задач на неориентированных графах, которые представляют такие объекты как электрические цепи, находит минимальное остовное дерево. Второй тип алгоритма, применяемый для решения задач на орграфах, которые представляют такие объекты, как карты авиарейсов, определяет кратчайшие пути. Эти алгоритмы находят широкое применение не только в приложениях, связанных со схемами авиарейсов и электрическими схемами, они используются также и при решении задач, возникающих во взвешенных графах.
Задача поиска минимального остовного дерева произвольного взвешенного неориентированного графа получила множество важных применений, и алгоритмы ее решения были известны, по меньшей мере, с двадцатых годов прошлого столетия. Тем не менее, эффективность ее реализации колеблется в широких пределах, а исследователи до сих пор заняты поисками более совершенных методов.
1. Кpистофидес, H. Теоpия гpафов. Алгоритмический подход. М. "Миp", 1978
2. Бондарев В.М., Рублинецкий В.И., Качко Е.Г. Основы программирования / Харьков: Фолио; Ростов на Дону: Феникс, 1997. – 368 .
3. Захарова, Л.Е. Алгоритмы дискретной математики: учебное пособие. – Моск. гос. ин-т электроники и математики. М., 2002, 120 с.
4. Кормен Т. Х., Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ, 2-е изд. — М.: Вильямс, 2005. — 1296 с.
5. Седжвик, Роберт Фундаментальные алгоритмы на C++. Алгоритмы на графах: Пер. с англ./ Роберт Седжвик. - СПб: ООО «ДиаСофтЮП», 2002. - 496 с.
6. http://www.algolist.manual.ru/links/
7. http://www.devel.vcity.ru/library.tmpl?05344_article_id=8
8. http://www.ergeal.ru/txt/archive/cs/discra/index.htm
9. Hечепуpенко, М.И. Алгоpитмы и пpогpаммы pешения задач на гpафах и сетях. – Hовосибиpск: Hаука, 1990
10. Алгоритм Флойда-Уоршелла // [Электронный ресурс]: Энциклопедия Википедия. – Электрон. дан. – Режим доступа: http://ru.wikipedia.org/wiki/Алгоритм_Флойда_—_Уоршелла. – Загл. с экрана.
11. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: Бином, 2000. – 960с.
12. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1988.
13. Липский В. Комбинаторика для программистов: Пер. с польск. – М.: Мир, 1988. – 213 с.
14. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2004. – 368с.
15. Оре О. Теория графов. – М.: Наука, 1980.
Реализация алгоритма Прима-Краскала на языке Паскаль
1. Листинг программы:
useswincrt;
Const
N=5; {N - число вершин графа}
type
Matrix=array[1..N,1..N] of Integer; {матрицарасстоянийграфа}
var
D,Ostov: Matrix; {D - матрица весов исходного графа, Ostov - матрица весов искомого остова}
color_of_top: array[1..N] of integer; {цветвершинграфа}
i,j,k,x,y,d_min: Integer; {d_min - текущая минимальная длина ребра}
ne_virozhd: Boolean;
BEGIN
ClrScr;
{Инициализируем граф - вводим матрицу весов графа D[i,j]}
for i:=1 to N do begin
WriteLn('Введите элементы ',i,'-й строки матрицы весов графа:');
WriteLn('Если вершины не связаны ребром - вводим любое отрицательное число');
for j:=1 to N do begin
Write('D[',i,',',j,']='); Read(D[i,j]);
end;
end;
{Выводим матрицу весов графа D[i,j]}
WriteLn;
WriteLn('Матрица весов графа:');
for i:=1 to N do begin
for j:=1 to N do begin
If D[i,j]>=0 then Write(D[i,j]:5) else Write(' x');
end;
WriteLn;
end;
{Инициализируем матрицу остовного дерева графа}
for i:=1 to N do
for j:=1 to N do
Ostov[i,j]:=0;
{"Раскрашиваем" вершины графа в разные цвета}
for i:=1 to N do
color_of_top[i]:=i;
k:=0; {k - число ребер остовного дерева}
ne_virozhd:=false;
{Общий шаг алгоритма}
whilek<N-1 dobegin
{Задаем первоначальное значение длины искомого ребра, заведомо большее всех имеющихся у графа}
d_min:= 30000;
{Находим ребро минимальной длины, не включенное до этого в остов графа}
for i:=1 to N-1 do
for j:=i+1 to N do
if (i<>j)and(D[i,j]>0) and (D[i,j]<d_min) and (color_of_top[i]<>color_of_top[j]) then
begin
d_min:=D[i,j];
x:=i;
y:=j;
ne_virozhd:=true;
end;
if ne_virozhd=true then begin
{Включаем найденное ребро минимальной длины в остов}
Ostov[x,y]:=D[x,y];
{Меняем цвет всех вершин, входящих в остов, на один цвет}
for i:=1 to N do
if color_of_top[i] = y then color_of_top[i] := x;
end;
{Увеличиваем количество рассмотренных ребер}
k:=k+1;
end;
{Выводим матрицу весов остова}
WriteLn;
WriteLn('Искомая матрица весов остова:');
for i:=1 to N do begin
for j:=1 to N do begin
If Ostov[i,j]>0 then Write(Ostov[i,j]:5) else Write(' x');
end;
WriteLn;
end;
END.
2. Блок-схема алгоритма
