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

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

Граф G = (V, E) имеет два естественных параметра: количество узлов |V| и количество  ребер  |E|.  Для  их  обозначения  мы  будем  использовать  запись  n = |V | и m = |E|. Время выполнения будет формулироваться в зависимости от этих двух параметров. Как обычно, мы будем ориентироваться на полиномиальное время выполнения, желательно с низкой степенью.

Однако из этих сравнений не всегда очевидно, какой из двух вариантов времени выполнения (например, 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, если граф содержит ребро (u, v), или 0 в противном случае.

Для ненаправленного графа матрица A симметрична, а A[u, v] = A[v, u] для всех узлов u, v Ѯ V. С представлением матрицы смежности наличие в графе заданного ребра (u, v) проверяется за время O(1). Тем не менее такое представление имеет два основных недостатка.

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

В худшем случае v может иметь Θ(n) инцидентных ребер, тогда проверка всех ребер будет выполняться за время Θ(n) независимо от представления. Но на практике во многих графах количество инцидентных ребер для большинства узлов существенно меньше, поэтому было бы полезно иметь возможность более эффективно искать инцидентные ребра.

Для представления графов в книге используется список смежности, который лучше подходит для разреженных графов, то есть графов, у которых количество ребер существенно меньше n2. В представлении списка смежности для каждого узла v создается запись со списком всех узлов, с которыми узел v соединен ребрами.

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

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