Курсовая работа: Алгоритмы на графах. Кратчайшие расстояния на графах

- необходимая память вычисляется по формуле

MaxS = S + k -1

где S - найдено на предыдущем шаге (DFS1),

а k - максимальное количество вершин одного уровня вложенности с такой же степенью S.

Для вычисления k совершается обход повторным поиском в глубину DFS2

- третьим поиском в глубину DFS3 находим и помещаем в очередь V все вершины, степень которых равна S.

- последним, четвертым поиском в глубину обходим данное дерево в порядке вершин в очереди V. То есть, в первую очередь вычисляем те функции, для которых требуется максимальная память.

Рассмотрим реализацию алгоритма более подробно.

Ввод исходных данных осуществляется следующим образом:

read(N,FC);

for i:=1 to N do

begin

read(f,kG[f]);

for j:=1 to kG[f] do read(G[f,j]);

end;

Здесь

N - исходное количество вершин,

FC - номер функции, которую нужно вычислить

kG[i] - количество параметров для вычисления функции i

G[i,j] - j-тый параметр, требуемый для вычисления функции i

Тело главной программы выглядит так :

for i:=1 to N do color[i]:=WHITE;

{пометить свободными все вершины}

DFS1(FC);

{находим S - максимальную степень вершин используемых для вычисления функции FC}

MaxS:=S;

DFS2(FC);

{Вычисляем K - количество вершин со степенью S в текущем слое и MaxS - максимальная из значений по слоям величина S+K-1}

kv:=0;