1. Понятие графа. Способы
представления графа
Граф – пара G = (V,E), где V – множество
объектов произвольной природы, называемых вершинами, а Е – семейство пар ei =
(vil, vi2), vijOV, называемых ребрами. В общем случае множество V и
(или) семейство Е могут содержать бесконечное число элементов, но мы будем
рассматривать только конечные графы, т. е. графы, у которых как V, так и Е
конечны. Если порядок элементов, входящих в ei, имеет значение, то граф
называется ориентированным, сокращенно – орграф, иначе – неориентированным.
Ребра орграфа называются дугами. В дальнейшем будем считать, что
термин «граф», применяемый без уточнений (ориентированный или
неориентированный), обозначает неориентированный граф.
Если е = <u,v>, то вершины v и и
называются концами ребра. При этом говорят, что ребро е является смежным
(инцидентным) каждой из вершин v и и. Вершины v и и также называются смежными
(инцидентными). В общем случае допускаются ребра вида е = <v, v>;
такие ребра называются петлями.
Степень вершины графа – это число ребер,
инцидентных данной вершине, причем петли учитываются дважды. Поскольку каждое
ребро инцидентно двум вершинам, сумма степеней всех вершин графа равна
удвоенному количеству ребер: 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;
| 
