Список смежности графа.

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

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

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

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

Далее, нам понадобятся три одномерных целочисленных массива:

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

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

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

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

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

#include "stdafx.h"
#include <iostream>
using namespace std;
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()
{
setlocale(LC_ALL,"Rus");
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;
}
system("pause>>void");
}

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

program listAdj;
uses crt;
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
clrscr;
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-ого столбца могут быть записаны несколько элементов (что соответствует нескольким смежным вершинам) назовем каждую строку в списке смежности его подсписком. Таким образом, в выведенном списке смежности, элементы подсписков будут отсортированы в обратном порядке. Но, как правило, порядок вывода смежных вершин (в подсписках) попросту неважен.