Список, в каждой строке которого записаны две смежные вершины и вес, соединяющего их ребра, называется списком ребер графа. Возьмем связный граф G =(V, E), и множество ребер E разделим на два класса d и k, где d – подмножество, включающее только неориентированные ребра графа G, а k – ориентированные. Предположим, что некоторая величина p соответствует количеству всех ребер, входящих в подмножество d, а s – тоже относительно k. Тогда для графа G высота списка ребер будет равна s + p *2. Иными словами, количество строк в списке ребер всегда должно быть равно величине, получающейся в результате сложения ориентированных ребер с неориентированными, увеличенными вдвое. Это утверждение следует из сказанного ранее, а именно, что данный способ представления графа предусматривает хранение в каждой строке двух смежных вершин, а неориентированное ребро, соединяющее вершины v и u, идет как из v в u, так и из u в v.
Рассмотрим смешанный граф (рис. 3.9), в котором 5 вершин, 4 ребра и каждому ребру поставлено в соответствие некоторое целое значение (для наглядности оно составлено из номеров вершин).
|
|
Рисунок 3.9 – Смешанный граф
В нем 3 направленных ребра и 1 ненаправленное. Подставив значения в формулу, получим высоту списка ребер: 3+1*2=5.
Так выглядит список ребер для приведенного графа. Это таблица размером n ´3, где n = s + p *2=3+1*2=5. Элементы первого столбца располагаются в порядке возрастания, в то время как порядок элементов второго столбца зависит от первого, а третьего от двух предыдущих.
Программная реализация списка ребер похожа на реализацию списка смежности. Так же как и в последней, в ней изначально необходимо организовать ввод данных, которые при помощи специальной функции будут распределяться по массивам. Второй шаг – вывести получившийся список смежности на экран.
В списке смежности хранились только смежные вершины, а здесь, помимо них, будут храниться веса инцидентных этим вершинам ребер, и для этой цели понадобиться дополнительный массив. К тому же, данный метод требует более строго порядка вывода вершин, т. к. если в списке смежности последовательность нарушалась лишь в строках, то использование аналогичного способа построения приведет к нарушению порядка в столбцах. Поэтому функцию добавления ребер следует организовать иначе.
Код программы на C++:
const int Vmax=100,
Emax=Vmax*(Vmax-1)/2; //в случае, если граф полный
int terminal[Emax], weight[Emax], point[Emax];
int head[Vmax], last[Vmax];
int n, m, v, u, w, k=0, i;
char r;
void Add(int v, int u, int w) //добавление ребра
{
k=k+1;
terminal[k]=u; weight[k]=w;
//если вершина v новая, то
//первая смежная ей вершина имеет номер k
|
|
if (head[v]==0) head[v]=k;
//если вершина v уже просматривалась, то
//следующая смежная с ней вершина имеет номер k
if (last[v]!=0) point[last[v]]=k;
last[v]=k;
}
void main() //главная функция
{
cout<<"Кол. вершин >> "; cin>>n;
cout<<"Кол. ребер >> "; cin>>m;
cout<<"Вводите ребра и их вес (v, u, w):\n";
for (i=0; i<m; i++)
{
cin>>v>>u>>w;
cout<<"Ребро ориент.? (y/n) >> "; cin>>r;
if (r=='y') Add(v, u, w);
else
{
Add(v, u, w);
Add(u, v, w);
}
cout<<"..."<<endl;
}
m=m*2;
cout<<"Список ребер графа:\n";
for (i=0; i<m; i++) //вывод списка ребер
{
k=head[i];
while (k>0)
{
cout<<"("<<i<<"->"<<terminal[k]<<")$="<<weight[k]<<endl;
k=point[k];
}
}
}
Код программы на Pascal:
const
Vmax=100;
Emax=Vmax*(Vmax-1) div 2; {в случае, если граф полный}
Var
terminal, weight, point: array [1..Emax] of integer;
head, last: array [1..Vmax] of integer;
n, m, v, u, w, k, i: integer;
yn: char;
procedure Add(v, u, w: integer);
begin
k:=k+1;
terminal[k]:=u; weight[k]:=w;
{если вершина v новая, то
первая смежная ей вершина имеет номер k}
if head[v]=0 then head[v]:=k;
{если вершина v уже просматривалась, то
следующая смежная с ней вершина имеет номер k}
if last[v]<>0 then point[last[v]]:=k;
last[v]:=k;
end;
begin {основной блок программы}
write('Количество вершин > '); read(n);
write('Количество ребер > '); read(m);
writeln('Вводите ребра и их вес (v, u, w) > ');
for i:=1 to m do {ввод ребер}
begin
read(v, u, w);
write('Ребро ориентир.? (y/n) > '); read(yn);
if yn='n' then begin
Add(v, u, w);
Add(u, v, w);
end
else begin
Add(v, u, w);
end;
end;
m:=m*2;
writeln('Список ребер:');
for i:=1 to m do {вывод списка ребер}
begin
k:=head[i];
while (k>0) do begin
writeln('(', i, '->', terminal[k], ')$=', weight[k]);
k:=point[k];
end;
end;
end.
Максимально возможное количество вершин в графе задано константой Vmax, а ребер – Emax. Последняя константа инициализируется выражением Vmax *(Vmax -1)/2, вычисляющим количество ребер в полном графе при известном числе вершин. Далее, в программах описываются 5 массивов:
· terminal – массив вершин, в которые входят ребра;
· weight – массив весов ребер;
· head [ i ]= k – хранит для i -ой вершины номер k -ого элемента массивов terminal и weight, где terminal [ k ] – первая вершина смежная с i -ой, а weight [ k ] – вес инцидентного ей ребра;
· last [ i ]= k – хранит для i -ой вершины номер k -ого элемента массивов terminal и weight, где terminal [ k ] – последняя вершина смежная с i -ой, а weight [ k ] – вес инцидентного ей ребра;
· point [ i ]= k – хранит для i -ой вершины номер k -ого элемента массивов terminal и weight, где terminal [ k ] – следующая вершина смежная с i -ой, а weight [ k ] – вес инцидентного ей ребра.
После ввода количества вершин (n) и ребер (m) графа, запускается цикл, на каждом шаге которого пользователь вводит с клавиатуры две смежные вершины и вес, лежащего между ними ребра. Если ребро является ориентированным, то функция добавления данных в список ребер (Add) вызывается один раз, если неориентированным – два раза. Общее число вызовов функции вычисляется все по тому же выражению s +(p *2), где s – ориентированные ребра графа, p – неориентированные. Закончив формирование списка ребер, необходимо вдвое увеличить переменную m, т. к. в случае чисто неориентированного графа высота списка будет равна 0+(m *2).
Осталось вывести на экран получившуюся конструкцию. Вспомним, что на номер первой вершины смежной с i -ой вершиной указывает элемент head [ i ], следовательно, каждая новая итерация внешнего цикла должна начинаться с взятия этого номера (k = head [ i ]). Внутренний цикл перестанет выполняться тогда, когда не найдется ни одной смежной с i -ой вершины (k станет равной нулю), а внешний – по окончанию вывода списка ребер.