Представления
Наиболее известный способ представления графа на бумаге состоит в геометрическом изображении точек и линий. В ЭВМ граф должен быть представлен дискретным способом, причем возможно много различных представлений. Простота использования, так же как и эффективность алгоритмов на графе, зависит от подходящего выбора представления графа. Рассмотрим различные структуры данных для представления графов.
Матрица смежностей. Одним из наиболее распространенных машинных представлений простого графа является матрица смежностей или соединений. Матрица смежностей графа
есть
-матрица
, в которой
, если в
существует ребро, идущее из
-й вершины в
-ю, и
в противном случае. Орграф и его матрица смежностей представлены на рис. 12.1.
Рис. 12.1. Ориентированный граф и его матрица смежностей
Заметим, что в матрице смежностей петля может быть представлена соответствующим единичным диагональным элементом. Кратные ребра можно представить, позволив элементу матрицы быть больше 1, но это не принято, так как обычно удобно представлять каждый элемент матрицы одним двоичным разрядом.
Для задания матрицы смежностей требуется
двоичных разрядов. У неориентированного графа матрица смежностей симметрична, и для ее представления достаточно хранить только верхний треугольник. В результате экономится почти 50% памяти, но время вычислений может при этом немного увеличиться, потому что каждое обращение к
должно быть заменено следующим: if
then
else
. В случае представления графа его матрицей смежностей для большинства алгоритмов требуется время вычисления, по крайней мере пропорциональное
.
Матрица весов. Граф, в котором ребру
сопоставлено число
, называется взвешенным графом, а число
называется весом ребра
. В сетях связи или транспортных сетях эти веса представляют некоторые физические величины, такие как стоимость, расстояние, эффективность, емкость или надежность соответствующего ребра. Простой взвешенный граф может быть представлен своей матрицей весов
, где
есть вес ребра, соединяющего вершины
и
.
Веса несуществующих ребер обычно полагают равными
или 0 в зависимости от приложений. Когда вес несуществующего ребра равен 0, матрица весов является простым обобщением матрицы смежностей.
Список ребер. Если граф является разреженным, то возможно, что более эффектно представлять ребра графа парами вершин. Это представление можно реализовать двумя массивами
и
. Каждый элемент в массиве есть метка вершины, а
-е ребро графа выходит из вершины
и входит в вершину
. Например, орграф, изображенный на рис. 12.1, будет представляться следующим образом:
Ясно, что при этом легко представимы петли и кратные ребра.
Структура смежности. В ориентированном графе вершина
называется последователем другой вершины
, если существует ребро, направленное из
в
. Вершина
называется тогда предшественником
. В случае неориентированного графа две вершины называются соседями, если между ними есть ребро. Граф может быть описан его структурой смежности, то есть списком всех последователей (соседей) каждой вершины; для каждой вершины
задается
- список всех последователей (соседей) вершины
. В большинстве алгоритмов на графах относительный порядок вершин, смежных с вершиной
в
, не важен, и в таком случае удобно считать
мультимножеством (или множеством, если граф является простым) вершин, смежных с
. Структура смежности орграфа, представленного на рис. 12.1, такова:
Adj(v) 1: 6 2: 1, 3, 4, 6 3: 4, 5 4: 5 5: 3, 6, 7 6: 7: 1, 6
Если для хранения метки вершины используется одно машинное слово, то структура смежности ориентированного графа требует
слов. Если граф неориентированный, нужно
слов, так как каждое ребро встречается дважды.
Структуры смежности могут быть удобно реализованы массивом из
линейно связанных списков, где каждый список содержит последователей некоторой вершины. Поле данных содержит метку одного из последователей, и поле указателей указывает следующего последователя. Хранение списков смежности в виде связанного списка желательно для алгоритмов, в которых в графе добавляются или удаляются вершины.
Матрица инцидентности -
задает граф :
если ребро
выходит из вершины
,
, если ребро
входит в вершину
, и
в остальных случаях.
Содержание раздела
