Список ребер

Список, в каждой строке которого записаны две смежные вершины и вес, соединяющего их ребра, называется списком ребер графа. Возьмем связный граф 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.

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

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

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

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

using namespace std ;

const int Vmax = 100 ,

Emax = Vmax * ( Vmax - 1 ) / 2 ; //в случае, если граф полный

int terminal [ Emax ] , weight [ Emax ] , point [ Emax ] ;

int n, m, v, u, w, k = 0 , i ;

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

//если вершина v новая, то

//первая смежная ей вершина имеет номер k

//если вершина v уже просматривалась, то

//следующая смежная с ней вершина имеет номер k

cout << "Вводите ребра и их вес (v, u, w): \n " ;

//вывод списка ребер

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

Emax = Vmax * ( Vmax - 1 ) div 2 ;

terminal , weight , point : array [ 1 .. Emax ] of integer ;

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

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

procedure Add ( v , u , w : integer ) ;

первая смежная ей вершина имеет номер k>

if head [ v ] = 0 then head [ v ] := k;

следующая смежная с ней вершина имеет номер k>

writeln ( 'Вводите ребра и их вес (v, u, w) > ' ) ;

for i := 1 to m do

if yn = 'n' then begin

for i := 1 to m do

Максимально возможное количество вершин в графе задано константой 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 станет равной нулю), а внешний – по окончанию вывода списка ребер.

Смотрите также:

Добавить комментарий Отменить ответ

Популярное

Авторские права

© 2012 — 2015 Kvodo.ru

Выражаем благодарность Алексееву Е. Р. за предоставленное им право использовать материалы книги «MS Visual C++ и Turbo C++ Explorer»



Формула Остроградского-Гаусса
Неопределенный интеграл