Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Пути в бесконтурном графе




Пусть дан ориентированный граф G=<V,E> без контуров, веса дуг произвольны. Результатом является — массив кратчайших расстояний (длин) D от фиксированной вершины s до всех остальных. Утверждение — в произвольном бесконтурном графе вершины можно перенумеровать так, что для каждой дуги (i, j) номер вершины i будет меньше номера вершины j.

Пример.Введем следующие структуры данных:

массив NumIn, NumIn[i] определяет число дуг, входящих в вершину с но­мером i;

массив Num. Num[i] определяет новый номер вершины i;

массив St, для хранения номеров вершин, в которые захо­дит нулевое количество дуг. Работа с массивом осуществ­ляется по принципу стека;

переменная nm, текущий номер вершины.

Идея алгоритма.

Вершина i, имеющая нулевое значение Nu­mIn (а такая вершина на начальном этапе обязательно есть в силу отсутствия контуров в графе), заносится в St, ей присваи­вается текущее значение nm (запоминается в Num), и изменя­ются значения элементов NumIn для всех вершин, связанных с i. Процесс продолжается до тех пор, пока St не пуст.

На рисунке 6 приведен пример графа, а в таблице 3 представлены результаты трассировки работы алгоритма для этого примера.

 

 

Рис. 6

Таблица 3

№ итераций Numln Num St Nm
начальная [2,2,2,1,0,1] [0,0,0,0,0,0] [5]
12.2.1.0,0,1] [0,0,0,0.1,0] [4]
[1.2,0,0.0,1] [0,0,0,2,1,0] [3]
[0.2,0,0,0,0] [0,0,3.2.1,0] [6,1]
[0,1,0,0,0,0] [0.0,3,2.1,4] [1]
[0,0,0,0,0,01 [5,0,3,2,1,4] [2]
[0,0,0,0,0,0] [5,6,3,2,1.4] []

 

Procedure Change_Num; { *A, Num — глобальные струк туры данных. *}

Var NumIn,St:Array[1..N] Of Integer;

i,j,u,nm,yk:Integer;

Begin

FillChar (Numln,SizeOf (Numln) ,0) ;

For i:=2 To N Do

For j:-1 To N Do

If A[i,j]<>0 Then Inc (Numln (j}) ;

nm:=0;yk:=0;

For To N Do

If Numln [i]=0

Then

Begin Inc (yk);Stack[yk]:=i; End;

While yk<>0 Do

Begin

u:=Stack[yk];Dec[yk];Inc(nm);Num[u]:=nm;

For i:=1 To N Do

If A[u,i]<>0 Then

Begin

Dec(Numln[i));

If Numln [i] =0 Then

Begin Inc(yk); Stack (yk} ;=i; End;

End;

End;

End;

Итак, пусть для графа G выполнено условие утверждения (вершины перенумерованы) и нам необходимо найти кратчай­шие пути (их длины) от первой вершины до всех остальных. Пусть мы находим оценку для вершины с номером i. Достаточ­но просмотреть вершины, из которых идут дуги в вершину с номером i. Они имеют меньшие номера, и оценки для них уже известны. Остается выбрать меньшую из них.

Procedure Dist;(*D, А - глобальные величины.*}

Var i, j : Integer;

Begin

D[1]:=0;

For i:=2 To N Do D[i] : =МахInt-<максимальное значение в матрице смежности А>;{*Определите, с какой целью вычитается из Maxlnt максимальный элемент матрицы А. *}

For i:=2 То N Do

For j :=1 To i-1 Do

If A[j,i]<>

Then D[i] :=Min (D[i] ,D[j] +A[j, i]) ;

End;

Процедура написана в предположении о том, что i и j — но­вые номера вершин и A[i,j] соответствует этим номерам. Одна­ко это не так. Новые номера по результатам работы предыду­щей процедуры хранятся в массиве Num. Требуется «стыковка» новых номеров и матрицы А.

 


Поможем в написании учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой





Дата добавления: 2014-11-10; просмотров: 784. Нарушение авторских прав; Мы поможем в написании вашей работы!

Studopedia.info - Студопедия - 2014-2022 год . (0.017 сек.) русская версия | украинская версия
Поможем в написании
> Курсовые, контрольные, дипломные и другие работы со скидкой до 25%
3 569 лучших специалисов, готовы оказать помощь 24/7