Пример программы с использованием матрицы смежности
Рассмотрим следующую задачу. Имеется ориентированный граф. Длиной пути считается число имеющихся в нем звеньев. Заданы две разные вершины (начало и конец) и целое число, определяющее макимально допустимую длину. Требуется построить минимальный граф путей ограниченной длины из начала в конец, то есть усечь граф так, чтобы:
· новый граф содержал все пути, соединяющие начало с концом и имеющие длины, не превышающие макимально допустимую длину;
· исключение любой вершины или дуги нового графа вело к нарушению первого условия.
Опишем алгоритм решения задачи. Вершины графа будем называть узлами, чтобы отличать их от вершины стека, используемого в этой задаче.
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.
Обход графа в глубину.
Поиск путей
Обходом графа называют посещение всех его вершин и ребер. Проще всего осуществляется обход в глубину с помощью стека.
Пусть граф неориентирован. Чтобы не путать вершину стека с вершинами графа, будем называть последние узлами. Пройденные узлы графа помечаются. В стеке хранится текущий путь, который инициализируется произвольным начальным узлом. Если из узла, находящегося в вершине стека, имеется ребро в непройденный узел, то этот узел помечается как пройденный и включается в стек. Исключение из стека происходит после прохождения всех ребер узла. Если стек становится пустым, процесс продолжается с какого-либо непомеченного узла. Трудоемкость обхода в глубину пропорциональна количеству ребер графа.
|
|
|
Вероятно, самой распространенной задачей на графах является поиск путей без циклов между заданными вершинами. Он может быть реализован на основе обхода в глубину. Если требуются все пути, вершины могут посещаться неоднократно. В этом случае пройденные вершины рассматриваются только для текущего пути. Исключение из стека происходит также после нахождения очередного пути. Описанный подход распространяется и для ориентированных графов. Такой способ нахождения решения является примером применения алгоритма с возвратами.
Трудоемкость перечисления всех путей на основе приведенного метода может быть очень высокой. Так для графа из N вершин, в котором каждая пара вершин связана ребром, число путей между двумя заданными вершинами оценивается астрономической величиной (N-2)! + (N-3)! + ….+ 2! + 1.
Приведем текст соответствующей программы.
Program Puti;{поиск путей в глубину на ориентированном графе}
Uses crt;
Const
max=10;
Type
mat=array[1..max,1..max] of integer; {матрица смежности }
put=1..max; { номер вершины в пути }
Var
matr : mat;
gr: array [1..max] of integer; { текущий путь }
zapret: array [1..max] of boolean;
{ запрет вершин: false-вершина запрещена }
a,b,ver,k,j,i: 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('Введите связи в виде пары вершин 99-конец) ');
Read(i);
if i<>99 then Read(j);
if (i>0) and (i<=ver) and (j>0) and (j<=ver) then
matr[i,j]:=1
else if i<>99 then Writeln('Ошибка ввода ')
Until i=99;
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; { добавление в путь текущей вершины }
Zapret[t]:=false;
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 Zapret[i] and (matr[t,i]=1) then
{ поиск в глубину: выбор продолжения пути без цикла }
PoiskPut(i);
{ здесь оказываемся после нахождения очередного пути }
{ или в случае попадания в тупик }
{ исключение из множества вершин пути последней вершины }
j:=j-1; { возврат в предыдущую вершину }
Zapret[t]:=true; {снятие зппрета}
End;
Begin { основная программа }
Clrscr; { очистка экрана }
ReadMat(matr); { ввод матрицы смежности }
l:=true;
While l do
begin
Wiwod(matr);
Writeln;
Write('Введите начальную вершину: ');
Readln(a);
Write('Введите конечную вершину: ');
Readln(b);
Writeln;
For i:=1 to ver do
Zapret[i]:=true; {все вершшины сначала разрешены}
j:=1;
PoiskPut(a); { перечисление всех путей }
Writeln('Путей больше нет ! ');
Write('Повторить поиск[д/н] ? ');
Readln(ch);
if ch='н' then l:=false { для выхода из цикла }
end
End.
В этой прграмме стек реализуется с помощью рекурсии. Рассмотрим порядок нахождения путей на примере. Пусть имеется граф
и требуется перечислить пути из вершины 1 в вершину 4. В процессе поиска в стеке будут находиться следующие номера вершин:
· 1;
· 1,3;
· 1,3,2;
· 1,3,2,4;
· 1,3,2;
· 1,3,2,5;
· 1,3,2,5,4;
· 1,3,2,5;
· 1,3,2;
· 1,3,4;
· 1,3;
· 1,3,6;
· 1,3;
· 1;
· 1,4;
· 1;
· Æ.
Последовательность обхода вершин графа можно представить деревом
Корнем дерева является начальная вершина, а листьями – конечная вершина либо тупиковые вершины, из которых нет продолжения пути без циклов. Последовательность нахождения путей соответствует обходу дерева в порядке сверху вниз.
Обход графа в ширину
При обходе в ширину вершины посещаются в порядке удаленности по числу дуг от выбранной начальной вершины. Для обхода в ширину часто используют очереди. Исходно очередь состоит из выбранной начальной вершины. В дальнейшем последовательно просматриваются элементы из начала очереди, а их преемники помещаются в конец очереди. Аналогично обходу в глубину помечаются посещенные вершины. После исчерпания очереди в качестве начальной выбирается какая-либо непомеченная вершина.
При поиске путей в глубину короткие по числу звеньев пути могут находиться далеко не в первую очередь. Так самым коротким в рассмотренном примере является прямой путь из 1 в 4, но этот путь находится последним.
Поиск путей в ширину сводится к проходу описанного дерева по уровням. В приведенном примере пути будут найдены в порядке
· 1,4;
· 1,3,4;
· 1,3,2,4;
· 1,3,2,5,4.
Поиск путей в ширину реализуется сложнее. Требуется помнить не один текущий путь, а все пути, способные привести к цели. Помимо очереди это можно обеспечить с помощью дерева, строящегося по уровням.
Дата добавления: 2018-11-24; просмотров: 202; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!