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

Существуют два основных способа представления графов: матрица смежности и список смежности. В этой книге будет использоваться представление списка смежности. Тем не менее начнем мы с обзора этих двух представлений и обсудим их достоинства и недостатки.

Граф G = (V, E) имеет два естественных параметра: количество узлов \ V\ и ко- личество ребер |E|. Для их обозначения мы будем использовать запись n = \V| и m = |E|. Время выполнения будет формулироваться в зависимости от этих двух параметров. Как обычно, мы будем ориентироваться на полиномиальное время вы- полнения, желательно с низкой степенью. Но когда время выполнения зависит от двух параметров, сравнение не всегда однозначно. Какое время лучше — O(m2) или n - 1 ребер. Однако из этих сравнений не всегда очевидно, какой из двух вариантов времени выполнения (например, m2 или n3) лучше, поэтому мы будем анализировать время выполнения с учетом обоих параметров. В этом разделе будет реализован базовый алгоритм поиска в графе с временем O(m + n). Это время будет называться линейным, потому что время O(m + n) необходимо просто для чтения ввода. Учтите, что при работе со связными графами время выполнения O(m + n) эквивалентно O(m), потому что m > n - 1.

Возьмем граф G = (V, E) с n узлами, множество которых обозначается V ={1, ..., n}. В простейшем способе представления графа используется матрица смежности. Это матрицаA размером n χ n, в которой элемент A[u, v] равен 1, если граф содержит ребро (и, v), или 0 в противном случае. Для ненаправленного графа матрица A симметрична, а A[u, v] = A[v, u] для всех узлов u, v V. С представле-

нием матрицы смежности наличие в графе заданного ребра (и, v) проверяется за время 0(1). Тем не менее такое представление имеет два основных недостатка.

♦ Затраты памяти составляют 0(n2). Если количество ребер в графе существенно меньше n2, возможны более компактные представления.

♦ Многие алгоритмы графов требуют проверки всех ребер, инцидентных заданно- му узлу v. В представлении матрицы смежности для этого требуется перебрать все остальные узлы w и проверить элемент матрицы A[v, w], чтобы узнать, суще- ствует ли ребро (v, w), а эта проверка занимает время 0(n). В худшем случае v может иметь 0(n) инцидентных ребер, тогда проверка всех ребер будет выпол- няться за время 0(n) независимо от представления. Но на практике во многих графах количество инцидентных ребер для большинства узлов существенно меньше, поэтому было бы полезно иметь возможность более эффективно искать инцидентные ребра.

Для представления графов в книге используется список смежности, который лучше подходит для разреженных графов, то есть графов, у которых количество ребер существенно меньше n2. В представлении списка смежности для каждого узла v создается запись со списком всех узлов, с которыми узел v соединен ре- брами. А если говорить точнее, создается массив Adj, в котором Аdj[v] — запись со списком всех узлов, смежных с узлом v. Для ненаправленного графа G = (V, E) каждое ребро e = (v, w) E присутствует в двух списках смежности: узел w при-

сутствует в списке узла v, а узел v присутствует в списке узла w.

Сравним представления матрицы смежности и списка смежности. Начнем с пространства, необходимого для представления. Матрица смежности имеет размеры n χ n, а следовательно, занимает пространство 0(n2). С другой сторо- ны, мы утверждаем, что для хранения списка смежности достаточно простран- ства 0(m + n). Ниже приводится обоснование.

Для начала нам понадобится массив указателей длины n для организации хра- нения списков в Аdj, а также место для самих списков. Длины списков могут отли- чаться от узла к узлу, но, как указано в предыдущем абзаце, каждое ребро e = (v, w) входит ровно в два списка: для v и для w. Таким образом, общая длина всех списков составляет 2m = 0(m).

Есть и другой (по сути, эквивалентный) способ обоснования этой границы. Степенью nv узла v называется количество ребер, инцидентных этому узлу. Дли- на списка в позиции Аdj [v] равна n , так что общая длина по всем узлам равна

0(∑..,”..) . Сумма степеней графа — характеристика, часто встречающаяся при анализе алгоритмов графов, поэтому полезно выяснить, чему она равна.

Доказательство. Каждое ребро e = (v, w) вносит вклад в эту сумму ровно два раза: один раз в величине nv, и один раз в величине nw. Так как в сумме учитываются вклады всех ребер, она составит 2m. ■


Сравнение матриц смежности со списками смежности можно резюмировать следующим образом.

(3.10) Представление графа в виде матрицы смежности требует простран- ства O(n2), а для представления в виде списка смежности достаточно простран- ства O(m + n).

Так как мы уже выяснили, что m < n2, ограничение O(m + n) никогда не бывает хуже O(n2), и оно намного лучше для разреженных графов, в которых m намного меньше n2.

Теперь нужно разобраться с простотой обращения к информации, хранящейся в этих двух представлениях. Вспомните, что в матрице смежности проверка при- сутствия в графе конкретного ребра (u, v) выполняется за время O(1). В списке смежности проверка может занимать время, пропорциональное степени O(nv): чтобы узнать, входит ли ребро v в список, нужно пройти по указателям списка смежности и. С другой стороны, если алгоритм в настоящее время проверяет узел и, он может прочитать список соседей с постоянными затратами времени на каждого соседа.

С учетом сказанного список смежности является естественным представлением для изучения графов. Если алгоритм в настоящее время рассматривает узел u, он может прочитать список соседей с постоянным временем на каждого соседа; пере- меститься к соседу v после его обнаружения в списке за постоянное время; и быть готовым к чтению списка, связанного с узлом v. Таким образом, списковое пред- ставление соответствует физическому «изучению» графа, в котором при переходе к узлу и вы узнаете его соседей и можете прочитать их с постоянным временем для каждого соседа.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Представление графов:

  1. ПРЕДСТАВЛЕНИЕ
  2. ПРЕДСТАВЛЕНИЕ ПАМЯТИ
  3. Музыкальное представление на телевидении
  4. ПРЕДСТАВЛЕНИЕ ВЫТЕСНЕННОЕ
  5. ПРЕДСТАВЛЕНИЕ ОБЩЕЕ
  6. ПРЕДСТАВЛЕНИЕ ПРОСТРАНСТВЕННОЕ
  7. КОНЦЕПЦИЯ ПРЕДСТАВЛЕНИЙ СОЦИАЛЬНЫХ
  8. Представления о деньгах
  9. 2.4.2. Наглядное представление оригинальной ситуации
  10. ПРЕДСТАВЛЕНИЕ РЕЛИГИОЗНОЕ: ПРОИСХОЖДЕНИЕ
  11. § 8.1. Общее представление о конфликтах в организации
  12. РЕАЛИЗАЦИЯ МЫСЛЕННОГО ПРЕДСТАВЛЕНИЯ
  13. 12. Наследственная трансмиссия и право представления
  14. ПРЕДСТАВЛЕНИЕ ЕДИНИЧНОЕ
  15. ПРЕДСТАВЛЕНИЕ КОЛЛЕКТИВНОЕ
  16. Развитие представлений о юридической психологии.
  17. «ХЭППЕНИНГ»: ПРЕДСТАВЛЕНИЕ СЛУЧАЙНОСТИ