Блог для любопытных и не только
Структуры

Графы

  • Название: Граф;
  • Применение: Способ хранения данных;
  • Время выполнения: зависит от типа представления;
  • Сложность: Средний;
  • Входные параметры: Массив;
  • Результат: Представление данных в виде упорядоченных вершин и ребер

Пример из жизни:

Очень часто люди даже не задумываясь пользуются математическими моделями или абстракциями. Например, бытовая задача — покрасить комнату 3 на 4 метра. Необходимо рассчитать площадь, для этого нужно реальную комнату заменить абстракцией в виде прямоугольника и соответственно перемножить длину на ширину. Задача решена!

Итак, а если необходимо составить туристический маршрут из точки «А» в «B»? На ум приходит отрезок или ломаная линия. Т.е. прежде чем отправиться в путь, турист так же должен заменить реальный маршрут абстрактной моделью в виде ломанной кривой, где точки соеднинения прямых линий являются потенциальными местами остановок в населенных пунктах. Таким образом, следующая модель наглядно показывает маршрут следования и места остановок.

Если переложить этот пример на широкий круг задач, то можно представить сеть городских дорог в виде отрезков, а перекрестки дорог в виде пересечения этих отрезков.

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

Последние два примера абстрактных моделей можно представить в виде графов. Что такое граф?

Определения:

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

перекрестки дорог в городе,

генеалогическое древо и т.д.

 

 

Таким образом, граф состоит из вершин(узлов) и ребер (связи между вершинами).  Более формальное определение звучит так — графом называют пару (V, E) где V это множество вершин (иногда в литературе встречается обозначение узлы, в нашем случае это синонимы), а E множество пар, каждая из которых представляет собой связь, которые называются рёбрами. Если рассматривать пример с метрополитеном, то станции пересадок можно рассматривать как узлы, а сами линии метрополитена, как ребра. Или перекрестки дорог в городе можно принять за вершины, а дороги за ребра.

Стоит отметить, что отношения между множеством объектов может быть разное. В зависимости от этого выделяют два основых типа графов — ориентированные и неориентированные. В ориентированном графе связи между ребрами являются направленными (значит что пары являются упорядоченными или имеют начало и конец), а значит 1->2 не равно 2->1 и можно определить как две разные связи. В неориентированном графе не существует разницы между связями ребер, т.к. 1->2 можно рассматривать, как 2->1. В ориентированных графах ребра рисуются как вектора (в некоторых источниках ребра ориентированных графов называют дугами), в неориентированных в виде обычных прямых линий.

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

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

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

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

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

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

 

Между вершинами 1 и 2, а также между вершинами C и D проведены кратные рёбра. Кратные ребра это такие ребра у которых начало и концы совпадают. Небольшое дополнение: в ориентированных графах кратными называются ребра у которых начало и концы совпадают с четом направления.

Заметим, что между вершинами E и F кратных рёбер нет, поскольку ориентированные рёбра считаются кратными, только если у них совпадают начала и концы с учётом ориентации.

 

Рёбра, исходящие из вершин G и D, называются петлями. Про некоторые графы специально говорят «графы без петель и кратных рёбер», чтобы подчеркнуть, что в них не встречаются ситуации, аналогичные изображённым выше.

Важнейшим свойством графа является связность. Всякий неориентированный граф разбивается на свои компоненты связности. На рисунке выше имеются три компоненты связности: {A, B}, {G, E, C, D, F} и {H}. Граф, у которого только одна компонента связности, называется связным. Граф, у которого более одной компоненты связности, называется несвязным. На рисунке выше изображён несвязный граф. Таким образом, графы могут быть как бы разорванными структурами и на это есть свои логические объяснения. Например, если рассматривается три несвязанных между собой участка пути в одном городе или сложный вариант экономического бартера и т.д. На практике, особенно, в программировании встречаются, как правило связанные графы.

На практике часто встречаются графы, которые обладают какими-нибудь особенностями строения. Один из часто встречающихся видов графов — это деревья. Дерево — это связный неориентированный граф без петель и кратных рёбер, в котором нет циклов. Типичный пример дерева изображён на рисунке ниже. Итак, граф в котором выполняется ровно четыре условия условия: связный, неориентированный, отсутствие петель, нет кратных ребер, нет циклов. 

На самом деле свойств графов (изоморфизм, абстрактность, разреженность и т.д.) бывает очень и очень много, были перечислены самые распространенные и широко применяемые в алготитмах. Существует целый раздел математики «теория Графов» и множество теорем с математическими доказательствами, поэтому нужно понимать, что графы — это целая наука и лишь незначительная часть этой предметной области может задействоваться, в том числе и в алгоритмах.

Реализация и программная разработка:

Рассмотрим следующий граф и на его примере разберем способы представления данных. Существуют два основных способа представления, которые подходят для ориентированных и неориентированных графов. Обычно для представления графов используются двухмерные массивы. В данном примере будем использовать двухмерный массив  G.

Матрица смежности. Способ представления данных зависит от архитектуры построения графа. Все зависит от количества ребер и вершин. В среднем на одно ребро приходится две вершины, другими словами количество количество рёбер (|E|) примерно равно количеству вершин в квадрате (|V|2).  Графы с такой архитктурой называются плотными.

Данный способ подходит для ориентированных и неориентированных графов. Для неориентированных графов матрица A является симметричной (то есть G[i][j] == G[j][i], т.к. если существует ребро между i и j, то оно является и ребром из i в j, и ребром из j в i).

В данном случае матрица смежности будет заполняться по следующим правилам:

Для ориентированных графов. Если существует исходящее ребро ведущее из i в j, то значением двумерного массива является 1 ( G[i][j] = 1) иначе присваеивается значение = 0 (G[i][j] = 0)

Для неориентированных графов. Если существует ребро ведущее из i в j, то значением двумерного массива является 1 ( G[i][j] = 1) иначе присваеивается значение = 0 (G[i][j] = 0)

Особенности: Заметим, что матрица смежности неориентированного графа всегда симметрична относительно главной диагонали. Главная диагональ в матрице идёт из левого верхнего угла в правый нижний.

Достоинства: Можно быстро проверить есть ли ребро между вершинами i и j, G[i][j].

Недостатки: Требует большого расхода памяти — O (|V|2), где V — количество вершин.

Списки смежности.

Данный способ представления больше подходит для разреженных графов, то есть графов у которых количество рёбер гораздо меньше чем количество вершин в квадрате (|E| << |V|2). В списках смежности указываются только соседи каждой вершины. Таким образом, значение массива будет не «флаг» в виде 0 или 1, а само значение соседней вершина. Давайте рассмотрим примеры.

Для ориентированных графов. Если существуют соседи т.е. концы ребер направлены на соотвествующие вершины, то происходит последовательная инициализация значений соседних вершин  G[i][j] = V[i]

 

Для неориентированных графов. Если существуют соседи т.е. ребра направлены на соотвествующие вершины, то происходит последовательная инициализация значений соседних вершин  G[i][j] = V[i]


 

Достоинства: Память требуемая для представления равна сумме количества вершин и ребер т.е. O (|E| + |V|) что является лучше, чем расходование памяти в матрице смежности.

Недостатки: Нет быстрого способа найти конкретное ребро.

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

неориентированного графа

Подведем итоги:

Для хранения ориентированных графов применяются те же структуры данных, с разумными поправками:

  • в списке рёбер ребро хранится в виде [начало, конец];
  • в матрице смежности ребро из i в j означает G[i][j] = 1, и если обратного ребра в графе нет, то будет верным равенство G[j][i] = 0;
  • в списках смежности для каждой вершины хранится, в какие вершины из неё исходят рёбра.

Что почитать:

Поделиться

Отправить ответ

avatar
wpDiscuz