Хранение графов списками смежности
Честные списки смежности
Простой способ хранения графов, которые вы уже знаете — это матрица смежности. Но она не работает, если вершин много, а ребер не очень много. Типичный пример, часто встречающийся в современных задачах — до $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); }
Контрольный вопрос: чем динамические массивы хуже связных списков?