Обход в глубину
Реализации класса графа С++
#include <iostream> #include <vector> class Graph { public: Graph(int num_of_vertexes) { n = num_of_vertexes; data = std::vector<std::vector<int>>(n); visited = std::vector<bool>(n, false); } void add_edge(int start, int stop) { data[start].push_back(stop); data[stop].push_back(start); } void DFS(int vertex) { if (visited[vertex]) { return; } visited[vertex] = true; std::cout << vertex + 1 << ' '; for (int neig: data[vertex]) { DFS(neig); } } int n = 0; std::vector<std::vector<int>> data; std::vector<bool> visited; }; int main() { int n, n_edges; std::cin >> n >> n_edges; Graph graph(n); for (size_t i = 0; i < n_edges; ++i) { std::cin >> from >> to; // how to add an edge? } }Реализации класса графа Python
class Graph: def __init__(self, num_of_vertices): self.n = num_of_vertices self.edges = [[] for _ in range(self.n)] self.visited = [False] * self.n def add_edge(self, start, stop): self.edges[start].append(stop) self.edges[stop].append(start) def DFS(self, vertex): if self.visited[vertex]: return self.visited[vertex] = True print(vertex + 1, end=" ") # Print the visited vertex for neighbor in self.edges[vertex]: self.DFS(neighbor) n = int(input()) n_edges = int(input()) graph = Graph(n) for _ in range(n_edges): from_vertex, to_vertex = map(int, input().split()) # how to add an edge? start_vertex = int(input()) graph.DFS(start_vertex)
Определение. Графом называется пара множеств \(G = (V, E)\), где множество \(V\) называется множеством вершин графа, а множество \(E\), состоящее из пар вершин \((u, v)\), называется множеством ребер графа.
Если существует ребро \((u, v)\), то говорят что оно соединяет вершины \(u\) и \(v\). Две вершины, соединенные ребром, называют смежными. Для вершины \(v\) любое ребро \((v, u)\) называется инцидентным ей. Число ребер, инцидентных вершине \(v\), называют степенью вершины \(v\).
Если какие-то две вершины соединены более, чем одним ребром, то говорят, что граф содержит кратное ребро. Если ребро соединяет вершину саму с собой, то такое ребро называют петлей. Если граф не содержит петель и кратных ребер, то он называется простым.
Граф называют ориентированным, если для каждого ребра задано направление, и неориентированным в противном случае. Для ребра \((u, v)\) обратным ребром называется ребро \((v, u)\). Неориентированные графы часто рассматривают как ориентированные, добавив вместо каждого ребра два для каждого направления.
Путем называется последовательность вершин, соединенных между собой ребрами. Если в пути не повторяются вершины, он называется простым. Из вершины \(v\) достижима вершина \(u\), если существует путь, начинающийся в \(v\) и заканчивающийся в \(u\). Если от каждой вершины достижима любая другая, граф называется связным.
Циклом называется путь, начинающийся и заканчивающийся в одной и той же вершине. Если помимо первой и последней вершины все остальные вершины на этой пути уникальны, то такой цикл называется простым. Граф называют ацикличным, если в нем нет простых циклов.
Ацикличный неориентированный граф называется лесом. Связный лес называется деревом. У деревьев есть другие эквивалентные определения:
Граф является деревом, если в нем \(n\) вершин и \((n-1)\) ребер и нет циклов.
Граф является деревом, если из любой вершины можно дойти в любую другую единственным образом.
Если дерево называется корневым, если у него есть ровно одна специальная вершина, называемая корнем. Часто подразумевается, что ребра корневого дерева ориентированы так, что от корня можно дойти от всех остальных вершин.
Хранение графов
Чаще всего в задачах по программированию вершины графа пронумерованы числами от \(0\) до \((n-1)\), чтобы было удобно обращаться к ним как к индексам в разных массивах.
В задачах графы чаще всего задаются списком всех ребер, которые нужно считать из ввода. В каком формате оптимально хранить граф? В зависимости от задачи есть несколько способов.
Список рёбер
Иногда достаточно хранить просто список ребер, которые нам дают на вход. Однако часто такой подход оказывается неэффективным для определенных операций.
Например, если мы хотим проверить, существует ли ребро между вершинами \(a\) и \(b\), в наивном случае нам нужно пройтись по всему списку в поисках такого ребра.
Чтобы избежать этого, можно задать этому списку какую-нибудь структуру. Например, можно отсортировать его сначала по первому элементу, а потом по второму, и тогда можно выполнять проверку бинарным поиском за \(O(\log m)\). Можно пойти дальше и обернуть его в какую-нибудь структуру, например в бинарное дерево или, ещё лучше, хеш-таблицу, но в любом случае возникают некоторые неэффективности.
Матрица смежности
Матрицей смежности называется двумерная матрица \(G\) размера \(n \times n\), в ячейке \(G_{ij}\) которой хранится единица, если существует ребро \((i, j)\), и ноль в противном случае.
При реализации обычно создается обычный двумерный массив типа bool. Если для каждой из \(n\) вершин мы храним информацию, существует ли ребро в каждую из остальных вершин, то суммарно мы храним \(n^2\) ячеек, и, следовательно, асимптотика по памяти — \(O(n^2)\).
В случае графов с кратными ребрами, иногда вместо нулей и единиц в матрице смежности хранят кратность соответствующего ребра.
Заметим, что в случае простых неориентированных графов, матрица смежности будет симметричной и иметь нули на главной диагонали.
Матрицы смежности очень эффективны для проверок — нужно считать и сравнить всего одну ячейку. Но что, если мы хотим для заданной вершины \(v\) иметь возможность быстро пройтись по всем её соседям? Здесь ничего быстрее \(O(n)\) не получится.
Список смежности
Давайте теперь для каждой из \(n\) вершин хранить не булевый массив, а номера всех смежных с ней вершин. Для этого нам потребуется любая динамическая структура, например std::vector в C++.
Поиск в глубину
Поиском в глубину (англ. depth-first search, DFS) или эйлеровым обходом называется рекурсивный алгоритм обхода корневого дерева или графа, начинающий в корневой вершине (в случае графа может быть выбрана произвольная вершина) и рекурсивно обходящий весь граф, посещая каждую вершину ровно один раз.
const int maxn = 1e5;
bool used[maxn]; // тут будем отмечать посещенные вершины
void dfs(int v) {
used[v] = true;
for (int u : g[v])
if (!used[u])
dfs(u);
}Немного его модифицируем, а именно будем сохранять для каждой вершины, в какой момент мы в неё вошли и в какой вышли — соответствующие массивы будем называть \(tin\) и \(tout\).
Как их заполнить: заведем таймер, отвечающий за «время» на текущем состоянии обхода, и будем инкрементировать его каждый раз, когда заходим в новую вершину:
int tin[maxn], tout[maxn];
int t = 0; // таймер
void dfs(int v) {
tin[v] = t++;
for (int u : g[v])
if (!used[u])
dfs(u);
tout[v] = t; // иногда счетчик тут тоже увеличивают
}У этих массивов много полезных свойств:
Вершина \(u\) является предком \(v\) \(\iff tin_v \in [tin_u, tout_u)\). Эту проверку можно делать за константу.
Два полуинтервала \([tin_v, tout_v)\) и \([tin_u, tout_u)\) либо не пересекаются, либо один вложен в другой.
В массиве \(tin\) есть все числа от 0 до \((n - 1)\), причём у каждой вершины свой номер.
Размер поддерева вершины \(v\) (включая саму вершину) равен \((tout_v - tin_v)\).
Если ввести нумерацию вершин, соответствующую \(tin\)-ам, то индексы любого поддерева всегда будут каким-то промежутком в этой нумерации.
Как мы дальше увидим, эти свойства очень полезны в других обходах и самых разных задачах на деревья.