Пример программы с использованием матрицы смежности

Рассмотрим следующую задачу. Имеется ориентированный граф. Длиной пути считается число имеющихся в нем звеньев. Заданы две разные вершины (начало и конец) и целое число, определяющее макимально допустимую длину. Требуется построить минимальный граф путей ограниченной длины из начала в конец, то есть усечь граф так, чтобы:

· новый граф содержал все пути, соединяющие начало с концом и имеющие длины, не превышающие макимально допустимую длину;

· исключение любой вершины или дуги нового графа вело к нарушению первого условия.

Опишем алгоритм решения задачи. Вершины графа будем называть узлами, чтобы отличать их от вершины стека, используемого в этой задаче.

1. Ввод данных. Задание для каждого I-го узла

L1[I]:=1000 и L2[I]:= 1000 .

В массивы L1 и L2 будут занесены впоследствии минимальные длины от начала и до конца.

2. Занесение номера начального узла B в стек.

3. L1[B]:=0.

4. Если стек пуст, переход к 11.

5. Выбор узла i из вершины стека.

6. Если L1[I]=L, то исключить вершину стека и перейти к 4. Здесь L - максимально допустимая длина.

7. M:= L1[I] + 1 – текущая минимальная длина для последователей узла I.

8. Выбор очередного последователя (с номером J) узла I.

9. Если M < L1[J], то

· L1[J]:=M;

· занесение узла J в стек.

10. Если рассмотрены не все последователи узла I, переход к 8; иначе переход к 4.

11. Повторение шагов, аналогичных шагам 2-10, но в направлении от конца к началу с использованием массива L2.

12. В цикле по номерам узлов I простановка признаков запрета тем узлам, для которых

L1[I] + L2[I] > L .

13. Исключение из графа запрещенных узлов вместе с инцидентными им дугами.

14. Исключение из графа всех дуг из I-го узла в J-й по условию

L1[I] + L2[J] +1 >L .

15. Конец.

Для хранения узлов можно было использовать очередь, а не стек, что обеспечивает расстановку длин по возрастанию. В целях удобства прохода по графу в прямом и обратном направлениях выбрана форма представления графа на основе матрицы смежности. Приведем текст программы на ПАСКАЛЕ.

Program MinGraph;

{ Выделение минимального графа по началу, концу и длине }

{ Используется стек, расстановка пометок - в глубину }

Uses Crt;

Type

prizn=0..1;

uzel=record

Zapr: prizn; { 1-вершина запрещена, 0-нет }

L: array[1..2] of integer { длины вперед и назад }

end;

Var

M, N, I, J, K, Nb, Nk, Top, Len: integer;

Matr: array[1..20,1..20] of prizn; { матрица смежности }

Stek: array[1..20] of integer;

{ стек вершин, для сыновей которых расставляем длины }

Ver: array[1..20] of uzel; { индекс-номер вершины }

Procedure Rasstan(Napr: integer);

{ расстановка длин в массивах L1 или L2 }

{ Napr=1 - расстановка от начальной вершины к конечной }

{ Napr=2 - расстановка от конечной вершины к начальной }

Begin

Top:=1; { вершина стека }

if Napr=1 then Stek[1]:=Nb { Nb-начальная вершина }

else Stek[1]:=Nk; { Nk-конечная вершина }

Ver[Stek[1]].L[Napr]:=0;

While Top>0 do

begin

I:=Stek[Top];

Top:=Top-1;

if Ver[i].L[napr]<Len then

{ не достигли максимальной длины }

For J:=1 to N do

begin

if Napr=1 then K:=Matr[I,J]

else K:=Matr[J,I];

if K=1 then { есть связь }

begin

M:=Ver[i].L[Napr]+1;

if M<Ver[j].L[Napr] then

{ вершина впервые или на меньшем расстоянии }

begin

Ver[J].L[Napr]:=M;

Top:=Top+1;

Stek[Top]:=J { занесение в стек }

end

end

end

end

End;

Procedure Pech; { распечатка матрицы смежности }

Begin

For I:=1 to N do

begin

WriteLn;

For J:=1 to N do

Write(Matr[I, J],' ')

end

End;

Begin { основная программа }

ClrScr; { очистка экрана }

Write('Введите число вершин ');

ReadLn(n);

For I:=1 to N do

For j:=1 to n do

Matr[I,J]:=0;

For I:=1 to N do

begin

WriteLn('Занимаемся вершиной ', I, ':');

K:=1000;

While K>0 do

begin

Write('Введите номер очередного последователя вершины ', I,

' (-1 – признак конца) ');

ReadLn(K); { K<0-признак конца списка последователей }

if (K>0) and (K<=N) then

begin

Matr[I,K]:=1;

Ver[I].L[1]:=1000; { для будущего поиска минимума }

Ver[I].L[2]:=1000;

Ver[I].Zapr:=0 { запрета нет }

end

end

end;

Write('Введите номер начальной вершины ');

ReadLn(Nb);

Write('Введите номер конечной вершины ');

ReadLn(Nk);

Write('Введите максимальную длину ');

Readln(Len);

WriteLn;

WriteLn('Старая матрица смежности:');

Pech;

ReadLn; { пауза }

Rasstan(1); { расстановка длин вперед }

if Ver[Nk].L[1]>Len then

{ вершина Nk не встречалась или дальше, чем на Len звеньев }

begin

WriteLn(' Граф пуст !!!');

Exit

end;

Rasstan(2); { расстановка длин назад }

For I:=1 to N do { расстановка запретов на вершины }

if Ver[i].L[1]+Ver[i].L[2]>Len then Ver[i].Zapr:=1;

For I:=1 to N do { исправление матрицы смежности }

if Ver[i].Zapr=1 then { i-я вершина запрещена }

For J:=1 to N do

begin

Matr[I, J]:=0;

Matr[J, I]:=0

end;

For I:=1 to N do { анализ дуг матрицы смежности }

For J:=1 to N do

if Matr[I, J]=1 then

if Ver[i].L[1]+1+Ver[j].L[2]>Len then

Matr[I, J]:=0;

WriteLn;

WriteLn('Новая матрица смежности:');

Pech;

ReadLn

End.