Структуры и алгоритмы обработки данных. Ключарев А.А - 54 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

54
Node1: string; {1-я вершина, инцидентная ребру}
Node2: string; {2-я вершина, инцидентная ребру}
Weight: integer; {вес ребра}
end;
var
Graph: TBranchList;
Пространственная сложность этого способа V(m)~O(m). Этот способ
хранения графа особенно удобен, если главная операция, которой чаще
всего выполняется, это перечисление ребер или нахождение вершин и
ребер, находящихся в отношениях инцидентности.
abcd
a 2508
b 0079
c 0004
d 0030
a
b
d
c
Матрица
смежности
abcd
2000
0500
0008
0070
0009
0004
0030
Матрица
инцидентности
5
7
8
9
34
Граф
Списки вершин и ребер
Список ребер
aa2
ab5
ad8
bc7
bd9
cd4
dc3
2
1
1
1
1
a
b
c
d
a 2 b 5 d 8 nil
c 7 d 9 nil
d 4 nil
c 3 nil
Списки смежных вершин
2 5 8 nil 7 9 nil 4 nil 3 nil
1a 1b 1c nil1d
(a, a)
(a, b)
(a, d)
(b, c)
(b, d)
(c, d)
(d, c)
Рис. 13. Граф и его реализации
Граф можно представить также в виде списочной структуры, состоя-
щей из списков двух типов – списки вершин и списков ребер:

Страницы