русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Поиск остовного дерева в ширину и поиск в глубину


Дата добавления: 2013-12-23; просмотров: 11245; Нарушение авторских прав


Минимального остовного дерева

Лекция 4. Поиск остовного дерева в ширину и поиск в глубину. Алгоритмы Прима и Краскала (жадный) для поиска

Дана неориентированная сеть N, нужно выбрать подмножество дуг, образующих дерево Т, в котором существует путь между каждой парой узлов сети. Дерево такого типа называется остовным деревом сети.

Во многих приложениях нужно в определенном порядке посетить все узлы графа, т. е. построить остовное дерево.

Рассмотрим следующие два общих способа обхода, называемые поиском в ширину (BFS, breadth-first-search) и поиском в глубину (DFS, depth-first-search).

Поиск в ширину, BFS. Выбираем произвольно узел графа G, назовем этот узел V0 и затем посетим всех соседей V0 в произвольном порядке, например, это узлы V1 , V2, …, Vi. После посещения всех соседей V0 начать обход заново из V1 (первого посещенного соседа узла V0) и посетить все соседние с V1 узлы, скажем, V11, V12,…, V1j, потом все новые узлы, соседние с V2, скажем, V21, V22, …, V2k. Систематически получаем:

 

Порядок Соседние узлы
V0 V1 , V2, …, Vi
V1 V11, V12,…, V1j
V2 V21, V22,…, V2j
V11 V11 1, V11 2,…, V11 j
V12 V12 1, V12 2,…, V12 j

 

На рис. 11 можно взять за V0 узел Va, тогда узлы можно посетить в следующем порядке:

V0, Vb, Vc, Vd, Ve, Vf,

V0, V1, V2, V11, V21 , V11 1.

 

Рис. 11.

 

Если взять в качестве V0 узел Vb, то можно посетить вершины в порядке

Vb , Va , Vc, Vd, Ve, Vf,

V0, V1 , V2, V3, V21, V31.

Замечание 1. После посещения нового узла можно посетить соседей нового узла в произвольном порядке. Здесь используется соглашение о том, что при необходимости выбора узлы посещаются в алфавитном порядке.

Замечание 2. Если пометить дугу, соединяющую посещенный узел с ранее посещенным узлом, то все эти помеченные дуги образуют остовное дерево графа G; если же каждая дуга имеет длину 1, то остовное дерево является деревом кратчайших путей из V0 во все остальные узлы G.



Поиск в глубину, DFS. Выбираем произвольно вершину V0, а затем следуем по ребру е01 в узел Vi , потом следуем по ребру e12 в узел V2, соседний с V1 . Вобщем случае, после посещения узла Vi следуем по ребру eij в узел Vj, если Vj ранее еще не был посещен. Далее применяем рекурсивно этот процесс к Vj и выбираем ребро ejk в узел Vk. Если вершина Vj уже была посещена, то возвращаемся в Vi и выбираем другое ребро. Если все ребра, инцидентные Vi, уже выбраны и нельзя найти ни одной новой вершины, то возвращаемся из Vj в предыдущую вершину, за которой идет Vi, и проверяем ей инцидентные ребра.

Если на рис. 11 начать с вершины Vb, то можно посетить узлы в следующем порядке (упорядочение определяется не единственным образом):

Vb, Vc, Va, Vd, Ve, Vf.

Дуги, следующие в новые вершины, образуют остовное дерево. Это дуги: ebc, eca, ecd, ede, eef.

Можно сравнить два способа посещения узлов. При BFS нужно проверить все ребра, инцидентные узлу, перед переходом к новому узлу. Таким образом, операция последовательно выполняется веером из узлов. При DFS переход к новому узлу осуществляется только после того, как найден новый узел, и происходит проникновение в глубину графа. Только тогда, когда все ребра ведут в старые вершины, идет возврат к предыдущему узлу и из него опять возобновляется DFS.

Алгоритмы BFS и DFS имеют одинаковую сложность для самого неблагоприятого случая. Сложность алгоритма для самого неблагоприятного случая – это приблизительная мера максимального числа действий, требуемых, чтобы выполнить алгоритм. Это функция размера входных данных, которые непосредственно в нашем случае были представлены графом (например, О(n)). Так как алгоритмы имеют одинаковую сложность, то ни один из них не имеет преимуществ перед другим. Тем не менее, для целого ряда специфических графов один алгоритм мог бы производить дерево покрытия эффективнее, чем другой. Например, поиск «по глубине» эффективнее для графа «колеса», а поиск «ширине» для графа «Мальтийский крест».



<== предыдущая лекция | следующая лекция ==>
Лекция 3. Кратчайшие пути между всеми парами узлов | Минимальное остовное дерево


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.004 сек.