Лекции по структурам и алгоритмам обработки данных (СиАОД). Первый семестр 6

Лекции по структурам и алгоритмам обработки данных (СиАОД). Первый семестр

стр.: 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16

Полный текст лекций можно скачать здесь

---

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

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

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

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

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

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.

4.3. Поиск путей на графе в глубину

Вероятно, самой распространенной задачей на графах является поиск путей без циклов между заданными вершинами. Проще всего реализуется поиск в глубину. В стеке хранится текущий путь, который инициализируется заданым начальным узлом графа. Если из узла, находящегося в вершине стека, имеется непройденная дуга в узел, не содержащийся в текущем пути, то этот узел включается в стек. Исключение из стека происходит после нахождения очередного пути и в том случае, когда не остается непройденных дуг. Такой способ нахождения решения является примером применения алгоритма с возвратами.

Рассмотрим следующую задачу. Имеется сеть железных дорог. По некоторым участкам движение возможно только в одном направлении. Известны расстояния всех участков дорог. Требуется перечислить все пути, ведущие из пункта А в пункт В, не проходящие дважды через один и тот же пункт. Приведем текст соответствующей программы.

Program Puti; { поиск путей в глубину на ориентированном графе }

Uses Crt;

Const

Max=20; { максимально допустимое число вершин графа }

Type

mat=array[1..Max,1..Max] of integer; { матрица смежности }

put=1..Max; { номер вершины в пути }

Var

Matr : mat;

M: set of put; { множество вершин, входящих в путь }

Gr: array [1..Max] of integer; { текущий путь }

A, B, Ver, K, I, J: integer;

L: boolean;

Ch: char;

Procedure ReadMat(var Matr: mat); { ввод матрицы смежности }

Begin

TextBackGround(Black);

TextColor(White);

ClrScr;

Write('Введите количество вершин графа: ');

ReadLn(Ver);

For I:=1 to Ver do

For J:=1 to Ver do

begin

Matr[I, J]:=0;

Matr[J, I]:=0

end;

Repeat

Write('Введите связи в виде пары вершин (-1 - конец) ');

Read(I);

if I<>-1 then Read(J);

if (I>0) and (I<=Ver) and (J>0) and (J<=Ver) then

Matr[I,J]:=1

else if I<>-1 then WriteLn('Ошибка ввода ')

Until I = -1;

WriteLn('Ввод закончен !');

WriteLn;

ReadLn { пауза }

End;

Procedure Wiwod(Matr: Mat);

Begin

Window(46,2,75,22); { окно вывода результатов }

TextBackGround(Cyan);

ClrScr;

TextColor(LightGreen);

Write(' ');

For I:=1 to Ver do

Write(i:2); { номера столбцов матрицы }

WriteLn;

For I:=1 to Ver do

begin

TextColor(LightGreen);

Write(I:2); { номера строк матрицы }

TextColor(White);

For J:=1 to Ver do

Write(Matr[I,J]:2);

WriteLn

end

End;

Procedure PoiskPut(T: integer);

{ поиск всех путей на графе }

Var I: integer;

Begin

Gr[J]:=T; { добавление в путь текущей вершины }

M:=M+[T]; { коррекция множества вершин пути }

J:=J+1;

if T=B then { B - конечная вершина }

begin

Write('Найден путь: ');

For I:=1 to J-1 do { вывод пути }

Write(Gr[I], ' ');

WriteLn;

ReadLn { пауза }

end

else

For I:=1 to Ver do

if not (I in M) and (Matr[T,I]=1) then

{ поиск в глубину: выбор продолжения пути без цикла }

PoiskPut(I);

{ здесь оказываемся после нахождения очередного пути }

{ или в случае попадания в тупик }

M:=M-[T];

{ исключение из множества вершин пути последней вершины }

J:=J-1 { возврат в предыдущую вершину }

End;

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

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

ReadMat(Matr); { ввод матрицы смежности }

L:=True;

While L do

begin

Wiwod(Matr);

WriteLn;

Write('Введите начальную вершину: ');

ReadLn(A);

Write('Введите конечную вершину: ');

ReadLn(B);

WriteLn;

J:=1; M:=[]; { инициализация множества вершин пути }

PoiskPut(A); { перечисление всех путей }

WriteLn('Путей больше нет ! ');

Write('Повторить поиск (д/н) ? ');

ReadLn(Ch);

if Ch='н' then L:=False { для выхода из цикла }

end

End.