|
||||
|
ЛЕКЦИЯ № 10. Графы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. Представление графа списком инцидентности. Алгоритм обхода графа в глубинуДля реализации графа в виде списка инцидентности можно использовать следующий тип:
Тогда граф задается следующим образом:
Теперь обратимся к процедуре обхода графа. Это вспомогательный алгоритм, который позволяет просмотреть все вершины графа, проанализировать все информационные поля. Если рассматривать обход графа в глубину, то существуют два типа алгоритмов: рекурсивный и нерекурсивный. При рекурсивном алгоритме обхода графа в глубину мы берем произвольную вершину и, отыскиваем произвольную непросмотренную (новую) вершину v, смежную с ней. Затем принимаем вершину v за неновую и отыскиваем любую смежную с ней новую вершину. Если же у какой-либо вершины нет более новых непросмотренных вершин, то полагаем эту вершину использованной и возвращаемся на уровень выше в ту вершину, из которой попали в нашу использованную вершину. Обход продолжается таким образом до тех пор, пока в графе не останется новых непросмотренных вершин. На языке Pascal процедура обхода в глубину будет выглядеть следующим образом:
Примечание В данной процедуре при описании типа Graph имелось в виду описание графа списком списков. Массив nov[i] – специальный массив, i-ый элемент которого равен True, если i-ая вершина не просмотрена, и False – в противном случае. Также часто используется нерекурсивный алгоритм обхода. В этом случае рекурсия заменяется на стек. Как только вершина просмотрена, она помещается в стек, а использованной она становится, когда больше нет новых вершин, смежных с ней. 3. Представление графа списком списков. Алгоритм обхода графа в ширинуГраф можно определить с помощью списка списков следующим образом:
При обходе графа в ширину мы выбираем произвольную вершину и просматриваем сразу все вершины, смежные с ней. Вместо стека используется очередь. Алгоритм обхода в ширину очень удобен при нахождении наикратчайшего пути в графе. Приведем процедуру обхода графа в ширину на псевдокоде:
|
|
||
Главная | В избранное | Наш E-MAIL | Добавить материал | Нашёл ошибку | Вверх |
||||
|