Структуры данных для хранения графов: обзор существующих и две «почти новых»

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

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

Итак, поехали. Какие же варианты структур данных для «графохранения» мы имеем.
 

1. Матричные структуры данных

1.1 Матрица смежности. Матрица смежности представляет из себя матрицу, где заголовки строк и столбцов соответствуют номерам вершин графа, а само значение каждого ее элемента a(i,j) определяется наличием или отсутствием ребер между вершинами i и j (ясно-понятно, что для неориентированного графа такая матрица будет симметрична, ну или же можно договориться, что все значения мы храним лишь выше главной диагонали). Для невзвешенных графов a(i,j) можно задать количеством ребер из i в j (если нет такого ребра, то a(i,j)= 0), а для взвешенных также – весом (суммарным весом) упомянутых ребер.