Задача 2. Лекция. Графы. Способы представления ≡

Условие

Рассмотрим граф G(V, E) с n = |V| вершинами v₁, ..., v_n. Его матрицей смежности (adjacency matrix) называется (n × n) — матрица a, в которой a_ij = { 1, если (v_i, v_j) ∈ E0 иначе.

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

Пример кода для считывания графа с n вершинами и m рёбрами в матрицу смежности.

var
    adj: array of array of Boolean;
    n, m, u, v, i: Integer;
begin
    Read(n, m);
    SetLength(adj, n, n);
    for i := 1 to m do begin
        Read(u, v);
        adj[u, v] := true;
        adj[v, u] := true;
    end;
end.

Альтернативное представление — список смежности (adjacency list). Требуемая при этом память пропорциональна размеру графа (сумме числа вершин и числа ребер). Элементами списка смежности являются массивы, по одному для каждой вершины графа. Для вершины u в таком списке хранятся вершины, в которые ведут ребра из u, т.е. вершины v, для которых (u, v) ∈ E. Для ориентированного графа каждое ребро входит только в один из этих списков (для начальной вершины), а для неориентированного — в два (для двух концов ребра). Список смежности, таким образом, требует памяти O(V + E). Проверка наличия ребра (u, v) теперь требует просмотра списка вершины u (что может быть больше O(1) шагов). Зато в этом представлении легко просмотреть всех соседей заданной вершины (что часто бывает необходимо). Список смежности для неориентированного графа симметричен (если u содержится в списке для v, то и v содержится в списке для u).

Пример кода для считывания графа с n вершинами и m рёбрами в список смежности.

var
    adj: array of array of Integer;

procedure Add(a, b: integer) begin
    SetLength(adj[a], Length(adj[a]) + 1);
    adj[a, High(adj[a])] = b;
end;

var
    n, m, u, v, i: Integer;
begin
    Read(n, m);
    SetLength(adj, n);
    for i := 1 to m do begin
        Read(u, v);
        Add(u, v);
        Add(v, u);
    end;
end.

std::vector< std::vector< int>> adj;
int n, m;
std::cin >> n >> m;
adj.resize(n);
for(int i = 0; i < m; ++i) {
    int u, v;
    std::cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
}
        

Матрица смежности или список смежности?

Что лучше? Ответ зависит от отношения между числом вершин |V| и числом ребер |E|. Заметим, что |E| может быть довольно малым — порядка |V| (если |E| сильно меньше |V|, то граф уже вырожденный — в частности, содержит изолированные вершины). Или же довольно большим — порядка |V|² (если граф содержит все возможные ребра). Графы с большим числом ребер называют плотными (dense), с малым — разреженными (sparse).

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

А вот хранить граф Интернета в виде списка смежности вполне разумно, поскольку хранить нужно несколько десятков миллиардов гиперссылок, каждая из которых будет занимать в списке всего несколько байтов, и такого размера диск поместится в карман. Такая разница происходит из-за того, что граф Интернета очень разрежен: страница содержит в среднем пару десятков ссылок на другие страницы — из нескольких миллиардов возможных.