![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Порядок порядок Пример Тип ребра
< > 4-2 Нисходящее < > 7-6 Поперечное Например, 7-6 представляет собой поперечное ребра, поскольку номер узла 7 в прямом и обратном порядке обхода больше, чем номер узла 6. Глава 19. Орграфы и ориентированные ациклические графы 1/1
ев DFS, и оба эти номера выше в тех узлах, которые предстоит посетить в других деревьях, однако нам не потребуется писать программный код для проверки подобных случаев. ■ Программа 19.2 реализует класс DFS, который определяет тип каждого ребра графа. Рисунок 19.10 служит иллюстрацией ее работы на примере орграфа, представленного на рис. 19.1. Проверка, проводимая с тем, чтобы убедиться, ведет ли то или иное ребро в узел с более высоким номером при обратном порядке обхода, эквивалентна проверке, был ли вообще присвоен узлу номер при обратном обходе. Любой узел, которому был присвоен номер в прямом порядке, но которому еще не был присвоен номер в обратном порядке, в дереве DFS является предшественником и получит более высокий номер в обратном порядке, чем номер в обратном порядке текущего узла. Как мы могли убедиться в главе 17, в которой рассматривались неориентированные графы, типы ребер — это и свойства динамики поиска, а не только свойства графа. В самом деле, как следует из рис. 19.11, различные леса DFS одного и того же графа могут существенно различаться по характеру. Например, четность номеров деревьев леса DFS зависит от начальной вершины. Тем не менее, несмотря на все эти различия, несколько классических алгоритмов обработки орграфов способны определить свойства орграфов благодаря тому, что РИСУНОК 19.10. ТРАССИРОВКА ОРГРАФА ПОИСКА В ГЛУБИНУ Трассировка поиска в глубину представляет собой выходные результаты программы 19.2 для примера орграфа, показанного на рис. 19.1. Она в точности соответствует обходу в прямом порядке дерева DFS на рис. 19.9.
|