Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 18. Поиск на графе. Этот рисунок прослеживает процесс поиска в ширину на заданном примере
РИСУНОК 1821. ПОИСК В ШИРИНУ Этот рисунок прослеживает процесс поиска в ширину на заданном примере. Мы начинаем его на всех ребрах, смежных с исходной вершиной в очереди (диаграмма вверху слева). Далее, мы переносим ребро 0-2 из очереди в дерево и приступаем к обработке инцидентных ему ребер 2-0 и 2-6 (вторая диаграмма сверху слева). Мы не помещаем ребро 2-0 в очередь, поскольку вершина 0 уже содержится в дереве. Затем мы переносим ребро 0-5 из очереди в дерево; и снова ребра, инцидентные вершине 5, не приводят нас к новым вершинам, однако мы добавляем в очередь ребра 5-3 и 5-4 (третья диаграмма сверху слева). После этого мы добавляем ребро 0-7 в дерево и устанавливаем ребро 7-1 в очередь (диаграмма внизу слева). Часть 5. Алгоритмы на графах
Как мы могли убедиться в разделе 18.4, поиск в глубину подобен исследованию лабиринта, проводимого одним человеком. Поиск в ширину можно сравнить с исследованием, проводимым группой людей, рассыпавшихся веером по всем направлениям. Несмотря на то что поиски в глубину и в ширину отличаются друг от друга во многих аспектах, здесь уместно подчеркнуть то, что между этими двумя методами существует прочная глубинная связь — такая, какую мы обнаружили, когда проводили краткий анализ методов в главе 5. В разделе 18.8 мы рассмотрим обобщенный метод поиска на графе, который мы можем переделать таким образом, чтобы он включал в себя оба эти алгоритма, равно как и множество других. Каждый алгоритм обладает собственными динамическими характеристиками, которые мы используем для решения соответствующих задач обработки графов. Что касается поиска в ширину, то наибольший интерес для нас представляет расстояние каждой вершины от исходной вершины (длина кратчайшего пути, соединяющего две эти вершины). Свойство 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 не может быть короче.
|