![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 18. Поиск на графе. Этот рисунок прослеживает процесс поиска в ширину на заданном примере
РИСУНОК 1821. ПОИСК В ШИРИНУ Этот рисунок прослеживает процесс поиска в ширину на заданном примере. Мы начинаем его на всех ребрах, смежных с исходной вершиной в очереди (диаграмма вверху слева). Далее, мы переносим ребро 0-2 из очереди в дерево и приступаем к обработке инцидентных ему ребер 2-0 и 2-6 (вторая диаграмма сверху слева). Мы не помещаем ребро 2-0 в очередь, поскольку вершина 0 уже содержится в дереве. Затем мы переносим ребро 0-5 из очереди в дерево; и снова ребра, инцидентные вершине 5, не приводят нас к новым вершинам, однако мы добавляем в очередь ребра 5-3 и 5-4 (третья диаграмма сверху слева). После этого мы добавляем ребро 0-7 в дерево и устанавливаем ребро 7-1 в очередь (диаграмма внизу слева). Часть 5. Алгоритмы на графах
Свойство 18.9. В процессе поиска в ширину вершины поступают в очередь FIFO и покидают ее в порядке, определяемом их расстоянием от исходной вершины. Доказательство: Справедливо более сильное условие: очередь всегда содержит ноль или большее число вершин, удаленных на к из исходной точки, за которой следует ноль или большее число вершин, удаленных на к + 1 от исходной точки, где к - некоторое целое значение. Это более сильное условие легко доказывается методом индукции. ■ Что касается поиска в глубину, то понимание динамических характеристик этого алгоритма достигается с помощью леса поиска DFS, который описывает структуру рекурсивных вызовов алгоритма. Основное свойство упомянутого леса состоит в том, что он представляет пути из каждой вершины в точку, откуда начался поиск связной компоненты, в которой она находится. Как показывает реализация и рис. 18.22, такое остовное дерево помогает достичь понимания поиска в ширину. Как и в случае поиска в глубину, мы имеем лес, который характеризует динамику поиска, по одному дереву на каждую связную компоненту, один узел дерева приходится на каждую верши- РИСУНОК 18.22. ДЕРЕВО BFS Это дерево представляет собой компактное описание динамических характеристик поиска в глубину в стиле, свойственном дереву, которое показано на рис. 18.9. Обход дерева в порядке уровней показывает нам, как разворачивается поиск: сначала мы наносим визит вершине 0, потом мы посещаем вершины 2, 5 и 7, затем, находясь в 2, мы выясняем, что в вершине 0 мы уже были, и направляемся в 6 и т.д. У каждого узла дерева имеются потомки, и каждый из них представляет узлы, смежные с этим узлом, в том порядке, в каком они рассматриваются алгоритмом BFS. Как и на рис. 18.9, связи дерева BFS соответствуют ребрам графа: если мы заменим ребра, ведущие во внешние узлы, на линии, ведущие в заданный узел, то мы получим чертеж графа. Связи, ведущие во внешние узлы, представляют собой ребра, которые не были помещены в очередь, так как они направлены в помеченные узлы: это либо родительские связи, либо перекрестные связи, которые указывают на некоторый узел, находящийся на том же уровне или на уровне, более близком к корню дерева. Вектор st есть представление дерева в виде родительских связей, которое мы можем использовать при поиске кратчайшего пути из любого узла в корень. Например, 3-5-0 представляет собой путь в графе из 3 в 0, поскольку st[3] есть 5, а st[5] - 0. Никакой другой путь из З в 0 не может быть короче.
|