Графы: основные понятия и алгоритмы

Определения

Граф — упорядоченная пара (V, E), где V — непустое множество вершин, E — множество (или мультмножество в случае мультгирафов) пар вершин (ребер).

Многие практически и олимпиадные задачи сводятся к графам. Например, графом можно описать сеть дорог, схему метро, электрическую цепь и т.д. Введем основные понятия для графов.

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

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

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

Хранение графов в памяти

Во-первых, будем считать, что все вершины пронумерованы от 1 до N. Если это не так, то мы можем перенумеровать имеющиеся вершины.

Для небольших графов удобно использовать матрицу смежности A = { a_ij }, где a_ij = 1, если есть ребро (i, j), иначе 0. Заметим, что матрица смежности неориентированного графа симметрична относительно главной диагонали. Матрица смежности требует O(N^2) памяти, поэтому ее применение ограничивается графами с числом вершин порядка 1000.

Для графов с большим числом вершин, но относительно малым числом ребер (такие графы называют разряженными) необходимо применять связные списки с несколькими головами (см. «Списки, стеки, очереди»). Также можно применять структуры данных реализованные в стандартных библиотеках: stl::vector в C++ (удобно и быстро) и ArrayList в Java (не очень удобно и достаточно медленно).

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

Алгоритмы

Сначала рассмотрим алгоритмы обхода графа. Они являются основой для многих алгоритмов (поиск путей, топологическая сортировка, поиск циклов, поиск максимального потока и др.).

Поиск в глубину

Поиск в глубину (Depth-first search, DFS) заключается в следующем: фиксируем текущую вершину, помечаем ее как посещенную, и пока есть смежные с ней не посещенные вершины, рекурсивно их обходим. Для определения того, что вершина посещена, обычно используется массив флагов.

Реализация на Java:

0000:     int vNum; // количество вершин
0001:     int eNum; // количество ребер
0002:     boolean[][] graph; // матрица смежности
0003:     boolean[] used; // массив пометок
0004:
0005:     void justDFS(int v) {
0006:         used[v] = true; // помечаем вершину
0007:         for (int nv = 0; nv < vNum; nv++) // перебираем вершины
0008:             if (!used[nv] && graph[v][nv]) // если вершина не помечена, и смежна с текущей
0009:                 justDFS(nv); // рекурсивно запускаем от нее DFS
0010:     }

Можно реализовать и нерекурсивный вариант поиска в глубину, используя стек.

Поиск в ширину (Breadth-first search, BFS)

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

Рассмотрим простейшую реализацию на Java:

0000:     void justBFS(int v) {
0001:         boolean[] used = new boolean [vNum]; // массив пометок
0002:         int[] queue = new int [vNum]; // очередь
0003:         int qH = 0; // голова очереди
0004:         int qT = 0; // хвост
0005:         
0006:         /* <обработка вершины v> */
0007:         used[v] = true; // помечаем исходную вершину
0008:         queue[qT++] = v; // помещаем ее в очередь
0009:         
0010:         while (qH < qT) { // пока очередь не пуста
0011:             v = queue[qH++]; // извлекаем текущую вершину
0012:             for (int nv = 0; nv < vNum; nv++) { // перебираем вершины
0013:                 if (!used[nv] && graph[v][nv]) { // если nv не помечена и смежна с v
0014:                     /* <обработка вершины nv> */
0015:                     used[nv] = true; // помечаем ее
0016:                     queue[qT++] = nv; // и добавляем в очередь
0017:                 }
0018:             }
0019:         }
0020:     }
Поиск компонент связности

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

Заметим, что если запустить обход из любой вершины какой-нибудь компоненты, то мы обойдем все вершины данной компоненты. Таким образом получаем следующий алгоритм: перебираем вершины, если текущая не помечена, увеличиваем счетчик компонент, и запускаем из текущей вершины поиск в глубину или ширину. Каждой вершине при обходе сопоставляем номер текущей компоненты.

Реализация:

0000:     void solve() {
0001:         used = new boolean [vNum]; // массив пометок
0002:         cc = new int [vNum]; // сс[v] = номер компоненты, к которой принадлежит v
0003:         ccNum = 0; // количество компонент
0004:         
0005:         for (int v = 0; v < vNum; v++) { // перебираем вершины
0006:             if (!used[v]) { // если текущая не помечена
0007:                 ccNum++; // значит мы нашли компоненту связности
0008:                 dfs(v); // запускаем на ней DFS
0009:             }
0010:         }
0011:     }
0012:     
0013:     void dfs(int v) {
0014:         used[v] = true;
0015:         cc[v] = ccNum; // ставим текущей вершине в соответствие номер компоненты
0016:         for (int nv = 0; nv < vNum; nv++)
0017:             if (!used[nv] && graph[v][nv])
0018:                 dfs(nv);
0019:     }