Поиск в глубину: сильная связность (10 декабря 2024)

1. Примеры графов, определения
   1. Слова: граф, смежность, инцидентность, орграф, неорграф.
   2. Друзья/знакомства, зависимости между работами/пакетами, страны и дороги
   3. Граф состояний (два героя дубасят друг другу: состояние = <хп1,мана1,позиция1,хп2,мана2,позиция2>).
   
   
2. Хранение графа
   1. Если удалять рёбра? vector<set<int>>
   2. Если плотный граф V = 10 000? vector<bitset>
   3. Если хотим минимизировать память? sizeof(vector<int>) = 24, мультисписок
   
   
3. Кодим dfs
   1. Рекурсия + пометка вершин. Время работы.
   2. Поиск компонент связности. Время работы.
   3. Восстановление пути на обратном ходу рекурсии
   
   
4. Применения dfs
   1. Поиск цикла.
   2. Остовное дерево dfs. Классифицакия рёбер.
   3. Topsort.
   
   
5. [20 минут] Компоненты сильной связности
   1. Тривиальный алгоритм поиска за O(kE)
   2. Алгоритм поиска за O(V+E) двумя dfs (topsort + красим по обратным рёбрам)
   3. Доказательство корректности (любая достижимая по обратным рёбрам другая компонента уже покрашена)
   4. Конденсация сс. Определение, построение.