Графы.

Графом называется структура данных, представляющая собой совокупность множества вершин V и множества ребер E. То есть формально граф можно записать как G = G(V, E).

Примеры графов.

graph

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

Теория графов возникла в 1736 году при решении известным математиком Леонардом Эйлером задачи о Кенигсбергских мостах (ныне город-анклав Калининград). Эта математическая задача заключалась в следующем: посетить каждый из семи мостов, проходя по ним не более одного раза. Впоследствии было определено, что данная задача решения не имеет.

kenigsberg

 

Вообще теория графов обрела свою популярность не сразу и долгое время воспринималась не всерьез.

Но постепенно область развивалась, и в 21 веке, во много в связи с бурным развитием вычислительной техники, уже является одним из основных инструментов при решении таких задач, как планирование автомобильных маршрутов, авиаперелетов, решение транспортных задач, планирования и даже приложений искусственного интеллекта. Основные преимущества графов в их наглядности и аналогии с реальным миром, со структурой описываемых задач. Действительно, очень удобным и понятным кажется при решении задач планирования маршрута из города А в город B изображать их в виде узлов или вершин, а дороги между населенными пунктами в виде соединяющих их ребер. Пример графа изображен на рисунке ниже:

%d0%b3%d1%80%d0%b0%d1%84%d1%8b

Раз уж мы заговорили о конкретных примерах, то следующим хотелось бы рассказать о разновидностях графов, коих на самом деле довольно много. Но мы упомянем только основные.

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

orient_graph

По учету весовых коэффицентов: взвешенные и невзвешенные. Граф называется взвешенным, если его ребру поставлено в соответствие некоторое числовое значение. В задачи определения маршрута число может означать длину между городами в километрах. А при решении задач планирования они могут определять временной интервал между задачами.

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

Ниже приведен пример взвешенного неориентированного графа.

weight_graph

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

relate_graph

Способы представления графов в компьютере.

Перед этим дадим определении смежности двух вершин i и j. Две вершины называются смежными, если они соединены между собой одним ребром.

Для представления графа в памяти компьютера существует несколько способов. Основными являются матрица смежности и списки смежности.

Матрица смежности — это квадратная матрица размером N*N, где N — число вершин в графе. Если вершина i соединена с вершиной j ребром. то элемент M[i, j] = 1, в обратном случае на пересечении i-го строки и j-го столбца будет стоять 0. Такое представление позволяет быстро определять, соединены ли пары вершин ребром или нет. Недостатком матрицы смежности могут служить большие затраты памяти для хранения больших разреженных графов. На рисунке ниже вы можете проверить, насколько матричное представление графа правильно отображает сам граф.

graph_matrix

Например, вершины 1 и 2 соединены ребром, и оно направлено от 1 к 2. Значит в ячейке матрицы M[1, 2] должна стоять единица, а в ячейке M[2, 1] — ноль, так как ребро направлено только в одну сторону. Если бы граф был неориентированным, то пришлось бы в обе ячейки поставить единицы.

Список смежности — для реализации хранения разреженных графов применяются связные списки. Как вы уже наверное догадались, проверка наличия ребра между двумя вершинами в этом случае затрудняется, что наверно не слишком удобно для плотных графов. Но гораздо эффективнее для работы с разреженными графами.

Реализация графа на языке Java.

Давайте определимся с тем, как мы будем хранить наш граф в памяти, чтобы затем с ним можно было работать и приступить к реализации алгоритмов. Во-первых, опишем класс Vertex, представляющий отдельную вершину графа:

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

Теперь создадим класс Graph для представления самого графа. Он будет содержать массив vertexArray для удобного доступа к вершинам графа и матрицу смежности размерности N*N(где N — количество вершин) для представления связей между вершинами в графе. При создании графа матрица смежности заполняется нулями:

Теперь представим, что мы работаем с неориентированным графом. Чуть выше мы уже говорили об особенностях представления ориентированных и неориентированных графов при помощи матрицы смежности. Сначала реализуем метод для добавления новой вершины в граф:

Мы просто добавляем вершину в последнюю незанятую ячейку массива. Теперь реализуем метод для добавления нового ребра:

В качестве параметра метод принимает индексы начальной и конечной вершин, которые нужно соединить между собой ребром. Эти индексы соответствуют индексам вершин из вспомогательного массива vertexArray.

Обход графа.

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

Обход в глубину.

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

Теперь предоставляем реализацию самого метода обхода в глубину:

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

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

Обход в ширину.

Алгоритм также начинает свою работу с некоторой вершины v. При раскрытии каждого узла мы получаем перечень дочерних вершин. Далее мы последовательно раскрываем уже эти вершины, находя всех потомков каждой из них. В отличие от поиска в глубину мы не двигаемся вглубь графа до тех пор, пока не раскрыты все вершины рассматриваемого узла. В таком случае мы двигаемся как бы вширь графа, не продвигаясь дальше, пока не будут раскрыты все вершины на текущем уровне глубины. Отсюда и название метода — обход в ширину. Основное отличие заключается в том, что для реализации данного вида обхода используется очередь, а не стек.

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

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *