![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 18. Поиск на графе. Подобное поведение типично для поиска в глубину, хотя эти характеристики и не гарантируются для всех графов
Упражнения 18.15. Сделайте чертеж леса DFS, который получается в результате применения стан 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4. 18.16. Сделайте чертеж леса DFS, который получается в результате применения стан 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4. 18.17. Составьте программу трассировки поиска в глубину, которая в стиле упраж о 18.18. Напишите программу, которая вычисляет представление полного дерева DFS в виде родительских связей (включая внешние узлы) с использованием вектора из Е целых чисел, принимающих значения в диапазоне от 0 до V— 1. Указание. Первые две компоненты этого вектора должны быть такими же, что и компоненты вектора st, описание которого дано в тексте. о 18.19. Снабдите класс DFS остовного дерева (программа 18.3) функциями-элементами (и соответствующими элементами данных), которые подсчитывают высоту самого высокого дерева леса, число обратных ребер и процент ребер, которые необходимо обработать, чтобы просмотреть каждую вершину. • 18.20. Проведите эксперименты с целью определения эмпирическим путем средних • 18.20. Напишите функцию, выполняющую построение графа за счет вставки ребер, Часть 5. Алгоритмы на графах
РИСУНОК 18.13. ПОИСК В ГЛУБИНУ Этот рисунок показывает, как протекает процесс поиска в глубину в случайном эвклидовом графе с близкими связями (слева). На рисунке показаны вершины и ребра дерева DFS в графе по мере того, как процедура поиска просматривает 1/4, 1/2, 3/4 и все вершины графа (сверху вниз). Дерево DFS (только древесные ребра) показано справа. Из этого примера следует, что для дерева поиска в глубину для графов рассматриваемого типа (как и для многих других типов графов, часто встречающихся на практике) характерна узкая продолговатая форма. Обычно мы находим где-то рядом вершину, которая еще не подвергалась просмотру.
|