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