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

1. Матрица смежности. 15 По строкам и столбцам располагаются номера вершин. 1 Если рёбра между ними отсутствуют, то на пересечении ставится 0, если ребро есть — 1. 1
2. Матрица инцидентности. 2 Для хранения используется двумерная матрица, в каждом столбце которой записано одно ребро. 2 Напротив вершин, инцидентных этому ребру, записана 1, в остальных случаях — 0. 2
3. Список смежности. 1 Представляет собой набор списков по числу вершин в графе. 1 Каждый список — это перечисление всех смежных данной вершине. 1
4. Список рёбер. 1 Представляет собой перечисление всех рёбер графа. 1
5. Структура с оглавлением. 2 Один из самых экономных способов представления графа в памяти. 2 Все массивы смежности записываются в одну строчку, создаётся массив-оглавление с указателями на начало списка для каждой вершины. 2
6. Список вершин и список рёбер. 2 Вершины записываются в односвязный список, от каждой вершины есть указатель на список всех рёбер, инцидентных данной вершине. 2 Каждое ребро, в свою очередь, имеет указатель на вторую инцидентную ему вершину и на следующее ребро. 2

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