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

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

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

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

---

if T<>Nil then

Begin

Rasch(T^.Left);

Rasch(T^.Right);

if T^.Left<>Nil then { не лист }

if T^.Pr='a' then { И-вершина }

begin

Kon:=T^.Left;

While Kon<>Nil do

begin

T^.SumNov:=T^.SumNov+Kon^.SumNov;

Kon:=Kon^.Right

end

end

else { ИЛИ-вершина }

begin

Kon:=T^.Left;

M:=-1;

While Kon<>Nil do

begin

Kon^.Zapret:='z'; { сначала запрет }

if Kon^.SumNov>M then

begin

M:=Kon^.SumNov;

Rab:=Kon

end;

Kon:=Kon^.Right { следующий сын }

end;

T^.SumNov:=M;

Rab^.Zapret:='r'; { оставили лучшую вершину }

end;

T^.SumNov:=T^.SumNov+T^.nov; { учет возможной оценки отца }

end

End;

Procedure Pech(T: ukaz);

{ печать сверху вниз лучшего (незапрещенного) элемента }

Begin

if T <> Nil then

begin

if T^.Pr='a' then Namer:=' (И-вершина) '

else if T^.Pr='o' then Namer:=' (ИЛИ-вершина) '

else Namer:=' (лист дерева) ';

if T^.Zapret<>'z' then

begin

Write(T^.Name,Namer);

WriteLn(' оценка новизны - ', T^.SumNov);

end;

Pech(T^.Left);

Pech(T^.Right)

end

End;

Begin

ClrScr;

New(Root);

Sozd(Root);

WriteLn('Дерево создано !');

ReadLn; { пауза }

Rasch(Root);

WriteLn('Расчет проведен !');

ReadLn;

WriteLn('Лучший элемент !');

Pech(Root);

ReadLn

End.

3.4. Прошитые деревья. Леса

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

Легко видеть, что для обхода прошитого дерева стек не нужен, однако корректировка таких деревьев существенно труднее. Например, при удалении поддерева с корнем в вершине, на которую указывает нить, требуется найти, откуда идет эта нить и куда направлена последняя нить удаляемого поддерева. Найденные вершины должны быть соединены новой нитью.

Прошивка чаще применяется для обхода сверху вниз, возможна для обхода слева направо, но требует дополнительного указателя для обхода снизу вверх. Действительно, при подъеме из вершины с обоими сыновьями свободного указателя для нити нет.

Множество деревьев называют лесом. Для представления леса помимо работы со списком деревьев иногда используют дополнительную вершину, сыновьями которой являются корни деревьев. Тогда обход всего леса сводится к обходу единственного дерева. Нужно только иметь в виду, что корень этого дерева – фиктивная вершина, добавленная для удобства обработки.

4. Графы

4.1. Представление графа. Транзитивное замыкание

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

Для представления графа чаще всего используют матрицу смежности, состоящей из нулей и единиц. Пусть имеется граф из n вершин V₁, V₂, …, V_n. Элемент a_ij матрицы смежности A равен 1, если имеется дуга из вершины V_i в вершину V_j, и 0 в противоположном случае. Для неориентированных графов матрица смежности симметрическая. Вместо нулей и единиц иногда задают другую информацию. Например, для дорог элемент a_ij может задавать расстояние между пунктами или время проезда.

Для каждой вершины V_i строка с номером i определяет возможных последователей, а i-й столбец – предшественников.

Количество путей между вершинами V_i и V_j, состоящих ровно из двух звеньев, определяется выражением

,

где суммирование ведется по всем промежуточным вершинам, для которых есть дуги из V_i и в V_j . Приведенное выражение определяет элементы матрицы A². Аналогично, число путей, состоящих ровно из трех звеньев, определяет матрица A³, а число путей, не превышающих трех звеньев, можно задает матрица

B₃= A + A² + A³.

Можно доказать по индукции, что общее число путей между всеми парами вершин длины не более m звеньев определяется матрицей

B₃= A + A² + …+A^m.

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

Матрицей достижимости P называют матрицу из нулей и единиц, элемент p_ij которой равен 1, если имеется какой-либо путь из вершины V_i в вершину V_j, и 0 в противоположном случае. Если считать каждую вершину достижимой из самой себя, то ненулевые элементы матрицы B_n-1 определяют единицы матрицы достижимости. Иными словами, мы получим матрицу достижимости, если при вычислении B_n-1 считать, что единица кодирует истину, а ноль – ложь, и использовать логические операции AND и OR вместо умножения и сложения.

Матрицу достижимости называют еще транзитивным замыканием матрицы смежности. Описанный способ нахождения транзитивного замыкания отличается высокой трудоемкостью вычислений. Рассмотрим алгоритм Уоршела, дающий более эффективный способ построения транзитивного замыкания.

Пусть элемент p_ij^(k) матрицы P^(k) равен 1, если существует путь из вершины V_i в вершину V_j с номерами промежуточных вершин, не превосходящими k, и 0 в противоположном случае. Тогда выполняется рекуррентное соотношение

где в качестве сложения и умножения фигурируют логические операции OR и AND.

Действительно, если имеется путь из V_i в V_j с номерами промежуточных вершин, не превосходящими k, то оба элемента p_ij^(k) и p_ij^(k+1) равны 1. Если же такого пути нет, но он появляется при добавлении вершины V_k+1 , то этот путь обязательно проходит через V_k+1 .

В качестве P⁽⁰⁾ выбирается исходная матрица смежности. Матрица P⁽ⁿ⁾ будет транзитивным замыканием, так как в ней не остается никаких ограничений на промежуточные вершины возможных путей.

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

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

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

Рассмотрим один из вариантов динамического представления графов. Снова первый список соответствует вершинам. В каждой вершине имеется указатель на список дуг, исходящих из этой вершины. Дуга помимо ссылки на следующую дугу имеет указатель на ту вершину, в которую она направлена.

Пусть имеется граф

Приведенный способ представления приводит к следующей структуре:

Nil

Nil

Nil

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

Ниже приведен пример программы, обеспечивающей ввод и корректировку графа в описанном представлении.

Program Graph;

{ создание и распечатка графа }

Uses Crt;

Type

ukaz=^uzel;

point=^duga;

uzel=record { список вершин графа }

Nom: integer;

Next: ukaz;

Sv: point

end;

duga=record { структура дуги графа }

Next: point;

Sv: ukaz

end;

Var

A, B: integer;

L: boolean;

Top, Kon, Ua, Ub: ukaz;

P, Q: point;

Ch: char;

Begin

L:=True; Top:=Nil;

While L do

Begin

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

Read(A);

if A=-1 then

begin

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

WriteLn;

L:=False

end

else

begin

Read(B);

Kon:=Top;

Ua:=Nil; Ub:=Nil;

While Kon<>Nil do

begin

if Kon^.Nom=A then Ua:=Kon;

if Kon^.Nom=B then Ub:=Kon;

if (Ua<>Nil) and (Ub<>Nil) then Kon:=Nil;

if Kon<>Nil then Kon:=Kon^.Next

end;

if Ua=Nil then { A-новая вершина }

begin

New(ua);

Ua^.Nom:=A;

Ua^.Next:=Top;

Top:=Ua;

Ua^.Sv:=Nil

end;

if Ub=Nil then { B-новая вершина }

begin

New(Ub);

Ub^.Nom:=B;

Ub^.Next:=Top;

Top:=Ub;

Ub^.Sv:=Nil

end;

if Ua^.Sv=Nil then { нет дуг у вершины A }

begin

New(p);

Ua^.Sv:=P;

P^.Next:=Nil;

P^.Sv:=Ub

end

else { есть дуги }

begin

Q:=Ua^.Sv; { первая дуга }

New(p);

P^.Next:=Q^.Next;

Q^.Next:=P;

P^.Sv:=Ub { вставка после первой дуги }

end

end

end; { конец While }

Ua:=Top;

While Ua<>Nil do

begin

WriteLn('Вершина ', Ua^.Nom);

P:=Ua^.Sv;

if P<>Nil then Write('Последователи: ')

else Write('Последователей нет !');

While P<>Nil do

begin

Kon:=P^.Sv;

B:=Kon^.Nom;

Write(B,' ');

P:=P^.Next

end;

WriteLn;

Ua:=Ua^.Next

end;

Ch:=ReadKey { пауза }

End.

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