5. Графы

Неориентированный граф представляет собой пару G=<V,E> где V -множество вершин (иногда используют термин дзет). Е - множество рёбер, соединяющих некоторые пары вершин. Количество вершин в графе будем обозначать как |V| (т.е. мощность множества V) или буквой n. количество рёбер -| Е| или е.

Ориентированный граф отличается тем. что для рёбер заданы направления. Ориентированные рёбра также называют дугами (иногда мы будем использовать термин "ребро", когда рассуждения применимы для обоих типов графов). Ребро, соединяющее вершину саму с собой, называется петлёй. Если такие рёбра не допускаются, то говорят, что задан граф без петель.

Один из возможных способов представления графа - простое перечисление рёбер в виде массива или связного списка – (см. рис. 3.3 Ь). Такой способ достаточно компактен, но применяется редко, поскольку выполнение любой из вышеперечисленных операций требует полного просмотра всего списка.

Часто используемым представлением графа является матрица смежности. В матрице смежности а элемент t7[i][j] равен 1, если вершина i смежна с вершиной j. и 0, если это не так. Заметим, что для каждого элемента матрицы смежности достаточно одного бита, поэтому для экономии памяти её можно реалнзовыватъ как битовый массив. Кроме того, для неориентированных графов матрица смежности будет симметрична относительно главной диагонали, поэтому будет достаточно хранить только одну её половину.

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

При таком подходе эффективно реализуется получение списка рёбер, выходящих из заданной вершины. Однако, чтобы проверить, смежны ли вершины а и Ъ, необходимо пройти по списку вершины а. Данный способ целесообразно применять для разреженных графов, в которых число рёбер существенно меньше |V|".

Разновидность данного подхода представлена на рис. 3.3 е). Здесь предполагается, что при работе с графом не требуется удалять или добавлять новые рёбра, поэтому вместо связных структур списки смежности хранятся в обычном массиве, что экономит память (нет необходимости хранить указатели).

1. Поиск в ширину Поиск в ширину (известный также как метод волны) позволяет найти в графе кратчайшие пути от заданной вершины до всех остальных (длиной пути считается число дуг в нём).

Алгоритм выглядит следующим образом. Пусть а - начальная вершина. Поместим вершину а в очередь и отметим её как посещенную.

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

2. Поиск в глубину лежит в основе или является важной составной частью огромного количества алгоритмов обработки графов.

Процесс поиска в глубину обычно можно начинать с любой вершины. Эта вершина отмечается как посещенная, после чего мы переходим к первой смежной с ней непосещённой вершине. С ней повторяется то же самое н т.д., пока это возможно. На рис. 3.6 под буквой а) мы. начав с вершины а, таким образом дойдём до вершины с по пути а—b—с.

Далее возвратимся на шаг назад, возьмём следующую смежную непосещённую вершину н т.д. В нашем примере мы возвращаемся к Ь. переходим от неё к вершине d и снова возвращаемся к о. Поскольку непосещенных вершин, смежных с Ь, больше не осталось, то возвращаемся к а. От вершины а также идти дальше некуда.

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

в качестве начальной и повторить всё сначала. В нашем примере ещё остались необработанные вершины е. f и g. поэтому берём очередную вершину е и снова повторяем для неё описанный алгоритм.

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

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