В прошлом параграфе мы обсудили основные определения теории графов. Однако, чтобы работать с графами, необходимо их как-то хранить в памяти компьютера. К сожалению, не существует универсального способа хранения графов, потому что каждый имеет свои достоинства и недостатки.
Рассмотрим такой способ хранения графа, как матрица смежности. Матрица смежности представляет собой матрицу, где по строкам и столбцам располагаются номера вершин. Если рёбра между вершинами отсутствует, то на пересечении -ой строки и -ого столбца ставится 0. Если ребро есть, то ставят 1. Пример графа и его матрицы смежности приведён на рисунке ниже.
💡 Остановитесь и подумайте:
Всегда ли матрица смежности для неориентированного графа симметрична?
Рассмотрим пример матрицы смежности для ориентированного графа. В целом, отличий не так много, кроме того, что матрица смежности перестала быть симметричной. Подумайте, почему.
Также при работе с графами применяется и матрица инцидентности. По столбцам располагаются рёбра, а по строкам номера вершин. На пересечении -ой вершины и -ого ребра ставится 1, если одним из концов ребра была вершина . Пример приведён ниже.
В случае ориентированного графа матрица инцидентности не сильно меняется, за исключением того, что на пересечении -ой вершины и -ого ребра ставится 1, когда дуга входит в вершину и -1, когда выходит.
Для экономии памяти может использоваться список смежности, который представляет из себя набор списков по числу вершин в графе. Каждый список представляет из себя перечисление всех смежных данной вершине.
В случае ориентированного графа список смежности выглядит аналогичным образом.
В некоторых случаях удобнее использовать список рёбер. Он представляет собой перечисление всех рёбер графа. Пример приведен ниже.
✒️ Упражнение:
Подумайте, а какой вариант хранения графа в памяти компьютера самый оптимальный. Почему?