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

Этот способ задания графов подразумевает, что для каждой вершины будет указан список всех смежных с нею вершин (для ориентированного графа – список вершин, являющихся концами исходящих дуг):

<номер начальной вершины>: <номера смежных вершин>

Пример: (рис. графов см. выше)

1) a: b c

b: c d f

c: d f

d: f

2) a: b 1 c 10

b: a 1 c 2 d 10

c: a 10 d 3

d: b 10 c 3

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

Type refnode=^node;

refarc=^arc;

node= record {список вершин}

id:integer; {номер вершины}

infnode:integer; {вес}

next:refnode; {указатель на следующую вершину в списке}

arclist:refarc {указатель на список дуг}

end;

arc= record {список дуг определенной вершины}

infarc:integer; {вес}

next:refarc; {указатель на следующую дугу, исходящую из данной вершины}

adj [1]:refnode {указатель на вершину, в которую ведет данная дуга}

end;

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

Например, для графа следующего вида

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

Type refnode=^node;

refarc=^arc;

node= record {список вершин}

id:integer; {номер вершины}

infnode:integer; {вес}

next:refnode; {указатель на следующую вершину в списке}

arclist:refarc {указатель на список дуг}

end;

arc= record {список дуг определенной вершины}

infarc:integer; {вес}

next:refarc; {указатель на следующую дугу, исходящую из данной вершины}

adj:refnode {указатель на вершину, в которую ведет данная дуга}

end;

получим следующее представление:

Задание. Нарисовать списковое представление графа (см. задание 2 раздела «Матрица инцидентности».

Рассмотрим основные процедуры работы с графами.

Дата добавления: 2015-10-13