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

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

  2. Хранение графа в C++
    1. Тупо: массив всех рёбер
    2. Матрица смежности: bool[][], vector<bool>[], int[][] для мульти или взвешенного
      1. -: перебор соседей O(n), память O(n2), неудобно хранить мульти-взвешенный граф
      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)