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

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

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

 

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

файл ListGraph.h

#include "graph.h"                          // Описание родительского класса

 

// Описание шаблона классов для представления

// простых однонаправленных списков

template <class T>

class List {

 

// Внутренний класс для представления элементов списка

struct Listltem {

Т item;                                            // Собственно элемент списка

Listltem *next;                              // Ссылка на следующий элемент списка

 

// Конструктор элементов введен для удобства реализации операций

Listltem(const T fiitem, Listltem *next = NULL)

{

Listltem::item = item;

Listltem::next = next; }

};

 

// Список представлен ссылками на первый и последний элементы...

Listltem *first, *last;

//...а также счетчиком числа элементов

int count;

public:

// Конструктор пустого списка - единственный в нашем описании

List() { first = last = NULL; count = 0;)

 

// Операции добавления элемента...

void add(const T &);

//...и проверки наличия элемента в списке

bool has(const T &) const;

};

 

// Собственно описание класса для представления L-графа

class ListGraph: public Graph {

// Массив списков целых, каждое из которых задает

// номер вершины, в которую входит дуга. Индексы в массиве

// задают номера вершин, из которых эти дуги исходят.

List<int> *graph;

// Количество вершин в графе.

int vertexNumber;

public:

// Конструктор порождает N списков и инициализрует массив этих

// списков, запоминая количество вершин, заданное аргументом

 ListGraph(int n) { graph = new List<int>[vertexNumber = n]; }

 

// Операция подсчета вершин просто выдает запомненное ранее значение

int vertexCount() const { return vertexNumber; 1

 

// Две следующие функции реализуют операции над дугами

void addArc(int from, int to);

bool hasArc(int from, int to) const;

};

 

файл ListGraph.cpp     

#include "ListGraph.h"

 

// Реализация операций над списком.

// Добавление нового элемента в список

template <class T>

void List<T>::add(const T & item) {

ListItem *newItem - new ListItem(item);

// Новый элемент включается в конец списка

if (last) last->next = newItem; else first = newItem;

last = newItem;

count++; }

 

// Проверка наличия элемента в списке

template <class T>

bool List<T>::has(const T & item) const {

 

// Список просматривается с начала в поисках нужного элемента

 for (ListItem *current = first; current; current = current->next) {

 if (current->item == item) return true;

}

// Элемент не найден

return false;

}

// Реализация операций над графом.

// Операция добавления дуги.

void ListGraph::addArc(int from, int to) {

if (from < 0 || from >= vertexNumber || to < 0 ||to >= vertexNumber)

return;                                             // невозможно добавить дугу

// Добавление новой дуги в конец списка

graph[from].add(to); }

 

// Операция проверки наличия дуги.

bool ListGraph::hasArc(int from, int to) const {

if (from < 0 || from >= vertexNumber || to < 0 || to >= vertexNumber)

return false; // неправильно заданы номера вершин 

 

//В списке с номером from ищем элемент to.

return graph[from].has(to);

}

 

Удаление дуги при таком представлении не удается реализовать столь же просто, как это было сделано для S-графа и M-графа. Для этого придется просмотреть соответствующий список, найти в нем нужную дугу и удалить ее из списка.

Представление графа в виде совокупности списков дуг становится неудобным в тех случаях, когда наиболее часто используются операции проверки наличия или модификации конкретной дуги, т. е. как раз те операции, которые наиболее эффективно реализуются для S-графов и M-графов. Зато эффективно реализуется перебор всех дуг, исходящих из заданной вершины, операция, которая сравнительно долго выполняется для S-графов и М-графов. Правда, для того чтобы найти дуги, входящие в заданную вершину, приходится вообще просмотреть все списки, т. е. пройти полностью всю структуру графа.