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

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

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

  3. Поиск в глубину (dfs = depth-first-search)
    4. 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. Трёх цветный dfs. Полезное свойство: нет рёбер из чёрной в белую.
    4. Поиск цикла в ориентированном графе. Корректность.

  4. Рёбра dfs
    1. dfs строит остовное дерево
    2. Терминология: древесные прямые, обратные, перекрёстные
    3. Теорема: относительно дерева dfs в неорграфе нет перекрёстных рёбер
− Перерыв −
  1. dfs умеет ещё и такое
    1. Двудольность графа, наличие нечётных циклов. Раскраска графа за O(V+E)
    2. Поиск цикла в неор графе: не идём в отца (используем обычный dfs с пометками). Для мульти графа, запоминаем номер ребра, не идём по обратному ему.
    3. Восстановление цикла: хранить стек вершин на пути dfs, цикл лежит на вершине стека
    4. topsort. Определение, поиск.

  2. Альтернативный алгоритм для topsort за линейное время. События "из вершины ничего не выходит, её можно взять"

  3. Связь с динамикой: (1) ленивая динамика = dfs, (2) чтобы динамику делать без рекурсии, можно сперва насчитать topsort и перебирать вершины в порядке topsort
  4. Компоненты сильной связности
    1. Определение. Доказательство отношения эквивалентности. Лемма: есть путь ⇒ есть простой путь
    2. Алгоритм поиска за O(VE)
    3. Алгоритм поиска за O(V+E) двумя dfs (topsort + красим по обратным рёбрам)