Хранение графов списками смежности

Честные списки смежности

Простой способ хранения графов, которые вы уже знаете — это матрица смежности. Но она не работает, если вершин много, а ребер не очень много. Типичный пример, часто встречающийся в современных задачах — до $100\,000$ вершин и до $100\,000$ ребер. Матрицу размером $100\,000\times 100\,000$ в память просто не влезет.

Для хранения таких графов применяют другой способ — так называемые списки смежности (или списки смежных вершин, или списки ребер, хотя насчет последнего термина есть разночтения). А именно, будем для каждой вершины хранить в связном списке все выходящие из нее ребра.

Простой пример — невзвешенный граф. В таком случае обычно нам не надо хранить выходящие из вершины ребра, достаточно хранить вершины, куда эти ребра идут. Поэтому просто сделаем $N$ (по количеству вершин) связных списков, в $i$-м из которых будем хранить вершины, смежные с $i$.

Пример: неориентированный граф с ребрами 1-2, 2-3, 3-4, 4-2 будем хранить в следующих четырех списках:

список 1:  2
список 2:  1 3 4
список 3:  2 4
список 4:  3 2

(порядок элементов в конкретном списке нам обычно не важен).

Аналогично, ориентированный граф с ребрами 1->2, 2->3, 3->4, 2->4 будем хранить в следующих четырех списках:

список 1:  2
список 2:  3 4
список 3:  4
список 4:  (пустой)

Т.к. в списке расходуется память только на реально нужные элементы, то элементов списков в сумме будет столько же, сколько и ребер (или в два раза больше для неориентированных графов), т.е. $100\,000$ ребер в память вполне влезут, даже если вершин столько же.

Если граф взвешенный, то в каждом элементе списка мы будем хранить не только вершину, куда идет соответствующее ребро, но и вес этого ребра. И т.п. — если нам нужна другая информация о ребрах, просто будем ее хранить в элементах списка.

Ускорение поисков

Подобное хранение позволяет также ускорить многие известные нам алгоритмы. А именно, что в поиске в ширину, что в поиске в глубину самое медленное место — это перебор всех соседей каждой вершины. С матрицей смежности нам приходится просматривать все вообще вершины, в результате чего соседи одной вершины перебираются за $O(N)$, а общая сложность получается $O(N^2)$.

Если же хранить граф списками смежности, то соседей каждой вершины можно перебрать за $O(e_i)$, где $e_i$ — количество выходящих из нее ребер. В результате сложность что поиска в ширину, что поиска в глубину получается $O(E)$, где $E$ — общее количество ребер в графе (т.к. нам по сути надо перебрать всех соседей всех вершин).

Динамические массивы

Есть немного другой подход. А именно, для каждой верщины будем просто хранить всех ее соседей в отдельном (для этой вершины) массиве. Но возникает проблема: длины массивов для разных вершин будут разные и заранее непредсказуемые. (Мы могли бы сделать массивы достаточно длинными, но у нас не хватит памяти). Для этого существует структура данных динамический массив — массив, у которого можно менять длину по ходу работы программы. Во многих языках он есть стандартный, там, где его нет, его можно реализовать. Реализацию я тут излагать не буду, а просто напишу, как использовать стандартную.

Free pascal

Пишете так:

var a:array of integer;

(Именно так, без указания размера!)

Это дает вам массив изначально нулевой длины (т.е. в нем изначально нет ни одного элемента). На этом массиве вы можете использовать процедуру setlength(a, k); — установить длину массива в k. Если длина массива раньше была меньше, то тем самым вы приписываете в конец массива элементы. Если была больше — убираете лишние элементы с конца массива.

Вторая полезная функция — length(a) — возвращает текущую длину массива.

Внимание! В таких массивах все элементы нумеруются с нуля! Т.е. если вы сделали setlength(a,10), то вы получили массив, в котором элементы нумеруются с 0 до 9, при этом length(a) будет равно 10.

Типичное применение для графов (разберитесь как оно работает):

// граф
var gr:array[1..100000] of array of integer;

// добавить один элемент в конец массива
procedure addElement(var a:array of integer; x:integer);
begin
setlength(a, length(a)+1);
a[length(a)-1]:=x; // обратите внимание на -1!
end;

...
//чтение ориентированного графа
read(n,m); // число вершин и ребер
for i:=1 to n do begin
    read(u,v); // очередное ребро -- u->v
    addElement(gr[u], v);
end;

// поиск в глубину
procedure dfs(u:integer);
var i:integer;
begin
if was[u]<>0 then exit;
was[u]:=1;
for i:=0 to length(gr[u])-1 do
    dfs(gr[u][i]); // gr[u,i] тоже должен бы работать
end;

Контрольный вопрос: чем динамические массивы хуже связных списков?

C++

Стандартный тип для динамического массива в C++ — std::vector. (Да и для не-динамического массива тоже.) Используется так:

#include <vector>
using namespace std;
...
vector<int> a; // динамический массив из int'ов, изначальной длины 0
vector<double> b(10); // из double'ов, изначальной длины 10
int i = a.size(); // длина массива
a.push_back(5); // добавляет элемент в конец массива

Есть еще полезные функции, можете посмотреть в интернете.

Применение для графов:

// чтение ориентированного графа
cin >> n >> m; // считали число вершин и ребер
// собственно граф
vector<vector<int> > gr(n); // массив длины n, каждый элемент его --- это массив int'ов начальной длины 0
                            // т.е. двумерный массив изначальных размером n x 0
for (int i=0; i<m; i++) {
    cin >> u >> v; // очередное ребро u->v
    gr[u].push_back(v);  // добавили в список соседей
}

// поиск в глубину
void dfs(int u) {
    if (was[u]) return;
    was[u] = 1;
    for (int i=0; i<gr[u].size(); i++)
        dfs(gr[u][i]);
}

// поиск в глубину, c++11 style
void dfs(int u) {
    if (was[u]) return;
    was[u] = 1;
    for (auto v: gr[u])
        dfs(v);
}

Контрольный вопрос: чем динамические массивы хуже связных списков?