Методические указания к выполнению работы. Vector <list <int>> graf. Vector <list <int>> graf.

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

То есть исходный граф, определяемый некоторой переменной, например graf, может описываться как

vector < list < int> > graf.

Если граф взвешенный, то компонентами его списков являются записи, содержащие помимо номера смежной вершины веса ребра (дуги), инцидентного этой вершине.

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

Файл «таблица смежности» состоит из блоков, соответствующих вершинам графа. Каждый блок имеет следующую структуру:

начальная вершина: список смежных с ней вершин

соответствующие ребрам (дугам) веса

Количество строк с весами ребер равно числу весов. Блоки в таком файле могут располагаться в произвольном порядке, причем, если вершина не является начальной ни для одного ребра (дуги) или ребро уже включено в список инцидентности другого его конца, то соответствующий ей блок может отсутствовать в файле.

Например, для неориентированного графа

 

Рис. 2

файл «таблица смежности» имеет вид

v₁: v₃ v₄

5 10

v₃: v₄

v₄: v₅

а ориентированный граф

 

 

Рис.4

задается «таблицей смежности»

1: 2 3

2: 3

3: 1

Для ориентированных графов могут формироваться как списки вершин, следующих за текущей, так и предшествующих ей вершин.

Файл «таблица ребер» имеет следующую структуру:

начальная вершина конечная вершина вес(а) ребра (дуги)

Также как и для «таблицы смежности» количество элементов в каждой из строк должно быть одинаковым, а число весов равно kv.

Например, файл «таблица ребер» графа, изображенного на рис.2 имеет вид.

v₁ v₃ 5

v₁ v₄ 10

v₃ v₄ 7

v₄ v₅ 4

Для формирования машинного представления графа необходимо сформировать список инцидентности для каждой вершины графа. Формирование списка инцидентности может осуществляться по принципу стека (LIFO), когда новая запись включается в начало списка, или по принципу очереди (FIFO), когда новая запись ставится в конец списка.

Определение количества вершин и рёбер (дуг) исходного графа выполняется программно при формировании списков инцидентности графа. Количество вершин определяется как максимальный номер вершины. Число рёбер (дуг) подсчитывается как суммарное число вершин для всех списков в исходном файле – для «таблицы смежности» и число строк – для «таблицы рёбер». Эти значения и построенные списки инцидентности выводятся на экран (или выходной файл).

Приведём алгоритмы построения списков инцидентности графа по входным файлам обоих видов. Используемые в алгоритмах обозначения:

nv – начальная вершина ребра (дуги);

kv – конечная вершина ребра (дуги).

1. Файл «таблица смежности».