Глава 18. Поиск на графе. Подобное поведение типично для поиска в глубину, хотя эти характеристики и не га­рантируются для всех графов

Подобное поведение типично для поиска в глубину, хотя эти характеристики и не га­рантируются для всех графов. Проверка наличия фактов этого рода для моделей графов, представляющих интерес, и различных типов графов, возникающих на практике, требу­ет подробных исследований. В то же время этот пример позволяет выработать интуитив­ное восприятие алгоритмов, использующих поиск в глубину, которое часто подтвержда­ется на практике. Рисунок 18.13 и аналогичные иллюстрации других алгоритмов поиска на графе (см. рис. 18.24 и 18.29) помогают лучше понять различия в их поведении.

Упражнения

18.15. Сделайте чертеж леса DFS, который получается в результате применения стан­
дартного 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, который получается в результате применения стан­
дартного 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.10 производит классификацию каждого из двух представлений любого реб­
ра графа на соответствие древесной связи, родительской связи, связи назад или свя­
зи вниз в дереве DFS.

о 18.18. Напишите программу, которая вычисляет представление полного дерева DFS в виде родительских связей (включая внешние узлы) с использованием вектора из Е целых чисел, принимающих значения в диапазоне от 0 до V— 1. Указание. Первые две компоненты этого вектора должны быть такими же, что и компоненты вектора st, описание которого дано в тексте.

о 18.19. Снабдите класс DFS остовного дерева (программа 18.3) функциями-элемента­ми (и соответствующими элементами данных), которые подсчитывают высоту самого высокого дерева леса, число обратных ребер и процент ребер, которые необходимо обработать, чтобы просмотреть каждую вершину.

• 18.20. Проведите эксперименты с целью определения эмпирическим путем средних
значений количественных величин, описанных в упражнении 18.19, для графов различ­
ных размеров, полученных для графов различных моделей (см. упражнения 17.64-
17.76).

• 18.20. Напишите функцию, выполняющую построение графа за счет вставки ребер,
выбранных случайным образом из заданного вектора и вставки в первоначально пус­
той граф. Используя эту функцию вместе с реализацией АТД графа, представленного
в виде списков смежных вершин, проведите эксперименты с целью определения эм­
пирическим путем свойств распределения количественных величин, описанных в упраж­
нении 18.19, для всех представлений примеров крупных графов различных размеров
в виде списков смежных вершин и различных моделей (см. упражнения 17.64-17.76).

Часть 5. Алгоритмы на графах

РИСУНОК 18.13. ПОИСК В ГЛУБИНУ

Этот рисунок показывает, как протекает процесс поиска в глубину в случайном эвклидовом графе с близкими связями (слева). На рисунке показаны вершины и ребра дерева DFS в графе по мере того, как процедура поиска просматривает 1/4, 1/2, 3/4 и все вершины графа (сверху вниз). Дерево DFS (только древесные ребра) показано справа. Из этого примера следует, что для дерева поиска в глубину для графов рассматриваемого типа (как и для многих других типов графов, часто встречающихся на практике) характерна узкая продолговатая форма. Обычно мы находим где-то рядом вершину, которая еще не подвергалась просмотру.

⇐ Предыдущая55565758596061626364Следующая ⇒