Графы и алгоритмы
| № | Понятие / Алгоритм | Определение / Свойства |
|---|---|---|
| Основные понятия теории графов | ||
| 1. | Граф (математическое определение) | \( \displaystyle G = (V, E) \) Где \( V \) — множество вершин, \( E \) — множество рёбер. |
| 2. | Степень вершины \( \deg(v) \) | Количество рёбер, инцидентных вершине. Сумма степеней всех вершин равна удвоенному числу рёбер: \( \displaystyle \sum \deg(v) = 2|E| \) |
| 3. | Деревья | Связный ациклический граф. Свойства: \( 1. \) Любые две вершины соединены ровно одним путем. \( 2. \) Количество рёбер: \( \displaystyle |E| = |V| - 1 \) |
| Алгоритмы поиска и обхода графа | ||
| 4. | Поиск в ширину (BFS - Breadth-First Search) | Обходит граф по "слоям" (сначала все соседи, потом соседи соседей). Структура данных: Очередь (Queue). Сложность: \( \displaystyle O(|V| + |E|) \) |
| 5. | Поиск в глубину (DFS - Depth-First Search) | Идет вглубь по ветви до упора, затем возвращается (Backtracking). Структура данных: Стек (Stack) или рекурсия. Сложность: \( \displaystyle O(|V| + |E|) \) |
| 6. | Алгоритм Дейкстры | Находит кратчайший путь от одной вершины до всех остальных во взвешенном графе без отрицательных весов. Структура данных: Очередь с приоритетом (Min-Heap). Сложность: \( \displaystyle O(|E| + |V| \log |V|) \) |