Else
Delete2(p^.left);
End;
End.
ЛЕКЦИЯ № 10. Графы
1. Понятие графа. Способы представления графа
Граф – пара G = (V,E), где V – множество объектов произвольной природы, называемых вершинами, а Е – семейство пар ei = (vil, vi2), vijOV, называемых ребрами. В общем случае множество V и (или) семейство Е могут содержать бесконечное число элементов, но мы будем рассматривать только конечные графы, т. е. графы, у которых как V, так и Е конечны. Если порядок элементов, входящих в ei, имеет значение, то граф называется ориентированным, сокращенно – орграф, иначе – неориентированным. Ребра орграфа называются дугами. В дальнейшем будем считать, что термин «граф», применяемый без уточнений (ориентированный или неориентированный), обозначает неориентированный граф.
Если е =
Степень вершины графа – это число ребер, инцидентных данной вершине, причем петли учитываются дважды. Поскольку каждое ребро инцидентно двум вершинам, сумма степеней всех вершин графа равна удвоенному количеству ребер: Sum(deg(vi), i=1…|V|) = 2 * |E|.
Вес вершины – число (действительное, целое или рациональное), поставленное в соответствие данной вершине (интерпретируется как стоимость, пропускная способность и т. д.). Вес, длина ребра – число или несколько чисел, которые интерпретируются как длина, пропускная способность и т. д.
Путем в графе (или маршрутом в орграфе) называется чередующаяся последовательность вершин и ребер (или дуг – в орграфе) вида v0, (v0,v1), v1…, (vn – 1,vn), vn. Число n называется длиной пути. Путь без повторяющихся ребер называется цепью, без повторяющихся вершин – простой цепью. Путь может быть замкнутым (v0 = vn). Замкнутый путь без повторяющихся ребер называется циклом (или контуром в орграфе); без повторяющихся вершин (кроме первой и последней) – простым циклом.
Граф называется связным, если существует путь между любыми двумя его вершинами, и несвязным – в противном случае. Несвязный граф состоит из нескольких связных компонент (связных подграфов).
Существуют различные способы представления графов. Рассмотрим каждый из них в отдельности.
1. Матрица инцидентности.
Это прямоугольная матрица размерности n х щ, где n – количество вершин, am – количество ребер. Значения элементов матрицы определяются следующим образом: если ребро xi и вершина vj инцидентны, то значение соотвествующего элемента матрицы равно единице, в противном случае значение равно нулю. Для ориентированных графов матрица инцидентности строится по следующему принципу: значение элемента равно – 1, если ребро xi исходит из вершины vj, равно 1, если ребро xi заходит в вершину vj, и равно О в противном случае.
2. Матрица смежности.
Это квадратная матрица размерности n х n, где n – количество вершин. Если вершины vi и vj смежны, т. е. если существует ребро, их соединяющее, то соответствующий элемент матрицы равен единице, в противном случае он равен нулю. Правила построения данной матрицы для ориентированного и неориентированного графов не отличаются. Матрица смежности более компактна, чем матрица инцидентности. Следует заметить, что эта матрица также сильно разрежена, однако в случае неориентированного графа она является симметричной относительно главной диагонали, поэтому можно хранить не всю матрицу, а только ее половину (треугольную матрицу).
3. Список смежности (инцидентности).
Представляет собой структуру данных, которая для каждой вершины графа хранит список смежных с ней вершин. Список представляет собой массив указателей, i-ый элемент которого содержит указатель на список вершин, смежных с i-ой вершиной.
Список смежности более эффективен по сравнению с матрицей смежности, так как исключает хранение нулевых элементов.
4. Список списков.
Представляет собой древовидную структуру данных, в которой одна ветвь содержит списки вершин, смежных для каждой из вершин графа, а вторая ветвь указывает на очередную вершину графа. Такой способ представления графа является наиболее оптимальным.
2. Представление графа списком инцидентности. Алгоритм обхода графа в глубину
Для реализации графа в виде списка инцидентности можно использовать следующий тип:
Type List = ^S;
S = record;
inf : Byte;
next : List;
end;
Тогда граф задается следующим образом:
Var Gr : array[1..n] of List;
Теперь обратимся к процедуре обхода графа. Это вспомогательный алгоритм, который позволяет просмотреть все вершины графа, проанализировать все информационные поля. Если рассматривать обход графа в глубину, то существуют два типа алгоритмов: рекурсивный и нерекурсивный.
При рекурсивном алгоритме обхода графа в глубину мы берем произвольную вершину и, отыскиваем произвольную непросмотренную (новую) вершину v, смежную с ней. Затем принимаем вершину v за неновую и отыскиваем любую смежную с ней новую вершину. Если же у какой-либо вершины нет более новых непросмотренных вершин, то полагаем эту вершину использованной и возвращаемся на уровень выше в ту вершину, из которой попали в нашу использованную вершину. Обход продолжается таким образом до тех пор, пока в графе не останется новых непросмотренных вершин.
На языке Pascal процедура обхода в глубину будет выглядеть следующим образом:
Procedure Obhod(gr : Graph; k : Byte);
Var g : Graph; l : List;
Begin
nov[k] := false;
g := gr;
While g^.inf <> k do
g := g^.next;
l := g^.smeg;
While l <> nil do begin
If nov[l^.inf] then Obhod(gr, l^.inf);
l := l^.next;
End;
End;
Примечание
В данной процедуре при описании типа Graph имелось в виду описание графа списком списков. Массив nov[i] – специальный массив, i-ый элемент которого равен True, если i-ая вершина не просмотрена, и False – в противном случае.
Также часто используется нерекурсивный алгоритм обхода. В этом случае рекурсия заменяется на стек. Как только вершина просмотрена, она помещается в стек, а использованной она становится, когда больше нет новых вершин, смежных с ней.
3. Представление графа списком списков. Алгоритм обхода графа в ширину
Граф можно определить с помощью списка списков следующим образом:
Type List = ^Tlist;
Tlist = record
inf : Byte;
next : List;
end;
Graph = ^TGpaph;
TGpaph = record
inf : Byte;
smeg : List;
next : Graph;
end;
При обходе графа в ширину мы выбираем произвольную вершину и просматриваем сразу все вершины, смежные с ней. Вместо стека используется очередь. Алгоритм обхода в ширину очень удобен при нахождении наикратчайшего пути в графе.
Приведем процедуру обхода графа в ширину на псевдокоде:
Procedure Obhod2(v);
{величины spisok, nov – глобальные}
Begin
queue = O;
queue <= v;
nov[v] = False;
While queue <> O do
Begin
p <= queue;
For u in spisok(p) do
If nov[u] then
Begin
nov[u] := False;
queue <= u;
End;
End;
End;
ЛЕКЦИЯ № 11. Объектный тип данных
1. Объектный тип в Pascal. Понятие объекта, его описание и использование
Исторически первым подходом в программировании являлось процедурное программирование, иначе называемое программированием снизу вверх. Вначале создавались общие библиотеки стандартных программ, используемые в различных областях применения ЭВМ. Затем на основе этих программ создавались более сложные программы для решения конкретных задач.
Однако вычислительная техника постоянно развивалась, ее стали применять для решения различных задач производства, экономики, в связи с чем возникла необходимость обработки данных различного формата и решения нестандартных задач (например, нечислового характера). Поэтому при разработке языков программирования стали обращать внимание на создание различных типов данных. Это способствовало появлению таких сложных типов данных, как комбинированные, множественные, строковые, файловые и др. Прежде чем решать задачу, программист проводил декомпозицию, т. е. разбиение задачи на несколько подзадач, для каждой из которых писался свой отдельный модуль. Основная технология программирования включала в себя три этапа:
1) проектирование сверху вниз;
2) модульное программирование;
3) структурное кодирование.
Но начиная с середины 60-х г. XX в., стали формироваться новые понятия и подходы, которые легли в основу технологии объектно-ориентированного программирования. В данном подходе осуществляется моделирование и описание реального мира на уровне понятий конкретной предметной области, к которой относится решаемая задача.
Объектно-ориентированное программирование представляет собой метод программирования, который весьма близко напоминает наше поведение. Оно является естественной эволюцией более ранних нововведений в разработке языков программирования. Объектно-ориентированное программирование является более структурным, чем все предыдущие разработки, касающиеся структурного программирования. Оно также является более модульным и более абстрактным, чем предыдущие попытки абстрагирования данных и переноса деталей программирования на внутренний уровень. Объектно-ориентированный язык программирования характеризуется тремя основными свойствами:
1) Инкапсуляцией. Комбинирование записей с процедурами и функциями, манипулирующими полями этих записей, формирует новый тип данных – объект;