Графы и поиск в глубину (9 декабря 2019)

1. Определения
   1. Ор/неор, мульти (с кратными ребрами и петлями), взвешенные
   2. Путь, реберно и вершинно простой путь, цикл, простой цикл, ориентированный цикл, ацикличный граф
   3. Отношения достижимости, связности, компоненты связности, входящая и исходящая степень вершины
   
   
2. Хранение графа в C++
   1. Тупо: массив всех рёбер
   2. Матрица смежности: bool[][], vector<bool>[], int[][] для мульти или взвешенного
      1. -: перебор соседей O(n), память O(n²), неудобно хранить мульти-взвешенный граф
      2. +: наличие/добавление/удаление ребра за O(1)
   3. Список смежности: vector/set/list<int>[]
      1. +: перебор соседей O(deg), память O(m)
      2. -: наличие/удаление ребра за O(deg) и O(log(deg))
   4. Мультисписок
      1. В чём проблема list? (медленный, жрёт кучу памяти) В чём проблема vector? (медленный, жрёт кучу памяти)
      2. Несколько рукописных списков на массиве (мультисписок)
      3. head[vertex], vector<edge> edges; struct edge { int to, next; };
   
   
3. Поиск в глубину (dfs = depth-first-search)

   dfs(int v) // простейшая версия
   .. if (visited[v]) return
   .. visited[v] = true
   .. for (int u : g[v]) dfs(u)
   for (int i = 0; i < n; ++i) if (!visited[i]) dfs(i)
   

   1. Выделение компонент связности. Правим код.
   2. Поиск пути (восстановление пути на обратном ходу рекурсии). Правим код.
   3. Двудольность графа, наличие нечётных циклов. Раскраска графа за O(V+E)

1. Рёбра dfs
   1. dfs строит остовное дерево
   2. Терминология: древесные прямые, обратные, перекрёстные
   3. Теорема: относительно дерева dfs в неорграфе нет перекрёстных рёбер
   
   
2. dfs умеет ещё и такое
   1. Поиск цикла в неор графе: не идём в отца (используем обычный dfs с пометками). Для мульти графа, запоминаем номер ребра, не идём по обратному ему.
   2. Восстановление цикла: хранить стек вершин на пути dfs, цикл лежит на вершине стека
   3. Проблема для орграфа. Трёх цветный dfs. Поиск цикла в ориентированном графе.
   4. Корректность (отметим первую вершину цикла, в которую пришёл dfs)
   5. topsort. Определение, поиск.
   
   
3. Альтернативный алгоритм для topsort за линейное время без рекурсии. События "из вершины ничего не выходит, её можно взять"
   
4. Связь с динамикой: (1) ленивая динамика = dfs, (2) чтобы динамику делать без рекурсии, можно сперва насчитать topsort и перебирать вершины в порядке topsort
   
5. Компоненты сильной связности
   1. Определение. Доказательство отношения эквивалентности. Лемма: есть путь ⇒ есть простой путь
   2. Алгоритм поиска за O(VE)