Графы. Способы представления графа в программе

В этой теме 0 ответов, 1 участник, последнее обновление  Васильев Владимир Сергеевич 1 год, 4 мес. назад.

  • Автор
    Сообщения
  • #2916

    Граф в программировании представляет собой совокупность двух конечных множеств:

    • множества вершин (точек, узлов);
    • множества дуг (ребер), соединяющих вершины.

    В качестве простейшего примера графа часто приводят систему дорог между городами, где города – это вершины, а дороги – ребра графа. Однако, вокруг нас есть множество и более обыденных примеров:

    • электрическая схема является графом, в котором вершины – элементы схемы, а дуги – соединяющие провода;
      graph_example_circuit_drawing
    • блок-схема алгоритма;
    • система каталогов операционной системы является частным случаем графа – каталоги и папки задаются вершинами, а отношение вложенности – дугами.

    Если направление ребер графа имеет значение (например при отражение отношения вложенности каталогов) – то граф называется ориентированным. Если направление не важно (например при соединении элементов электрической цепи) – граф является неориентированным. Кроме того, ребрам часто приписывается вес, граф в этом случае называется взвешенным – в системе дорог веса ребер могут отражать расстояния между городами.

    В связи с этим возникает необходимость обработки графов компьютером, но для этого необходимо сначала каким-то удобным для обработки образом разместить его в памяти. Итак, граф (G) – это совокупность вершин (V), и дуг (E), в зависимости от того, как они задаются, выделяются следующие способы машинного представления графа:

    • матрица смежности для графа из N вершин хранится в виду двумерного массива размером N x N. Вершины графа в этом случае задаются номерами (индексами строк и столбцов матрицы), а ячейка графа matrix[i, j] отражает наличие дуги между соответствующими вершинами. Например, при наличии дуги в ячейке может быть записана единица (или вес ребра i->j для взвешенного графа) , а при отсутствии – ноль;
    • матрица инцидентности для графа из N вершин и M дуг хранится в виде двумерного массива размером N x M. Ячейка матрицы matrix[i, j] отражает инцидентность ребра j вершине i, т.е. тот факт, что это ребро выходит или входит в вершину i. Если ребро не связано с вершиной – в соответствующей ячейке матрицы записывается ноль, в противном случае единица (если граф ориентированный, то начало ребра можно отметить -1, а конец 1, если граф взвешенный – единица может быть заменена весом соответствующего ребра).

    Пример графа:

    graph_example

    Матрица смежности графа:

    A B C D E F G
    A 0 12 0 0 0 16 3
    B 12 0 8 0 0 0 6
    C 0 8 0 4 0 0 8
    D 0 0 4 0 14 0 30
    E 0 0 0 14 0 28 11
    F 16 0 0 0 28 0 13
    G 3 6 8 30 11 13 0

    Матрица инцидентности графа:

    AB BC CD DE EF FA AG BG CG DG EG FG
    A 12 0 0 0 0 0 3 0 0 0 0 0
    B 12 8 0 0 0 0 0 6 0 0 0 0
    C 0 8 4 0 0 0 0 0 8 0 0 0
    D 0 0 4 14 0 0 0 0 0 30 0 0
    E 0 0 0 14 28 0 0 0 0 0 11 0
    F 0 0 0 0 28 16 0 0 0 0 0 13
    G 0 0 0 0 0 16 3 6 8 30 11 13

    Работая с приведенными матрицами возможно, например, найти в графе кратчайшие пути между вершинами, построить минимальные остовы и т.д., однако, у них есть недостатки:

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

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

    Списки смежности графа:

    A B(12) F(16) G(3)
    B A(12) C(8) G(6)
    C B(8) D(4) G(8)
    D C(4) E(14) G(30)
    E D(14) F(28) G(11)
    F A(16) E(28) G(13)
    G A(3) B(6) C(8) D(30) E(11) F(13)

    Списки смежности и инцидентности решают проблему расширяемости графа, т.к. новые узлы и дуги могут быть очень просто и эффективно добавлены во время выполнения программы, кроме того они более оптимальны по памяти, т.к. хранятся только данные о существующих дугах. Однако, такой способ представления графа менее эффективен по процессорному времени, т.к. для проверки существования дуги в худшем случае нужно будет перебрать все дуги, выходящие из некоторой вершины, но в матрице смежности было достаточно обратиться к элементу массива (асимптотическая сложность ухудшилась с O(1) до O(K) при использовании связных списков или O(log(K)) при использовании хеш-массивов). Важно, что K в этом случае – количество смежных вершин, для многих графов оно не будет очень большим (например, если граф представлял бы карту города, то скорее всего значение K для каждой вершины не превышало бы 4-6), в связи с этим, нужно очень внимательно выбирать структуру данных для хранения списков смежности/инцидентности.

    Литература по теме:

Для ответа в этой теме необходимо авторизоваться.