Некоторые способы представления графов в компьютерных науках:

• Матрица смежности. 14 Для графа из N вершин хранится в виде двумерного массива размером N x N. 1 Вершины графа задаются номерами (индексами строк и столбцов матрицы), а ячейка графа отражает наличие дуги между соответствующими вершинами. 1
• Матрица инцидентности. 1 Для графа из N вершин и M дуг хранится в виде двумерного массива размером N x M. 1 Ячейка матрицы отражает инцидентность ребра j вершине i, то есть тот факт, что это ребро выходит или входит в вершину i. 1
• Списки смежности. 14 Для каждой вершины создаются списки соседей, а затем все эти списки помещаются в другой список. 4 Этот способ применяется, когда в графе небольшое количество рёбер, то есть когда граф разрежённый. 4
• Список рёбер. 2 Представляет собой перечисление всех рёбер графа. 2
• Структура с оглавлением. 3 Один из самых экономных способов представления графа в памяти. 3 Фактически все массивы смежности записываются в одну строчку, в один линейный массив, и создаётся массив-оглавление, с указателями на начало списка для каждой вершины. 3
• Список вершин и список рёбер. 3 Вершины записываются в односвязный список, от каждой вершины есть указатель на список всех рёбер, инцидентных данной вершины. 3 Каждое ребро, в свою очередь, имеет указатель на вторую инцидентную ему вершину и на следующее ребро. 3