Составители:
52
ние вершин ребрами означает взаимодействие подпрограмм. Часто имеет
значение направление дуги в графе.
1.3.3.2. Реализация
Выбор структуры данных для хранения графа в памяти имеет принци-
пиальное значение при разработке эффективных алгоритмов. Рассмотрим
два матричных и три списочных представления графа (см. рис. 13):
– матрица смежности;
– матрица инцидентности;
– списки смежных вершин;
– список ребер;
– списки вершин и ребер.
При дальнейшем изложении будем предполагать, что вершины гра-
фа обозначены символьной строкой и всего их до n, а ребер – до m.
Каждое ребро и каждая вершина имеют вес – целое положительное чис-
ло. Если граф не является помеченным, то считается, что вес равен
единице.
Матрица смежности – это двумерный массив размером n×n:
type
TAdjacencyMatrix = array [1..n, 1..n] of integer;
var
Graph: TAdjacencyMatrix;
При этом
0, если вершина не смежна вершине ,
Graf[ , ] вес ребра (дуги), если вершина смежна вершине ,
вес вершины, если .
ij
ij i j
ij
⎧
⎪
=
⎨
⎪
=
⎩
Вес вершины указывается в элементах матрицы смежности, находя-
щихся на главной диагонали, только в том случае, если в графе отсут-
ствуют петли. В противном случае, в этих элементах указывается вес
петли.
Пространственная сложность этого способа V(n)~O(n
2
). Способ очень
хорош, когда надо часто проверять смежность или находить вес ребра
по двум заданным вершинам.
Матрица инцидентности – это двумерный массив размером n×m:
type
TIncidenceMatrix = array [1..n, 1..m] of integer;
Страницы
- « первая
- ‹ предыдущая
- …
- 50
- 51
- 52
- 53
- 54
- …
- следующая ›
- последняя »
