Список ребер графа.

Список, в каждой строке которого записаны две смежные вершины и вес, соединяющего их ребра, называется списком ребер графа. Возьмем связный граф G=(V, E), и множество ребер E разделим на два класса d и k, где d – подмножество, включающее только неориентированные ребра графа G, а k – ориентированные.

Предположим, что некоторая величина p соответствует количеству всех ребер, входящих в подмножество d, а s – тоже относительно k. Тогда для графа G высота списка ребер будет равна s+p*2. Иными словами, количество строк в списке ребер всегда должно быть равно величине, получающейся в результате сложения ориентированных ребер с неориентированными, увеличенными вдвое.

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

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

В нем 3 направленных ребра и 1 ненаправленное. Подставив значения в формулу, получим высоту списка ребер: 3+1*2=5.

Так выглядит список ребер для приведенного графа. Это таблица размером n×3, где n= s+p*2=3+1*2=5. Элементы первого столбца располагаются в порядке возрастания, в то время как порядок элементов второго столбца зависит от первого, а третьего от двух предыдущих.

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

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

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

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

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

program ListEdges;
uses crt;
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
clrscr;
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 станет равной нулю), а внешний – по окончанию вывода списка ребер.