Представление графа в программе (часть 2)

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

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

Способ 2: Список ребер

Обычно матрицу представляют как несколько вершин, и ребра между этими вершинами. Но можно представить себе граф и как список ребер между двумя вершинами. Тогда наш граф будет представлять из себя список объектов типа Edge<T>, где T- тип вершины.  Этот класс является вложенным по отношению к EdgesListGraph.

В случае взвешенного графа каждому ребру нужно также добавить вес weight:

Класс EdgesListGraph будет содержать список таких объектов Edge<T>. Типом T в нашем случае будет простой Integer. В конструкторе EdgesListGraph может принимать изначальный список вершин, или в пустом конструкторе создавать новый список.

Метод dump просто выводит содержимое списка edges. print выводит этот же список, предварительно сортируя по значению from. Как следствие все ребра из одной вершины будут идти по порядку, что более наглядно.

Поиск вершин, в которые можно попасть из заданной выполняется довольно долго - нам нужно пройтись по всему списку и сравнить значения from у каждого объекта edge. Но мы можем улучшить этот метод, если будет хранить список отсортированным. Тогда нам нужно найти бинарным поиском вершину в списке и печатать все вершины пока вершина в списке совпадает с переданной в метод.

Операции добавления и удаления вершины в такой случае невозможны, так как у нас нет вершин. Хотя метод удаления вершины можно реализовать, удалив все ребра, исходящие из заданной вершины. Но для простоты в этим методах мы выбрасываем исключение.

Метод добавления / удаления нового ребра - просто добавление / удаления объекта edge в список ребер.

Посмотрим что получилось.

Для взвешенного графа опять же метод добавления ребра будет отличаться весом, и методе print добавим вывод веса.

Посмотрим на вывод взвешенного графа.

Из плюсов такого способа можно отметить простоту, и легкое добавление нового ребра.

Но поиск в неотсортированном списке происходит за линейное время. К тому же нельзя добавить вершину без ребер. Это основные минусы.

Способ 3: Список смежности

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

У нас есть список всех вершин. Элементы списка - связный список, который хранит все вершины в которые можно попасть из данной вершины. Элементы связного списка просто числа, равные вершине (для ориентированного графа) или структура данных, хранящая номер вершины и вес (для взвешенного графа).

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

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

Методы dump и print.

Метод нахождения всех доступных вершин из заданной очень быстрый, т.к. поиск в ArrayList по индексу происходит за константное время. Мы находим LinkedList и выводим его содержимое

Добавление новой вершины - добавление нового связного списка. Удаление можно выполнить или как удаление связного списка, или как удаление всех вершин из заданной вершины (закомментированный вариант). Но при удалении связного списка все вершины, которые находятся дальше в списке сдвинутся на 1. Возможно это не то, что мы ожидаем.

Добавление или удаление ребра - добавление или удаление элемента в связный список.

Вывод для графа на основе списка смежности.

Для взвешенного графа мы добавим новый класс Pair<E, T>, который будет содержать вершину и вес.

Теперь элементами связного списка будут объекты типа Pair.

Также методы print и addEdge для взвешенного графа изменятся и будут учитывать вес.

Вывод для взвешенного графа следующий.

Заключение

Мы рассмотрели 3 основных способа представления графа в программе.

• Матрица смежности
• Список ребер
• Список смежности

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

И напоследок, весь исходный код можно найти на github.