Составители:
53
var
Graph: TIncidenceMatrix;
При этом
{
0, если вершина не инцидентна ребру ,
Graf[ , ]
вес ребра (дуги в ), если вершина инцидентна ребру .
ij
ij
ij
=
Пространственная сложность этого способа V(n, m)~O(n×m). Матри-
ца инцидентности лучше всего подходит для операции «перечисление
ребер, инцидентных вершине x».
Списки смежных вершин – это одномерный массив размером n, со-
держащий для каждой вершины указатели на списки смежных с ней
вершин:
type
PNode = ^Node;
Node = record {смежная вершина}
Name: string; {имя смежной вершины}
Weight: integer; {вес ребра}
Next: PNode; {следующая смежная вершина}
end;
TAdjacencyList = array [1..n] of record
NodeWeight: integer; {вес вершины}
Name: string; {имя вершины}
List: PNode; {указатель на список смежных}
end;
var
Graph: TAdjacencyList;
Пространственная сложность этого способа V
max
(n)~O(n
2
). Хране-
ние списков в динамической памяти позволяет сократить объем расхо-
дуемой памяти, так как в этом случае не будет резервироваться место
под n соседей для каждой вершины. Можно и сам массив представить в
виде динамического списка, но это не имеет особого смысла, так как
граф обычно является статичной (неизменяемой) структурой.
Этот способ хранения лучше всех других подходит для операции «пе-
речисление всех вершин, смежных с x».
Список ребер – это одномерный массив размером m, содержащий
список пар вершин, инцидентных с одним ребром графа:
type
TBranchList = array [1..m] of record
Страницы
- « первая
- ‹ предыдущая
- …
- 51
- 52
- 53
- 54
- 55
- …
- следующая ›
- последняя »
