2. Представление графов.
 

Реализация алгоритмов обработки графов в виде машинных процедур в высокой степени зависит от способа представления графов на логическом и физическом уровнях. А способ представления графа существенно зависит от типов структур данных, допускаемых используемым языком программирования и типом ЭВМ. Выбор наилучшего способа представления графа зависит от природы моделируемых данных (процессов) и операций, выполняемых над ними. На выбор подходящего представления влияют такие факторы, как число вершин, максимальная полустепень исхода, частота изменения числа вершин и ребер, является ли граф ориентированным или нет и т.д. Таким образом, какого-то одного наилучшего способа представления не существует, лучшее представление зависит от решаемой задачи. Выбор конкретного представления графа может существенно повлиять на эффективность его обработки.

Граф G = (V,E) может быть полностью определён простым перечислением двух множеств V и E. Однако в большинстве случаев этот способ представления не позволяет создавать эффективные алгоритмы обработки графов.

Широко распространенным способом представления графов являются матричный способ и соответствующее отображение их в векторной (смежной) памяти в виде двухмерных массивов. Этот способ имеет несомненные достоинства:

а) массивы легко хранить и обрабатывать в ЭВМ;
б) для получения характеристик графа могут быть использованы операции матричной алгебры;
в) имеются хорошо известные алгоритмы обработки графов.

Однако матричный способ представления имеет и крупный недостаток, связанный с тем, что массивы являются статическими по размерам структурами.