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