Элементы теории графов

Способы представления графов

Рассмотрим способы представления графов в памяти ЭВМ. Граф является топологической абстракцией, предназначенной для описания некоторых топологических свойств самых разных объектов и отношений между этими объектами. Существует большое число типов графов, отличающихся классификационными признаками. Такое многообразие обусловлено различными свойствами графов. Так, графы могут быть связными, слабосвязными, сильносвязными, полносвязными, несвязными, ориентированными, неориентированными, взвешенными, контурными, бесконтурными, содержащими петли или кратные рёбра (псевдографами), мультиграфами, гиперграфами и т.п. [2, 9].

Для графов имеется большое число алгоритмов обработки данных, например, поиск вершин в графе, поиск кратчайших путей, построение деревьев на графах, очерёдность обхода вершин и т.п.

Для работы с графом он должен быть каким-либо образом представлен в памяти ЭВМ. Способ представления зависит от характера решаемых на графе задач. Существует несколько способов отображения графа на память машины, каждый из которых обладает собственными достоинствами и недостатками [9]. Существуют также и алгоритмы преобразования этих способов описания графа друг в друга [10].

Список рёбер

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

(1,2), (1,3), (1,4), (2, 4), (3,4).

Простой ненаправленный циклический граф

Рис. 11.1 - Простой ненаправленный циклический граф

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

(1,2), (1,3), (1,4), (4. 2), (4, 3)

Рис. 11.2 - Простой направленный циклический граф и его список рёбер

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

  • 11.3, описывается следующим списком рёбер:
    • (1,2, 0.20), (1,3, 0.30), (1,4, 0.10), (4, 2, 0.33), (4, 3, 0.15).
Взвешенный направленный циклический граф

Рис. 11.3 - Взвешенный направленный циклический граф

Список рёбер для графа из М ребер требует в расчёте на вершину объём памяти, пропорциональный 2М. Для получения списка рёбер, непосредственно связанных с текущей вершиной требуется М шагов.

Под термином «список» во всех рассмотренных случаях следует понимать как массив однотипных элементов (в более простом случае), так и связный список в том числе, и даже древовидную структуру данных. Наряду с простотой, рассматриваемый способ описания графа обладает, по крайней мере, двумя особенностями, которые при определённых обстоятельствах можно посчитать недостатками. Эти особенности следующие:

  • - порядок перечисления рёбер в списке в общем случае может быть произвольным. Это следует из самой природы графа, когда точно расположение вершин не важно, важны лишь их взаимное расположение и связи между ними. В то же время возможны ситуации, когда отсутствует какой-либо логический порядок в перечислении рёбер, что может привести к ухудшению понимания структуры графа, а также к усложнению алгоритмов его обработки;
  • - в том случае, когда для хранения рёбер используется массив, список рёбер оказывается пригодным только для описания графа с неизменяющейся структурой или с одним и тем же числом рёбер. Для описания и обработки динамически изменяющегося графа потребуется применить связный список. В этом случае по мере добавления или удаления вершин и рёбер структура графа изменится, также как и порядок следования рёбер. Это также приведёт к усложнению алгоритмов обработки графа.
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >