Списки смежности

Списки инцидентности.

Массив ребер.

Массив ребер – это массив, в котором ребра хранятся парами вершин, которые они соединяют.

Это наиболее понятный, но достаточно неудобный способ хранения графа. Однако у него есть один большой плюс - при таком способе представления легко вводить дополнительные характеристики ребер. Например, чтобы сохранить веса ребер, достаточно сделать массив размером Mx3 и в дополнительную ячейку для каждого ребра записать его вес.

Например, для графа, приведенного на рис.6 массив ребер будет следующий: (1,2), (1,3), (2,1), (2,4), (2,5), (3,1), (3,2), (3,5), (4,1), (4,2), (4,3), (4,5), (5,2), (5,4).

Если априорно известно, что граф не ориентированный, то включая описание (v, w) не включается описание (w, v).

Для каждой вершины графа создаются три списка:

ü v ⁰: только неориентированные ребра, инцидентные вершине;

ü v ⁺: исходящие ребра;

ü v ^-: входящие ребра.

Ели граф ориентирован, то для каждой вершины v достаточно списков v ⁺ и v ^-. Если граф неориентированный, то достаточно списков v ⁰.

Например,

1^0:	(1,2),(1,3)
1^+:
1^-:
2^0:	(2,1), (2,4), (2,5)
2^+:
2^-:	(3,2)
3^0:	(3,1)
3^+:	(3,2), (3,5)
3^-:	(4,3)
4^0:	(4,2), (4,5)
4^+:	(4,1), (4,3)
4^-:
5^0:	(5,4), (5,2)
5^+:
5^-:	(3,5)

Представляет собой структуру данных, которая для каждой вершины графа хранит список смежных с ней вершин. Список представляет собой массив указателей, i-ый элемент которого содержит указатель на список вершин, смежных с i-ой вершиной.

Список смежности более эффективен по сравнению с матрицей смежности, так как исключает хранение нулевых элементов.

Например (рис.6):

1:	2,3
2:	1,4,5
3:	1,2,5
4:	1,2,3,5
5:	1,4

Матрицей инцидентности (инциденций) неориентированного графа называется матрица , для которой , если вершина инцидентна ребру , в противном случае .

Матрицей инцидентности (инциденций) ориентированного графа называется матрица , для которой , если вершина является началом дуги , , если является концом дуги , в остальных случаях .

Дата добавления: 2014-01-20