При программировании задач обработки сетевых структур требуется решить вопрос о представлении графа структурами данных языка программирования. Выбор представления графа определяется прежде всего тем, какие алгоритмы обработки графов используются, а также соображениями экономии памяти при обработке очень больших графов или в условиях жестких ограничений на расход памяти.
Говоря о представлении графа, имеют в виду прежде всего вопрос о представлении в памяти его структуры, т. е. считается, что по представлению графа нужно уметь определять, какие вершины с какими другими вершинами в графе связаны. На практике кроме структуры графа нужно каким-то образом представлять и нагрузку на его вершины и дуги. От того, какие элементы графа нагружены и какого типа эта нагрузка, тоже зависит представление графа.
Ниже приводится несколько способов представления графов, причем для каждого способа указано, для каких алгоритмов он подходит, а также дана приблизительная оценка занимаемой памяти. Везде далее считается, что число вершин графа N = card(V) и число дуг (или ребер) графа M = card(E) — величины постоянные. Можно считать, что вершины графа имеют номера от 0 до N-1, а каждая дуга характеризуется парой номеров вершин, инцидентных этой дуге.
В листингах будем представлять только структуру графов, причем для каждого способа представления опишем только конструктор соответствующего класса и операции добавления новой дуги и проверки наличия дуги с заданными концами. Поскольку большинство операций, представленных ниже в листингах, одинаковы для всех представлений графов, имеет смысл описать абстрактный класс Graph, в котором и определить все эти операции в виде пустых виртуальных функций. Тогда конкретные представления графов будут описаны в виде классов, производных от базового класса Graph.