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


Представления - часть 2


Веса несуществующих ребер обычно полагают равными
\infty
или 0 в зависимости от приложений. Когда вес несуществующего ребра равен 0, матрица весов является простым обобщением матрицы смежностей.

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

g = (g_1,g_2,\ldots,g_{\left| E \right|}
и
h = (h_1,h_2,\ldots,h_{\left| E \right|} )
. Каждый элемент в массиве есть метка вершины, а
i
-е ребро графа выходит из вершины
g_i
и входит в вершину
h_i
. Например, орграф, изображенный на рис. 12.1, будет представляться следующим образом:
g = (1,2,2,2.2,3,3,4,5,5,5,7,7),
h = (6,1,3,4,6,4,5,5,3,6,7,1,6).
Ясно, что при этом легко представимы петли и кратные ребра.

Структура смежности. В ориентированном графе вершина

y
называется последователем другой вершины
x
, если существует ребро, направленное из
x
в
y
. Вершина
x
называется тогда предшественником
y
. В случае неориентированного графа две вершины называются соседями, если между ними есть ребро. Граф может быть описан его структурой смежности, то есть списком всех последователей (соседей) каждой вершины; для каждой вершины
v
задается
Adj(v)
- список всех последователей (соседей) вершины
v
. В большинстве алгоритмов на графах относительный порядок вершин, смежных с вершиной
v
в
Adj(v)
, не важен, и в таком случае удобно считать
Adj(v)
мультимножеством (или множеством, если граф является простым) вершин, смежных с
v
. Структура смежности орграфа, представленного на рис. 12.1, такова:

Adj(v) 1: 6 2: 1, 3, 4, 6 3: 4, 5 4: 5 5: 3, 6, 7 6: 7: 1, 6

Если для хранения метки вершины используется одно машинное слово, то структура смежности ориентированного графа требует

\left| V \right| + \left| E \right|
слов. Если граф неориентированный, нужно
\left| V \right| + 2\left| E \right|
слов, так как каждое ребро встречается дважды.

Структуры смежности могут быть удобно реализованы массивом из

\left| V \right|
линейно связанных списков, где каждый список содержит последователей некоторой вершины. Поле данных содержит метку одного из последователей, и поле указателей указывает следующего последователя. Хранение списков смежности в виде связанного списка желательно для алгоритмов, в которых в графе добавляются или удаляются вершины.




Начало  Назад  Вперед



Книжный магазин