Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Поискнаграфе
|
|
| М |
ы часто изучаем свойства графа, систематически исследуя каждую из его вершин и каждое ребро. Определение некоторых простых свойств - например, вычисление степеней всех его вершин - выполняется просто, если мы исследуем каждое ребро (в любом порядке). Многие другие свойства графа имеют отношение к путям на графах, таким образом, естественный порядок их изучения состоит в переходе от одной вершине к другой вдоль ребер графа. Почти все алгоритмы обработки графов, которые мы применяем, используют эту базовую абстрактную модель. В данной главе мы рассматриваем фундаментальные алгоритмы поиска на графах (graph search), которые используются для перемещения по графам, с изучением по мере продвижения его структурных свойств.
Поиск на графе в таком виде эквивалентен исследованию лабиринта. Точнее, коридоры в лабиринте соответствуют ребрам графа, а точки, в которых коридоры в лабиринте пересекаются, соответствуют вершинам графа. Когда программа меняет значение переменной при переходе от вершины v к вершине w, что обусловлено наличием ребра v-w, мы отождествляем его с передвижением человека из точки v в точку w. Мы начинаем эту главу с изучения методов систематического исследования лабиринтов. В соответствии с этим процессом, мы наглядно представляем себе, как базовые алгоритмы поиска по графу проходит через каждое ребро и каждую вершину графа.
В частности, рекурсивный алгоритм DFS (depth-first search — поиск в глубину) точно соответствует конкретной стратегии исследования лабиринта, избранной в главе 18. Поиск в глубину представляет собой классический гибкий алгоритм, который применяется для решения задачи связности и множества других задач обработки графов. Возможны две
Часть 5. Алгоритмы на графах
реализации этого базового алгоритма; одна в виде рекурсивной процедуры и другая — с использованием явно заданного стека. Замена стека очередью FIFO (First in First Out -первым пришел, первым обслужен) приводит к другому классическому алгоритму - к алгоритму BFS (breadth-first search — поиск в ширину), который используется для решения других задач обработки графов, связанных с нахождением кратчайших путей.
Основной темой, рассматриваемой в данной главе, являются алгоритмы поиска в глубину, поиска в ширину и другие связанные с ними алгоритмы, а также их применение при обработке графов. Краткий обзор алгоритмов поиска в глубину и поиска в ширину было проведено в главе 5, тогда как здесь мы их рассматриваем на основании первого принципа, в контексте классов, выполняющих обработку графов на основе поиска, и используем их, чтобы показать, какие отношения устанавливаются между различными алгоритмами обработки графов. В частности, мы рассмотрим общий подход к поиску на графах, который охватывает некоторое множество классических алгоритмов обработки графов, в том числе алгоритмов поиска в глубину и поиска в ширину.
В качестве иллюстрации применения этих базовых методов поиска на графах для решения более сложных задач мы будем рассматривать алгоритмы поиска связных компонент, двусвязных компонент, остовных деревьев и кратчайших путей, а также алгоритмы решения множества других задач по обработке графов. Эти реализации являют собой примеры подхода, который мы намерены использовать для решения более трудных задач в главах 19-22.
Мы завершим эту главу исследованием основных проблем, сопряженных с анализом алгоритмов на графах в контексте конкретного случая, сравнивая несколько различных алгоритмов определения числа связных компонент в конкретном графе.