Обход - граф
Cтраница 3
Алгоритм выделения в смешанном дереве исходов D ( А, V) подграфов, соответствующих совокупным вариантам, базируется на процедуре пошагового обхода графа D, начиная от его конечных вершин. [31]
Полагая, что вершины соответствуют районам суши, а ребра - мостам, эту задачу можно сформулировать в виде вопроса о возможности последовательного обхода графа, изображенного на рис. 2, с условием однократного использования его ребер и возвращения в исходную точку. [32]
 |
Пример обхода графа в глубину. [33] |
Рассмотрим пример расчета по программе алгоритма 6.2 обхода графа, представленного на рис. 6.13. Сплошными линиями отмечены ребра, которые были пройдены во время обхода графа в глубину, пунктирными - обратные ребра. [34]
С помощью любого из этих методов можно проверить, связен ли рассматриваемый граф. При обходе графа можно составлять список пройденных узлов, а по завершении обхода составленный список можно сравнить со списком всех узлов графа. Если списки содержат одни и те же элементы, то граф связен. В противном случае в графе есть вершины, до которых нельзя дойти из начальной вершины, поэтому он несвязен. [35]
Легко видеть, что в результате получится растущее дерево А, которое содержит только вершины дерева D, достижимые из г с помощью ориентированных цепей. В этом смысле любой обход графа D охватит все вершины, которые можно достигнуть. [36]
Такой способ представления удобен для графов с небольшим количеством ребер. Однако для алгоритмов обхода графов он неудобен: здесь требуется перевод во внутреннее представление. [37]
Таким условием является завершение обхода графа требований, включая отдельные вершины. [38]
В таком случае совершается обход плоскости, целью которого является обнаружение всех пикселов, достижимых из затравочной точки без пересечения контура. Моделью этой процедуры может служить обход графа, предусматривающий использование какой-либо из рассмотренных в гл. Заполнение области по критерию связности уместно осуществлять лишь с помощью алгоритмов, предусматривающих анализ значений яркости пикселов, поскольку этот критерий предполагает произвольный доступ к пикселам, находящимся внутри области. [39]
Данный алгоритм выполняет последовательную построчную обработку, причем в памяти должно храниться лишь небольшое число строк или их частей. Для простоты будем описывать работу алгоритма как процесс обхода графа смежности строк, хотя запоминание последнего в явном виде не предусматривается. Анализ параллельного режима работы проведен в гл. Для данного алгоритма весьма существенным являются понятия вертикального, горизонтального и диагонального маршрутов, которые мы определим следующим образом. [40]
Генерация поискового индекса требует систематического обхода Web-утоъ и определения местонахождения каждого документа. Структура Web аналогична структуре ориентированного графа, поэтому здесь применимы алгоритмы обхода графа. [41]
Генерация поискового индекса требует систематического обхода Web-узяов и определения местонахождения каждого документа. Структура Web аналогична структуре ориентированного графа, поэтому здесь применимы алгоритмы обхода графа. [42]
Простейший матричный алгоритм отыскания бикомпонент, описанный в § 2, принадлежит, по-видимому, С. Несколько методов описано в книге А. А. Зыкова [33]; наиболее эффективные алгоритмы основаны на обходе графа, представленного списками смежности, с использованием стра тегии поиска в глубину. Близок к ним ( в смысле использования стратегии поиска в глубину) алгоритм В. Н. Касьянова [42], основанный на специальных нумерациях вершин. Поттосину [69], алгоритм отыскания линейных, компонент принадлежит В. [43]
Более подробные сведения о методах реализации и обработки стеков и очередей читатель может найти в одной из множества имеющихся книг, посвященных алгоритмам и структурам данных ( см. также разд. Обход графа можно осуществлять и не прибегая к использованию указанных структур данных - эта возможность связана с применением поиска с возвратом при отсутствии иных способов продолжения обхода. [44]
Точки сочленения можно обнаружить с помощью грубой силы, удаляя из графа поочередно каждую вершину и пользуясь одним из наших алгоритмов обхода графа для проверки связности оставшейся части. Если оставшийся граф связен, то удаленная вершина не является точкой сочленения. При таком подходе мы должны выполнить N обходов графа с N вершинами, что потребует 0 ( 7V2) операций. Однако сохраняя незначительное количество дополнительной информации при обходе графов, можно обнаружить все точки сочленения и компоненты двусвязности при единственном обходе. [45]
Страницы: 1 2 3 4