Содержание
- 2. Метод поиска в ширину (BFS, Breadth-first search) Пусть задан граф G = (V, E) и некоторая
- 3. Алгоритм обхода в ширину Инициализация для ( ∀u ∈ (V\{s}) выполнить { цвет[u] ← белый; предок[u]←
- 4. пока (Q ≠ ∅) выполнить { u ← first (Q); //посмотреть первый эл-т для ( ∀v
- 5. Использование очереди В качестве промежуточной структуры хранения при обходе в ширину будем использовать очередь. 1 2
- 6. Нахождение кратчайшего пути в лабиринте 1 2 2 3 2 3 3 3 4 4 5
- 7. Пример построения остовных деревьев В глубину: В ширину: 1 6 2 3 4 5 8 7
- 8. Каркас графа. Определения G(V,E) - связный неориентированный граф с заданной функцией стоимости, отображающей ребра в вещественные
- 9. Алгоритм Краскала (Джозеф Крускал, 1956 год) Сортируем ребра графа по возрастанию весов. Полагаем, что каждая вершина
- 10. Время работы: Cортировка рёбер - O(|E|×log|E|) Компоненты связности удобно хранить в виде системы непересекающихся множеств. Все
- 11. Алгоритм Краскала Вход. Неориентированный граф G= (V, Е) с функцией стоимости с, заданной на его ребрах.
- 12. Пример м1 1 3 4 9 23 17
- 13. Получившееся дерево является каркасом минимального веса. Введем массив меток вершин графа Mark. Начальные значения элементов массива
- 15. Алгоритм Прима На каждом шаге вычеркиваем из графа дугу максимальной стоимости с тем условием, что она
- 16. Пример м1 1 3 4 9 23 17 20 15 36 25 28 16
- 17. Алгоритм Прима ( Ярника, Дейкстры ) Алгоритм впервые был открыт в 1930 году чешским математиком Войцехом
- 18. 1) Выбирается произвольная вершина - она будет корнем остовного дерева; 2) Измеряется расстояние от нее до
- 19. 10 2 3 6 1 8 5 7 4 9 1 1 1 2 2 2
- 20. Реализация за O (M log N + N2) Отсортируем все рёбра в списках смежности каждой вершины
- 21. Система непересекающихся множеств (СНМ) Система непересекающихся множеств — это структура данных, которая реализует разбиение множества. Каждое
- 22. СНМ поддерживает следующие операции: MakeSet (x) — добавляет в СНМ новый элемент x, который заносится в
- 23. Простая реализация В этой реализации для каждого элемента множества хранится номер или, другими словами, цвет подмножества,
- 24. Реализация с помощью списков 1 способ. Если хранить множества в виде линейных списков с указателями на
- 25. Весовая эвристика Весовая эвристика — это улучшение простой реализации, в которой следует перекрашивать элементы из множества
- 26. Реализация с использованием дерева
- 27. Применение весовой эвристики (вес вершины – количество узлов в ее поддереве)
- 28. Если размер дерева равен k, то его высота не более ⎣log k⎦ . Доказательство по индукции:
- 29. Эвристика объединением по рангу (ранг вершины – максимальная высота ее поддеревьев)
- 30. При применении ранговой эвристики получаем дерево высоты O(log n) Покажем, что если ранг дерева равен k,
- 31. Эвристика сжатия путей
- 32. Пример реализации СНМ const int MAXN = 1000; int p[MAXN], rank[MAXN]; void makeset (int x) {
- 34. Скачать презентацию