- Лекции по структурам и алгоритмам обработки данных (СиАОД). Первый семестрПолный текст лекций можно скачать здесь
- 4.2. Пример программы с использованием матрицы смежности
Рассмотрим следующую задачу. Имеется ориентированный граф. Длиной пути считается число имеющихся в нем звеньев. Заданы две разные вершины (начало и конец) и целое число, определяющее макимально допустимую длину. Требуется построить минимальный граф путей ограниченной длины из начала в конец, то есть усечь граф так, чтобы:
новый граф содержал все пути, соединяющие начало с концом и имеющие длины, не превышающие макимально допустимую длину;
исключение любой вершины или дуги нового графа вело к нарушению первого условия.
Опишем алгоритм решения задачи. Вершины графа будем называть узлами, чтобы отличать их от вершины стека, используемого в этой задаче.
Ввод данных. Задание для каждого I-го узла
L1[I]:=1000 и L2[I]:= 1000 .
В массивы L1 и L2 будут занесены впоследствии минимальные длины от начала и до конца.
Занесение номера начального узла B в стек.
L1[B]:=0.
Если стек пуст, переход к 11.
Выбор узла i из вершины стека.
Если L1[I]=L, то исключить вершину стека и перейти к 4. Здесь L - максимально допустимая длина.
M:= L1[I] + 1 – текущая минимальная длина для последователей узла I.
Выбор очередного последователя (с номером J) узла I.
Если M < L1[J], то
L1[J]:=M;
занесение узла J в стек.
Если рассмотрены не все последователи узла I, переход к 8; иначе переход к 4.
Повторение шагов, аналогичных шагам 2-10, но в направлении от конца к началу с использованием массива L2.
В цикле по номерам узлов I простановка признаков запрета тем узлам, для которых
L1[I] + L2[I] > L .
Исключение из графа запрещенных узлов вместе с инцидентными им дугами.
Исключение из графа всех дуг из I-го узла в J-й по условию
L1[I] + L2[J] +1 >L .
Конец.
Для хранения узлов можно было использовать очередь, а не стек, что обеспечивает расстановку длин по возрастанию. В целях удобства прохода по графу в прямом и обратном направлениях выбрана форма представления графа на основе матрицы смежности. Приведем текст программы на ПАСКАЛЕ.
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.