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

Введение

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

1. матрица смежности

2. список ребер

3. списки смежности

Основы

Начнем с определения графа (да, не самого строгого определения). Граф - это условное представление множества объектов и то, как эти объекты связаны друг с другом. Например, объектами могут быть города, а их связями - дороги. Или объектами могу быть люди, а связями - их отношения. Такие объекты в общем случае называются вершинами графа, а связь между вершинами - ребрами. Например, кружки на изображении ниже - это вершины, а линии - ребра.

Мы будем рассматривать граф, состоящий из 4 вершин и 5 ребер, изображенный на рисунке 1. В графе слева неважно направление ребра. Например, если человек А является другом человеку В в социальной сети, то и человек В является другом человека А. Нет направленности. Такие графы называются неориентированным. (рис 1. слева).

В противоположность неориентированным граф может быть ориентированным (рис 1. справа). Например, вершины графа это города, а ребра - существующие рейсы поездов/самолетов. Если есть рейс из города А в город В - это не означает, что такой рейс есть обратно. Грани в таких графах имеют направление. Например, на рисунке 1 справа из вершины 1 можно попасть только в вершину 2, а из вершины 4 - в вершины 1 и 3.

Кроме того, граф может быть взвешенный (рис 2). Это означает, что граф не только ориентированный, но и каждое ребро имеет вес. Например, попасть из вершины 4 в вершину 1 можно двумя способами: напрямую по ребру с весом 9 или через вершину 3, тогда стоимость будет 8 (3 + 5). Весом может быть расстояние от одной вершины до другой, стоимость перемещения и т.д. Например, из города А можно попасть в город В разными способами: напрямую самолетом или поездом, но через промежуточный город.

Прежде чем переходить непосредственно к способам представления графа, сначала рассмотрим, что мы ожидаем от представления графа. Нам хотелось бы иметь следующие возможности:

• возможность посмотреть внутренние представление данных в графе 
• возможность посмотреть внутреннее представление данных в графе в удобном для восприятия формате
• возможность просмотреть все вершины, в которые можно попасть из конкретной вершины
• добавить новое/удалить ребро конкретной вершины
• добавить новую/удалить вершину
• возможность узнать количество ребер/вершин (возможно)

для всех этих методов заведем интерфейс BaseGraph, представленный ниже. 

Метод dump будет выводить внутреннее представление графа как есть, а print - в некотором удобном для восприятия формате. reachableVertexFrom - будет выводить вершины, в которые можно попасть из заданной вершины vertix. Для вершины 2 с графа на изображении выше метод напечатает только 4, т.к. из вершины 2 можно попасть только в вершину 4. Дальше идут методы добавления/удаления вершины и удаления граней. Для добавления новой грани, в зависимости от того, является граф взвешенным или нет, нужно или только вершины from и to, или еще и стоимость(cost) этого ребра. Поэтому добавим еще 2 интерфейса, наследующие BaseGraph и уточняющие тип графа: взвешенный (WeightedGraph) или нет (UnweightedGraph).

Это все что нужно сделать заранее.

Способ 1: Матрица смежности

Первый способ представления называется матрица смежности. Граф можно представить как матрицу N x N, где N - количество вершин. В нашем случае у нас 4 вершины. Далее, для каждой вершины (в каждой строке) мы отмечаем, есть ли ребро к остальным вершинам. Если есть - ставим 1 ( можно true) или вес ребра из вершины A в вершину В. Ноль обозначает то, что ребра между вершинами нет. Например, для вершины 2 есть ребро только к вершине 4, т.к. в пересечении строки 2 и столбца 4 значение больше 0. Если граф неориентированный, то он будет симметричен относительно диагонали из верхнего левого угла в нижний правый (ребро из 1 в 2 и из 2 в 1 - одно и тоже ребро).

Представлен такой граф будет как класс MatrixGraph, который содержит двумерную массив - это и есть наша матрица. В конструкторе такой граф принимает или список вершин, или изначальную матрицу. Так как массивы начинаются с 0, а нам удобнее работать с вершинами начиная с 1, при указании размера массива мы создаем его на 1 больше.

Метод dump выводит внутреннее представление графа непосредственно, а print в удобном для восприятия виде. В обоих случаях мы просто проходим по двумерному массиву. Заметим, что начинаем цикл с 1, а не с 0.

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

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

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

Где данный способ представления действительно хорош - это добавление новых ребер. Находим пересечение вершин в строке и столбце и заносим туда 1 или стоимость ребра. Для удаления ребра - записываем 0.

Создадим метод main и попробуем создать наш граф. Вызовем методы dump, print и reachableVerticlesFrom(4). Результаты изображены ниже.

Вывод метода dump в точности совпадает с изображением 3 (слева). Метод print печатает возможные переходы, а reachableVertexFrom(4) - переходы из вершины 4.

Все это касалось невзвешенного графа. Для взвешенного графа в матрице нужно хранить не 1, а вес ребра. Все методы для класса взвешенного графа совпадают с методами невзвешенного, кроме метода addEdge и немного изменен метод print(в вывод добавлен вес):

Демонстрация взвешенного графа:

Можно также заметить, что вывод метода dump точно совпадает с рис.3 (справа)

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

Из минусов - расходование памяти на двумерный массив, вне зависимости от количества вершин. Добавление и удаление вершин также вызывает трудности.

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