Представление графа в виде связанного списка

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

Рис.2. Граф и его представление в виде связанных списков.

 

Соответствующее представление будем называть L-графом (от list— список). В листинге приведено возможное описание класса и реализация операций для ненагруженного L-графа. Кроме описания класса для L-графа в листинге показано определение простого однонаправленного списка объектов с операциями добавления элемента в список и проверки наличия элемента в списке.