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


Итак, можно себе представить, как нарисовать граф на бумаге, но как его хранить в программе?
Рисунок 18.
Рассмотрим несколько способов хранения ребер графа:
  1. Матрица смежности. Матрица смежности — квадратная матрица, размера n*n, где n — количество вершин в графе. Таким образом в ячейке [i][j] можно хранить вес ребра идущего из i-той вершины в j-ую, 1 или 0, если нужно только знать, существует ли ребро между этими вершинами.
  2. Рисунок 19. Матрица смежности.
      Плюсы:
    • Легкость задания ребер при таком способе хранения. Т. е.. чтобы задать ребро между известными вершинами, нужно просто изменить одну ячейку в массиве.
    • Маленькие временные затраты на проверку существования ребра между двумя вершинами. Проверить, есть ли ребро между двумя известными вершинами, можно за время O(1), т. к. для этого нужно просто извлечь значение соответственной ячейки массива.
      Минусы:
    • Большой расход памяти. Данный способ хранения вершин требует O(n2) памяти, что бывает очень невыгодно в разреженных графах. Также из этого следует, что таким способом нельзя задавать большие графы. Обычно такой способ представления ребер станвовится неэффективным уже при количестве вершин большем ста.
    • Большие временные затраты на перебор всех ребер из заданной вершины. Для того, чтобы узнать все вершины, в которые ведут ребра из данной, нужно совершить n проверок, т. е. это можно сделать за время O(n), в то время, как другие способы хранения ребер позволяют сократить это время.
  3. Список ребер. Список ребер — это структура, в которой каждой вершине соответствует список из ребер. Для этого кроме хранения самого ребра, для него требуется хранить ссылку на предыдущее ребро, исходящее из той же вершины, что и данное.
Пусть есть ребро (x;y). Тогда нам нужно знать две величины:
last[x] — ссылка на последнее ребро, котоорое было добавлено, как исходящее из x.
prev[a] — для каждого ребра a, ссылка на предыдущее добавленное ребро, которое исходит из той же вершины, что и a.
Рисунок 20.
    Плюсы:
  • Маленькие затраты памяти. Для хранения списка из m ребер требуется O(m) памяти, что обычно намного меньше, чем O(n2).
  • Быстрый перебор всех ребер, исходящих из заданной вершины. Так как каждое ребро связано с другим ребром, исходящим из такой же вершины, то просто переходя по этим связям можно перебрать все ребра, которые исходят из заданной вершины за время O(m), где m —количество ребер, исходящих из заданной вершины.
    Минусы:
  • Долгая проверка на существование ребра между двумя заданными вершинами. Т. к. у нас есть только ссылка на следующее ребро, то проверить, есть ли ребро с определенными начальной и конечной вершинами можно сделать, перебрав все ребра, исходящие из начальной вершины, что будет давать максимальную сложность O(m).

Комментариев нет:

Отправить комментарий