А. Цветкова - Информатика и информационные технологии - конспект лекций

3. Список смежности (инцидентности).

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

Список смежности более эффективен по сравнению с матрицей смежности, так как исключает хранение нулевых элементов.

4. Список списков.

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

Для реализации графа в виде списка инцидентности можно использовать следующий тип:

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 – в противном случае.

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

Граф можно определить с помощью списка списков следующим образом:

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;

Исторически первым подходом в программировании являлось процедурное программирование, иначе называемое программированием снизу вверх. Вначале создавались общие библиотеки стандартных программ, используемые в различных областях применения ЭВМ. Затем на основе этих программ создавались более сложные программы для решения конкретных задач.

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