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

По отношению к памяти списки смежности менее требовательны, чем матрицы смежности, для их хранения нужно O (| V |+| E |)памяти. Такой список графически можно изобразить в виде таблицы, столбцов в которой – два, а строк не больше чем вершин в графе. В качестве примера возьмем смешанный граф:

Рисунок 3.8 – Смешанный граф

В нем 6 вершин (| V |) и 5 ребер (| E |). Из последних 2 ребра направленные и 3 ненаправленные, и, причем из каждой вершины выходит, как минимум одно ребро в другую вершину, из чего следует, что в списке смежности этого графа будет | V | строк.

Вершина выхода	Вершины входа
	2, 5
	1, 4

В i строке и 1 столбце указана вершина выхода, а в i строке и 2 столбце – вершины входа. Так, к примеру, из вершины 5 выходят два ребра, входящие в вершины 1 и 4.

Теперь перейдем непосредственно к программной реализации списка смежности. Количество вершин и ребер будут задаваться с клавиатуры, поэтому установим ограничения, иначе говоря, определим две константы, одна из которых отвечает за максимально возможное число вершин (Vmax), другая – ребер (Emax). Далее, нам понадобятся три одномерных целочисленных массива:

terminal [1.. Emax ] – хранит вершины, в которые входят ребра;

next [1.. Emax ] – содержит указатели на элементы массива terminal;

head [1.. Vmax ] – содержит указатели на начала подсписков, т. е. на такие вершины записанные в массив terminal, с которых начинается процесс перечисления всех вершин смежных одной i -ой вершине.

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

Код программы на C++:

const int Vmax=100, Emax=Vmax*2;

int head[Vmax];

int next_el[Emax];

int terminal[Emax];

int n, m, i, j, k, v, u;

char r;

void Add(int v, int u) //добавление ребра

{

k=k+1;

terminal[k]=u;

next_el[k]=head[v];

head[v]=k;

}

void main() //главная функция

{

k=0;

cout<<"Кол. вершин >> "; cin>>n;

cout<<"Кол. ребер >> "; cin>>m;

cout<<"Вводите смежные вершины:"<<endl;

for (i=0; i<m; i++)

{

cin>>v>>u;

cout<<"Ребро ориент.? (y/n) >> "; cin>>r;

if (r=='y') Add(v, u);

else

{

Add(v, u);

Add(u, v);

}

cout<<"..."<<endl;

}

cout<<"Список смежности графа:";

for (i=0; i<n+1; i++) //вывод списка смежности

{

j=head[i];

if (i) cout<<i<<"->";

while (j>0)

{

if (!next_el[j]) cout<<terminal[j];

else cout<<terminal[j]<<", ";

j=next_el[j];

}

cout<<endl;

}

}

Код программы на Pascal:

Const

Vmax=100;

Emax=Vmax*2;

Var

head: array [1..Vmax] of integer;

next: array [1..Emax] of integer;

terminal: array [1..Emax] of integer;

n, m, i, j, k, v, u: integer;

r: char;

procedure Add(v, u: integer); {добавление ребер}

begin

k:=k+1;

terminal[k]:=u;

next[k]:=head[v];

head[v]:=k;

end;

begin {основной блок программы}

k:=0;

write('Кол. вершин >> '); read(n);

write('Кол. ребер >> '); read(m);

writeln('Вводите смежные вершины:');

for i:=1 to m do

begin

read(v, u);

write('Ребро ориент.? (y/n) >> '); read(r);

if r='y' then add(v, u)

else begin

add(v, u);

add(u, v);

end;

writeln('...');

end;

writeln('Список смежности графа:');

for i:=1 to n do {вывод списка смежности}

begin

j:=head[i];

write(i, '->');

while j>0 do

begin

if next[j]=0 then write(terminal[j])

else write(terminal[j], ', ');

j:=next[j];

end;

writeln;

end;

end.

Работа двух приведенных программ идентична, а отличаются они друг от друга, лишь символикой, используемой в языке программирования, поэтому дальнейшие рассуждения будут касаться их обеих. Итак, первое действие, на которое стоит обратить внимание это запрос на ввод суммы вершин n и ребер m графа (пользователь должен заранее знать эти данные). Далее, запускается цикл ввода ребер (смежных вершин). Условие в этом цикле нужно для того, чтобы узнать, какое введено ребро. Если введено направленное ребро, то функция add вызывается 1 раз, иначе – 2, тем самым внося сведения, что есть ребро как из вершины v в вершину u, так и из u в v. После того как список смежности сформирован, программа выводит его на экран. Для этого использован цикл от 1 до n, где n – количество вершин, а также вложенный в него цикл, который прекращает свою работу тогда, когда указатель на следующий элемент для i -ой вершины отсутствует, т. е. все смежные ей вершины уже выведены.

Функция add производит добавление ребер в изначально пустой список смежности:

Add(v, u)

k:=k+1

terminal[k]:=u

next[k]:=head[v]

head[v]:=k

Чтобы сделать это, производятся операции с формальными параметрами, вспомогательной переменной k и тремя одномерными целочисленными массивами. Значение переменной k увеличивается на 1. Затем в k -ый элемент массива terminal записывается конечная для некоторого ребра вершина u. В третий строке k -ому элементу массива next присваивается адрес следующего элемента массива terminal. Ну и в конце массив head заполняется указателями на стартовые элементы, те с которых начинается подсписок смежных вершин с некоторой i -ой вершиной.

Так как в ячейке на пересечении i -ой строки и 2-ого столбца могут быть записаны несколько элементов (что соответствует нескольким смежным вершинам) назовем каждую строку в списке смежности его подсписком. Таким образом, в выведенном списке смежности, элементы подсписков будут отсортированы в обратном порядке. Но, как правило, порядок вывода смежных вершин (в подсписках) попросту неважен.