Алгоритмы на графах: Дейкстры, Прима, Краскала

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

Существуют различные виды представления графа:

1. списки смежности,
2. списки рёбер,
3. матрица смежности,
4. матрица инцидентности.

Списки смежности и списки рёбер

Являются компактными и удобными в том случае, когда граф является разреженным. В случае со списком смежности хранение представляет собой массив вершин графа, для каждой из которых определены все вершины в которые можно попасть из неё.

[a] -> a:2 -> b:5 -> d:8
[b] -> c:7 -> d:9
[c] -> d:4
[d] -> c:3

[a,a,2]
[a,b,5]
[a,d,8]
[b,c,7]
[b,d,9]
[c,d,4]
[d,c,3]

Матрица смежности и матрица инцидентности

Является более удобным представлением в том случае, когда нужно быстро отвечать на вопрос «является ли данное ребро инцидентно к…» или аналогичные. Но, если графы не плотные (а разреженные), то занимается существенное количество памяти. Матрица смежности состоит из таблицы размером , где на пересечении для каждой пары вершин находится или признак того, что ребро между ними существует (для неориентированных графов), либо вес ребра. Матрица инцидентности имеет размер , а её пересечении говорит о том, что данное ребро инцидентно вершине (то есть один из её концов содержит вершину). В случае ориентированного графа в матрице смежности используются положительные числа для того, чтобы обозначить, что ребро выходит из этой вершины:

   a  b  c  d
a  2  5  0  8
b  0  0  7  9
c  0  0  0  4
d  0  0  3  0

       a  b  c  d
(a,a)  2  0  0  0
(a,b)  0  5  0  0
(a,d)  0  0  0  8
(b,c)  0  0  7  0
(b,d)  0  0  0  9
(c,d)  0  0  0  4
(d,c)  0  0  3  0