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

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

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

  • Автор
    Сообщения
  • #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

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

    ABCDEFG
    A012000163
    B12080006
    C0804008
    D004014030
    E0001402811
    F1600028013
    G3683011130

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

    ABBCCDDEEFFAAGBGCGDGEGFG
    A1200000300000
    B1280000060000
    C084000008000
    D00414000003000
    E000142800000110
    F000028160000013
    G0000016368301113

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

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

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

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

    AB(12)F(16)G(3)
    BA(12)C(8)G(6)
    CB(8)D(4)G(8)
    DC(4)E(14)G(30)
    ED(14)F(28)G(11)
    FA(16)E(28)G(13)
    GA(3)B(6)C(8)D(30)E(11)F(13)

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

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

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